100 bags of Apples, Beetroots, and Cakes

Question

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.

Answer 1

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.

Answer 2

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.