All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 Click to listen to the single ▶Support album on Kickstarter 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

 No Solution Yet Submitted by Ady TZIDON Rating: 4.0000 (1 votes)

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
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2014 by Animus Pactum Consulting. All rights reserved. Privacy Information