# $100$ boxes of fruits - pick $51$ and get at least half of each type?

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.

-
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
@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
@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

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.

-
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
No one solved it in a Russian maths olympiad! Man that is hard – Casebash Aug 16 '10 at 9:18