During the schoolyear olympiads were held. At each one best students were awarded. It is known that the prize receivers of every two olympiads had exactly student in common. Show that there exists a student who got a prize at every olympiad.
Problem 1420
Official solution
Look at an arbitrary olympiad, let that be , where the prizes went to some students. Each of the remaining olympiads had to have someone among those receiving a prize. By pigeonhole principle there exists a student who in addition to also got a prize at at least olympiads. Let that student be and those olympiads be .
Let now be an arbitrary olympiad that is different from . As each one of the olympiads has one prize-winning student in common with and exactly students get prizes at , applying pigeonhole principle again shows that one of those five had to get a prize at at least two of . Since these two have student in common and according to initial conditions that student is the only one, this means that also got a prize at olympiad . But since we picked arbitrarily, must have got a prize at every olympiad.