All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Math. competition, (Posted on 2012-03-21)
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

Comments: ( Back to comment list | You must be logged in to post comments.)
 A start (spoiler?) | Comment 1 of 9
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.

 Posted by Steve Herman on 2012-03-21 10:39:26

 Search: Search body:
Forums (0)