Maths Olympiad Prep

Library / /47 of 68

Combinatorics Difficulty 5.8 AIME, harder Prove it Estonia

During the schoolyear 2222 olympiads were held. At each one 55 best students were awarded. It is known that the prize receivers of every two olympiads had exactly 11 student in common. Show that there exists a student who got a prize at every olympiad.

Solution

Look at an arbitrary olympiad, let that be A1A_1, where the prizes went to some 55 students. Each of the remaining 2121 olympiads had to have someone among those 55 receiving a prize. By pigeonhole principle there exists a student who in addition to A1A_1 also got a prize at at least 55 olympiads. Let that student be aa and those olympiads be A2,,A6A_2, \dots, A_6.

Let now BB be an arbitrary olympiad that is different from A1,,A6A_1, \dots, A_6. As each one of the olympiads A1,,A6A_1, \dots, A_6 has one prize-winning student in common with BB and exactly 55 students get prizes at BB, applying pigeonhole principle again shows that one of those five had to get a prize at at least two of A1,,A6A_1, \dots, A_6. Since these two have student aa in common and according to initial conditions that student is the only one, this means that aa also got a prize at olympiad BB. But since we picked BB arbitrarily, aa must have got a prize at every olympiad.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.