11
$\begingroup$

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.

  • 0
    What if there is only 2 apples in one box and the rest of the boxes have none? :/2010-08-15
  • 2
    @BBischof I guess you look in the boxes ;)2010-08-15
  • 0
    @BBischof, at least half, so having more than half is okay.2010-08-15
  • 1
    @Joshua I am implying that there would be no solution, because no 51 boxes would be guaranteed to have that one box.2010-08-16
  • 0
    @Jon Cheater!!!!!!!2010-08-16
  • 0
    @BBischof You can look in the boxes2010-08-16
  • 0
    Wait, what?! If you can look in the boxes, then you should be able to just calculate your solution based on the particular set-up. I guess I just don't understand this question.2010-08-16
  • 0
    There must be some condition that is missing.2010-08-16
  • 0
    @txwikinger, since the OP wasn't the original asker of the question(he says his friend asked him) then the OP may not realize the issue/know the condition :/ @n0vakovic, if this indeed is the case, maybe we should close this question, of course I would be more in favor of it getting fixed up and answered, but otherwise... :/ Thanks for asking though :)2010-08-16
  • 0
    @BBischof and others: My bad, language barriers... What should be the problem is to be sure you can always get half of everything in 51 boxes. Formulation edited. Sorry for the confusion.2010-08-16
  • 0
    @n0vakovic I don't understand that last message, but rather than talking by comments and filling this question up, just email me. The email address is bryan (dot) bischof (at) gmail (dot) com.2010-08-16
  • 0
    @BBishof Ha, what I meant to say is not only can look but you can grab the apples and move them around ;)2010-08-16
  • 0
    This feels a whole lot like [the ham sandwich theorem](http://en.wikipedia.org/wiki/Ham_sandwich_theorem) to me, though I can't quite make the connection into a proof.2010-08-16
  • 0
    Can you prove that the "hardest" problem is where every box is filled, but has a single piece of fruit in (e.g. 34 apples, 33 bananas, 33 oranges) - i.e. minimal variation between the boxes, since the more variation, the easier it becomes to pick out boxes that contain over half the fruit. And since it can be fairly easily shown that you can solve the hardest case, therefore all others are solvable?2010-08-16
  • 0
    What if you add another type of fruit?2010-08-16

1 Answers 1

6

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.

  • 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!2010-08-16
  • 3
    No one solved it in a Russian maths olympiad! Man that is hard2010-08-16