Sunday, December 8, 2019

mathematics - 99 Bags of Apples and Oranges




You have $99$ bags, each containing various numbers of apples and oranges. Prove that there exist $50$ bags among these which together contain at least half the apples and at least half the oranges.



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


Clarification: I changed the wording from "you can grab $50$ bags..." to "there exist $50$ bags..."


Clarification from comments: each bag can contain any number of apples and any number of oranges with any total number of fruit; the total amount of fruit in a bag doesn't have to be the same for each bag.



Answer



Let $B_1,B_2,\dots,B_{99}$ be the bags, in increasing order of number of apples contained; say the number of apples in $B_i$ is $a_i$ for all $i$.


If our 50 bags grabbed are $B_{99}$, one of $B_{98}$ and $B_{97}$, one of $B_{96}$ and $B_{95}$, ..., and one of $B_2$ and $B_1$, then they must contain between them at least half of all apples, since at worst they contain $a_{99}+a_{97}+\dots+a_5+a_3+a_1\geq a_{98}+a_{96}+\dots+a_4+a_2+0$ apples.


Now how do we fix all those "one of"s? Just pick whichever of $B_{98}$ and $B_{97}$ has the more oranges, then whichever of $B_{96}$ and $B_{95}$ has the more oranges, and so on. Then our 50 selected bags - even excluding $B_{99}$! - must contain at least half of all oranges.


QED.



No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...