On a mathematical competition n problems were given. The final results showed that:
(1) on each problem, exactly three contestants scored 7 points;
(2) for each pair of problems, exactly one contestant scored 7 points on both problems;
Prove that if n>= 8, then there is a contestant who got 7 points at each problem. Is the statement necessarily true for n=7?
Italian TST 2000
Let $ k $ be the greatest number of problems solved by a contestant. Let $ A $ be the set of $ k $ problems solved by such a contestant. Suppose $ k<n $.
First, condition (2) tells us that every pair of problems is "connected" exactly once (i.e. by exactly one contestant).
Considering a problem $ p $ not included in $ A $, it has to have a contestant in common with each of the problems in $ A $, but so that for each pair of problems in $ A $, these aren't solved both by the same contestant again. Therefore you need $ k $ contestants to "connect" $ p $ to the elements of $ A $, so $ k\leq 3 $, because of the condition (1).
If every contestant solved $ \leq 3 $ problems, each problem is connected at most with 2 other problems for each contestant who solved it, so at most 6. But this can't be if $ n\geq 8 $ because there are two problems not connected.
In the case $ n=7 $ it's easy to find a configuration that shows there hasn't necessarily to be a contestant who solved each problems. For example, if
problem 1 was solved by contestants a,b,c;
problem 2 was solved by contestants a,d,e;
problem 3 was solved by contestants a,f,g;
problem 4 was solved by contestants b,d,g;
problem 5 was solved by contestants b,e,f;
problem 6 was solved by contestants c,e,g;
problem 7 was solved by contestants c,d,f,
it's easy to check that the conditions are verified.
First, condition (2) tells us that every pair of problems is "connected" exactly once (i.e. by exactly one contestant).
Considering a problem $ p $ not included in $ A $, it has to have a contestant in common with each of the problems in $ A $, but so that for each pair of problems in $ A $, these aren't solved both by the same contestant again. Therefore you need $ k $ contestants to "connect" $ p $ to the elements of $ A $, so $ k\leq 3 $, because of the condition (1).
If every contestant solved $ \leq 3 $ problems, each problem is connected at most with 2 other problems for each contestant who solved it, so at most 6. But this can't be if $ n\geq 8 $ because there are two problems not connected.
In the case $ n=7 $ it's easy to find a configuration that shows there hasn't necessarily to be a contestant who solved each problems. For example, if
problem 1 was solved by contestants a,b,c;
problem 2 was solved by contestants a,d,e;
problem 3 was solved by contestants a,f,g;
problem 4 was solved by contestants b,d,g;
problem 5 was solved by contestants b,e,f;
problem 6 was solved by contestants c,e,g;
problem 7 was solved by contestants c,d,f,
it's easy to check that the conditions are verified.
Non per andare OT, ma tutto ad un tratto nel forum si scrive in inglese 
?!
Per carità, non è di certo un problema, ma c'è gente che potrebbe non capire (spero di non essere smentito subito
).
?!Per carità, non è di certo un problema, ma c'è gente che potrebbe non capire (spero di non essere smentito subito
)."[i]What is a good Olympiad problem?[/i] Its solution should not require any prerequisites except cleverness. A high scool student should not be at a disadvantage compared to a professional mathematician."