XXVII Olimpiada Matemática Rioplatense

We will show that the maximum possible number of employees is $n=16$.

First, we prove that $n\le 16$. We represent each possible weekly schedule for an employee with a 7-tuple of 0's and 1's whose coordinates correspond to the days of the week and where 1 stands for 'working day' and 0 stands for 'non working day'.

The condition of the problem states that, for every pair of employees, their weekly schedules differ in at least 3 days, that is, the corresponding tuples differ in at least 3 coordinates.

Let $v_1,\dots ,v_n$ be the tuples representing the weekly schedules of the $n$ employees. For each $v_i$, there are 7 tuples differing in exactly one coordinate with $v_i$; we call them neighbors of $v_i$. Note that, if $i\ne j$, $v_j$ is not a neighbor of $v_i$, since they differ in at least 3 coordinates; in addition, $v_i$ and $v_j$ do not have common neighbors, since if there exists $v$ differing in exactly one coordinate with $v_i$ and exactly one coordinate with $v_j$, then $v_i$ and $v_j$ differ in at most 2 coordinates, contradicting the assumption.

Then, considering $v_1,\dots ,v_n$ and all their neighbors, we have $n+7n=8n$ different tuples. Since there are $2^7=128$ possible weekly schedules, we deduce that $8n\le 128$, which implies that $n\le 16$.

Finally, the following is an example with 16 employees satisfying the required conditions:

$$\begin{array}{rlrlrlrl}{v}_1& =(0,0,0,0,0,0,0),& v_2& =(1,1,1,0,0,0,0),& v_3& =(1,0,0,1,1,0,0),& v_4& =(1,0,0,0,0,1,0),\\ v_5& =(0,1,0,1,0,0,1),& v_6& =(0,1,0,0,1,1,0),& v_7& =(0,0,1,1,0,1,0),& v_8& =(0,0,1,0,1,0,1),\\ v_9& =(1,1,1,1,1,1,1),& v_{10}& =(0,0,0,1,1,1,1),& v_{11}& =(0,1,1,0,0,1,1),& v_{12}& =(0,1,1,1,1,0,0),\\ v_{13}& =(1,0,1,0,1,1,0),& v_{14}& =(1,0,1,1,0,0,1),& v_{15}& =(1,1,0,0,1,0,1),& v_{16}& =(1,1,0,1,0,1,0).\end{array}$$

We denote $d(v_i,v_j)$ the number of coordinates in which $v_i$ and $v_j$ differ. Note that:

$d(v_1,v_3)=3$, for $2\le j\le 8$, $d(v_1,v_9)=7$, and $d(v_1,v_j)=4$, for $10\le j\le 16$; for $2\le i\le 8$, $d(v_i,v_j)=4$, for $2\le j\le 9$, $j\ne i$, $d(v_i,v_j)=4$ for $10\le j\le 16$, $j\ne i+8$, and $d(v_i,v_{i+8})=7$; * $d(v_9,v_j)=3$, for $10\le j\le 16$, and $d(v_i,v_j)=4$ for $10\le i<j\le 16$.