A company has $n$ employees. It is known that each of the employees works at least one of the $7$ days of the week, with the exception of an employee who does not work any of the $7$ days. Furthermore, for any two of these $n$ employees, there are at least $3$ days of the week in which one of the two works that day and the other does not (it is not necessarily the same employee who works those days). Determine the highest possible value of $n$.
Problem
Source: Rioplatense Olympiad 2018 level 3 p6
Tags: combinatorics, maximum value
Davi Medeiros
28.03.2020 20:56
We will prove first that $n \le16$. To do so, consider the graph where the $2^7$ vertices represent each of the $2^7$ possible ways to build a week schedule for a worker (there are 2 possibilities for each of the 7 days: to work or not to work). We connect two vertices by an edge if, and only if, the weekly journey that represents them differs by exactly one day. Note that, with this, each vertex has degree 7.
Consider $v_1, ..., v_n$ the $n$ vertices that represent the weekly hours of each of the $n$ employees. We paint each vertex $v_i$ black and paint each of the 7 neighbors of each $v_i$ white. Notice that:
1. There are no two vertices painted in black and white (because if there were, there would be two employees whose weekly workload differs by 1 day, which is absurd, since these days differ by at least 3 days).
2. There is no vertex painted white more than once (for if there were such a vertex $v$, then $v$ is neighbor of $v_i$ and neighbor of $v_j$, and thus, like $v_i, v$ differ in one position, and $v_j, v$ differ in one position, so $v_i, v_j$ differ by a maximum of 2 positions, contradiction.
In this way, each vertex was painted at most once, and as we painted $8n$ vertices ($n$ being black and $7n$ being white, as they are neighbors of the n black vertices), so $8n \le 2^7 \Rightarrow n \le 16$.
Now we show that there's an example with 16 employees. If we view the weekly schedule as a 7-uple formed by $0$'s and $1$'s, with $0$ meaning "not work on that day" and $1$ meaning "work on that day, we can assign the schedules to the 16 employees in this way:
$$(0,0,0,0,0,0,0), (1,1,1,0,0,0,0), (1,0,0,1,1,0,0), (1,0,0,0,0,1,1), (0,1,0,1,0,0,1), (0,1,0,0,1,1,0), (0,0,1,1,0,1,0), (0,0,1,0,1,0,1)$$$$(1,1,1,1,1,1,1), (0,0,0,1,1,1,1), (0,1,1,0,0,1,1), (0,1,1,1,1,0,0), (1,0,1,0,1,1,0), (1,0,1,1,0,0,1), (1,1,0,0,1,0,1), (1,1,0,1,0,1,0)$$
It's not hard to see that this works.