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
(In reply to
Still not there (4/5 solution?) by Steve Herman)
Steve,
The following is not a direct answer to your question, but it shows how at least 2 contestants who solve 5 of the problems can have each pair of problems solved by more than 2/5 of the contestants.
If there are 4 contestants, then it is only necessary that each pair be solved by 2 contestants (2/5 of 4 = 1.6 & 2 > 1.6). This can be accomplished with 2 of the contestants solving 5 and 2 solving 4. For example:
contestant : solved (pairs)
1 : 1,2,3,4,5
(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)
2 : 1,2,3,4,6
(1,2),(1,3),(1,4),(1,6),(2,3),(2,4),(2,6),(3,4),(3,6),(4,6)
3 : 1,2,5,6
(1,2),(1,5),(1,6),(2,5),(2,6),(5,6)
4 : 3,4,5,6
(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)
pair : solved by contestants [total who solved]
(1,2) : 1,2,3 [3]
(1,3) : 1,2 [2]
(1,4) : 1,2 [2]
(1,5) : 1,3 [2]
(1,6) : 2,3 [2]
(2,3) : 1,2 [2]
(2,4) : 1,2 [2]
(2,5) : 1,3 [2]
(2,6) : 2,3 [2]
(3,4) : 1,2,4 [3]
(3,5) : 1,4 [2]
(3,6) : 2,4 [2]
(4,5) : 1,4 [2]
(4,6) : 2,4 [2]
(5,6) : 3,4 [2] )
As to the shortfall, when 5 are solved by a contestant, 10 pairs are solved, yet there are 6 pairs unsolved that includes the unsolved problem. With each additional contestant solving only 4 (6 pairs), at least one of the unmatched pairs will be solved by fewer or equal to the 2/5 number of contestants.

Posted by Dej Mar
on 20120323 15:42:31 