Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 10 down vote favorite
4

Friend told me this one, I'm completely stuck but also completely fascinated:

There are 100 boxes with apples, oranges and bananas (mixed). How to Prove that you can pick 51 boxes and to get at least half of all apples, at least half of all oranges and at least half of all bananas?

Edit: You can take a look in the boxes.

share|improve this question
What if there is only 2 apples in one box and the rest of the boxes have none? :/ – BBischof Aug 15 '10 at 22:19
2  
@BBischof I guess you look in the boxes ;) – Jonathan Fischoff Aug 15 '10 at 22:34
@BBischof, at least half, so having more than half is okay. – Joshua Shane Liberman Aug 15 '10 at 23:55
1  
@Joshua I am implying that there would be no solution, because no 51 boxes would be guaranteed to have that one box. – BBischof Aug 16 '10 at 0:48
@Jon Cheater!!!!!!! – BBischof Aug 16 '10 at 0:49
show 10 more comments

1 Answer

up vote 6 down vote accepted

This is apparently a (hard) problem from the Russian Math Olympiad which no one in the exam solved.

See here for a list of questions in that exam: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=125&t=32171

A solution for this problem is here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1367869#p1367869

A hint that was given (by Fedor Petrov):

If we have $2k$ boxes, we may partition them into two groups of $k$ boxes in such a way that number of apples in both groups differ by at most the maximal number of apples in a single box, and the same for oranges.

share|improve this answer
2  
Ok, now I don't feel like complete idiot for not being able to solve it. Formulation sounds very innocent. What a beautiful problem! – n0vakovic Aug 16 '10 at 8:16
3  
No one solved it in a Russian maths olympiad! Man that is hard – Casebash Aug 16 '10 at 9:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.