In a mathematical competition, in which 6 problems were
posed to the participants, every two of these problems were solved by more
than 2/5 of the contestants.
Moreover, no contestant solved all the 6 problems.
Show that there are at least 2 contestants who solved exactly 5 problems
each.
source: IMO 2005
I guess I am doing something wrong. I seem to have at least 4 contestants solving 5 exactly. On the other hand, 4 is greater than 2, so maybe I have proved it.
My thinking is as follows. Assume n contestants, all of whom do 6 problems. There are therefore n*6*5/2 = 15n pairs of problems.
If a contestant solves 4, then he has solved 4*3/2 = 6 pairs of problems. If a contestant solves 5, than he has solved 5*4/2 = 10 pairs, which is 4 more pairs than the contestant who solves 4.
So, if every contestant solves 4, then there are 6n solved pairs out of 15n pairs of problems. If these solutions are spread evenly across all problems, then each pair of problems is solved an average of 2/5 of the time, which is not enough solutions to get them all solved more than 2/5 of the time.
It seems to me that we need 15 more solved pairs to get every pair above 2/5, and each contestant who solves 5 adds an additional 4 solved pairs to the total count, so we need at least 4 solvers who solve exactly 5 (since nobody solved exactly 6).
So have I gone wrong someplace? Probably so, as this is difficulty 4.
A start (spoiler?)
