Maths Olympiad Prep

Track / Stage 5 / 340 of 400 #1420 of 2444

Problem 1420

AIME late
Combinatorics Difficulty 5.8 Prove it Estonia — Open Contests · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

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