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 2012-03-23 15:42:31