uniolympiads Ελληνικά

IMC 2002, Day 2, Problem 2

Two hundred students participated in a mathematical contest. They had 66 problems to solve. It is known that each problem was correctly solved by at least 120120 participants. Prove that there must be two participants such that every problem was solved by at least one of these two students.

Original from the official PDFTwo hundred students participated in a mathematical con- test. They had 6 problems to solve. It is known that each problem was correctly solved by at least 120 participants. Prove that there must be two participants such that every problem was solved by at least one of these two students.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. For each pair of students, consider the set of those problems which was not solved by them. There exist (2002)=19900\binom{200}{2}=19900 sets; we have to prove that at least one set is empty.

For each problem, there are at most 80 students who did not solve it. From these students at most (802)=3160\binom{80}{2}=3160 pairs can be selected, so the problem can belong to at most 3160 sets. The 6 problems together can belong to at most 6⋅3160=189606\cdot3160=18960 sets.

Hence, at least 19900−18960=94019900-18960=940 sets must be empty.

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?