
Problem 3. In a competition 8 judges marked the contestants by yes or no. It is known that for any two contestants, two judges gave both a yes; two judges gave the first one a yes and the second one a no; two judges gave the first one a no and the second one a yes, and finally, two judges gave both a no. What is the greatest possible number of contestants?

Emil Kolev


Solution: Denote the number of contestants by $n$. Consider a table with 8 rows and $n$ columns such that the cell in the $i$ th row and $j$ th column contains 0 (1) if the $i$ th judge gave the $j$ th contestant a no (a yes). The conditions of the problem now imply that the table formed by any two columns contains among its rows each of the pairs $00,01,10$ and 11 twice. We shall prove that 8 columns having this property do not exist. Assume the opposite. It is easily seen that if in any column all 0s are replaced by 1 s and vice versa, the above property is retained. Therefore without loss of generality suppose that the first row consists of 0s. Denote the number of $0 \mathrm{~s}$ in the $i$ th row by $a_{i}$. It is clear that the total number of $0 \mathrm{~s}$ is $8 \cdot 4=32$. Further, the number of occurrences of 00 is $\binom{8}{2} \cdot 2=56$. On the other hand the same number is $\sum_{i=1}^{8}\binom{a_{i}}{2}$. Since $a_{1}=8$, it
follows that $\sum_{i=2}^{8} a_{i}=24$. It is easy to prove now that $\sum_{i=2}^{8}\binom{a_{i}}{2} \geq 30$. Therefore $56=\sum_{i=1}^{8}\binom{a_{i}}{2} \geq 58$, which is false.

The diagram on the right shows that it is possible to have exactly

| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 |
