5
$\begingroup$

Inspired by Mike Earnest's 99 Bags of Apples and Oranges...

You have 100 bags, each containing various numbers of apples, beetroots, and cakes. Prove that there exist 51 bags among these which between them contain at least half the apples and at least half the beetroots and at least half the cakes.

Needless to say, you may not add or remove fruits to/from the bags.

As in the previous post, each bag can contain any number of each foodstuff with any total number, and the total amount of fruit in a bag doesn't have to be the same for each bag.

$\endgroup$
  • $\begingroup$ can a bag have only one fruit.....lets say one bag have only apples...? $\endgroup$ – user2408578 May 25 '15 at 6:14
  • $\begingroup$ @user2408578 Yep, no restrictions whatsoever. $\endgroup$ – Rand al'Thor May 25 '15 at 8:54
6
$\begingroup$

Take the bag with the most apples, and set it aside. Let's say it had $A$ apples. Do the same with the one with the most beets, and say it had $B$ beets. We ignore these until the very end.

Queue up the remaining $98$ bags in order of number of apples. We split these $98$ bags into a Left and Right pile, using the following algorithm:

While the queue is nonempty, remove two bags at the end with fewer apples. 
Of these two bags, call the bag with more beets X, and the other Y.
Throw X into either the Left or Right pile, whichever has FEWER beets.
Throw Y into the other pile.

I claim that, when this is done, that the "apple discrepancy" between the Left and Right piles is at most $A$, and the "beet discrepancy" is at most $B$.

Let's say the apple sizes were $a_1\le a_2\le \dots\le a_{98}$. In the worst case, the apple discrepancy is $$(a_{98}+a_{96}+\dots+a_2)-(a_{97}+\dots+a_1)$$$$=a_{98}-(a_{97}-a_{96})-\dots-(a_3-a_2)-a_1\le a_{98}\le A,$$ proving the first half of the claim.

To prove the second half, we first show that, after every pair of bags is thrown, the the pile with more beets will have a "pivotal bag," one whose removal will cause this pile to have at most as many beets as the other. Assume by induction this is true after $2n-2$ bags have been thrown, and let's say that Left has at least as many beets as Right at this point.

  • If Left still has at least as many beets after throwing bags number $2n-1$ and $2n$, then whatever bag was pivotal before is still pivotal now.

  • If, on the other hand, throwing these two bags causes Right to have more beets, then the bag thrown into Right is now pivotal.

By induction, there is always a pivotal bag. Therefore, the discrepancy is at most the number of beets in the pivotal bag, which is at most $B$, proving the claim.

Now, we have two piles, Left and Right, each with $49$ bags, and the two bags set aside at the beginning. Throw those two bags into whichever of Left and Right (let's say it was Left) has more cakes. Left might have had fewer apples than right, but from the claim, we know it was losing by at most $A$. After the bag with $A$ apples is thrown in, Left now has at least as many apples as right. Same for the beets. Thus, Left now has at least half of each foodstuff.

$\endgroup$
  • $\begingroup$ Looks great! I haven't got the time to work through this proof properly now, but will do later. PS: congrats on becoming a Trusted User :-) $\endgroup$ – Rand al'Thor May 25 '15 at 18:33
8
$\begingroup$

Here is an answer which is overkill, using an unintuitive technical analysis theorem instead of combinatorics, but which surprisingly works.

Assume all fruits have the same volume and density. Arrange the bags in 3-dimensional space in such a way that any plane intersects the contents of at most 3 bags. This is always possible to do (think about it).

By the ham sandwhich theorem, there exists a plane such that there is an equal volume of apples on either side of the plane, and similarly for the beetroots and cakes. At this point, there are at most 3 bags crossing the plane, so at least 97 not crossing it. This means that one side of the plane has at most 48 bags. Furthermore, these at most 48 bags, combined with the at most 3 bags on the border, contain half the volume of each food. Thus, combined together, these at most 51 bags contain half of each food by volume, and therefore by number.

$\endgroup$
  • $\begingroup$ +1 this explanation is nice one.....with Ham Sandwhich Theorem $\endgroup$ – user2408578 May 25 '15 at 9:05
  • 2
    $\begingroup$ Nice. The Ham Sandwich Theorem generalizes to any number of dimensions, so your argument does, too: if there are $n$ bags and $k$ foodstuffs, then one can find $\lfloor(n-k)/2\rfloor+k$ bags containing at least half of each foodstuff, and it is not too hard to write down an example in which each bag contains a fixed quantity of a single foodstuff to show that this is the best possible. $\endgroup$ – Julian Rosen May 25 '15 at 16:18
  • $\begingroup$ Could you explain a bit more how the ham sandwich theorem is applicable? I'm surprised at such a short proof, and wonder if there may be a hole in it somewhere. This problem is known for being really hard (it was in an olympiad competition once and nobody solved it). $\endgroup$ – Rand al'Thor May 25 '15 at 16:43
  • $\begingroup$ @randal'thor Though the above proof looks short, it is not, for it takes a long time to prove the ham-sandwich theorem from the ground up. $\endgroup$ – Mike Earnest May 25 '15 at 17:27
  • $\begingroup$ I'm unsure about: "If this plane crosses any bags, move those to the side with fewer bags." Would you mind explaining some more? If the plane crosses a bunch of bags, which sides do you move them to, and how does this guarantee each side still has half of each foodstuff? $\endgroup$ – xnor May 30 '15 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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