On a mathematical competition $ n$ problems were given. The final results showed that: (i) on each problem, exactly three contestants scored $ 7$ points; (ii) for each pair of problems, exactly one contestant scored $ 7$ points on both problems. Prove that if $ n \geq 8$, then there is a contestant who got $ 7$ points on each problem. Is this statement necessarily true if $ n = 7$?
Problem
Source: Italy TST 2000
Tags: combinatorics unsolved, combinatorics
28.09.2008 22:17
Suppose there's no one who got every problem, but suppose someone got over 3 problems. (i.e. questions 1,2,3,4...). Then there must be a problem k he/she did not get. Someone else must have gotten k and 1, but he did not get 2, 3 or 4 by (ii). Similarly with k and 2, k and 3 and k and 4. Then k was solved at least 4 times contradiction. So noone got over 3 problems. Any group of 3 problems contribute 3 pairs of problems. So at maximum all problems contribute 3n pairs. However, we have (n)(n-1)/2 pairs who must be solved together. If n = 7, then 3n = (n)(n-1)/2. If n > 7, then 3n < (n)(n-1)/2. So the (n)(n-1)/2 pair condition cannot be filled. Thus if n is over 8 there must be one contestant who got every problem. 7 can be done. (1,2,3), (1,4,5), (1,6,7), (2,4,6), (2,5,7), (3,4,7), (3,5,6)
12.01.2012 13:45
Look at each problem $P_k$, $1\leq k \leq n$, as being the set of those contestants scoring $7$ points on it. Then (i) means $|P_k| = 3$ for all $1\leq k\leq n$, and (ii) means $|P_k \cap P_{\ell}| = 1$, for all $1\leq k \neq \ell \leq n$. We are asked to prove that if $n\geq 8$ then $\left | \bigcap_{1\leq k \leq n} P_k\right |$, and to find a counterexample for $n=7$. This is related to the Erdös-de Bruijn theorem; the counterexample for $n=7$ is the finite projective plane of order $2$, known as the Fano configuration, also known as the symmetric BIBD $(7,3,1)$.