12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I suspect the presence of Pigeonhole principle... $\endgroup$ – leoll2 May 23 '15 at 14:29
  • 1
    $\begingroup$ @ghosts_in_the_code can you provide a counterexample? $\endgroup$ – leoll2 May 23 '15 at 15:54
  • $\begingroup$ @ghosts_in_the_code By various, I mean each bag can have any number of apples, any number of oranges, making any total. The bags do not need to all have the same number of fruits. $\endgroup$ – Mike Earnest May 23 '15 at 15:58
  • $\begingroup$ Can the bags be empty? $\endgroup$ – Bob May 23 '15 at 16:09
  • $\begingroup$ @Bob Yes, they can be empty. For example, if all bags were empty, then grabbing any $50$ bags works, since zero is at least half of zero. $\endgroup$ – Mike Earnest May 23 '15 at 16:12
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ QED indeed! I will certainly accept your answer, but I think I will wait a bit to see if other cool answers crop up as well. I know there are many distinct proofs methods, yours being the most constructive $\endgroup$ – Mike Earnest May 23 '15 at 21:23
13
$\begingroup$

Arrange the bags in a circle. I will call a collection of 50 consecutive bags a team (so there are 99 possible teams), and a team will be called appley if it contains at least half of the apples.

Define the opponent of a given team to be the team whose rightmost bag is the leftmost bag of the given team. For any given team, every bag is either a member of that team or a member of its opponent (and one bag is a member of both). This means that if a team is not appley, then its opponent is appley. Different teams have different opponents, so there must be at least as many appley teams as non-appley teams. There are 99 teams in total, so at least 50 of them are appley.

A similar argument shows that at least 50 teams are orangey (that is, at least 50 of the teams contain at least half the oranges). Of 99 teams, at least 50 are appley and at least 50 are orangey, so there must be at least one teams which is both appley and orangey (because $50+50>99$). This team consists of 50 bags, and contains at least half the apples and at least half the oranges.

$\endgroup$
  • $\begingroup$ This is really cool! To elaborate: let $A$ be the set of appley teams, and $B$ be the set of teams whose opponents are appley. You showed $A\cup B$ is all $99$ teams (if a team is not appely, its opponent is). Since $|A|=|B|$, we have $99=|A\cup B|\le |A|+|B|=2|A|$, proving $|A|\ge 49.5,$ so $|A|\ge50$. $\endgroup$ – Mike Earnest May 24 '15 at 4:43
  • $\begingroup$ "There are 99 teams in total, ..." - agreed (count possible common bags). You argument seems to put appley teams in 1:1 correspondence with non-appley teams by construction, implying an even total number of teams. How does that correspond with the odd number of teams? Cont'd ... $\endgroup$ – Lawrence May 24 '15 at 13:40
  • $\begingroup$ ... cont'd. Simplified example: instead of 99 bags, say we have 3 bags $a,b,c$. Then we can have team pairs $[ab,bc], [bc,ca], [ca,ab]$. Suppose team $bc$ was appley. This would mean from the first two match-ups that both $ab$ and $ca$ were not appley. However, this makes the last match-up a team pair with two non-appley teams. Is this a failure of the assertion that "if a team is not appley, then its opponent is appley"? (By the way, other than this, I really like your proof. +1 ) $\endgroup$ – Lawrence May 24 '15 at 13:40
  • 1
    $\begingroup$ @Lawrence If a team is non-appley, its opponent is appley. However, if a team is appley, we are not saying its opponent is non-appley (they could both be appley). As you pointed out, since there are an odd number of teams, there must at least one appley team whose opponent is also appley. $\endgroup$ – Julian Rosen May 24 '15 at 13:46
  • 1
    $\begingroup$ @Lawrence no, different teams do have different opponents. Notice, however, that the opponent of the opponent of a team is not (quite) the original team, so you can't "pair them off" in the way you seem to be imagining. $\endgroup$ – Ben Millwood May 26 '15 at 14:35
4
$\begingroup$

Suppose you have 50 bags on the ground and 49 in the truck, and suppose the ones on the ground have more apples. One at a time, take a bag from the ground and put it in the truck, and put one from the truck tand place it on the ground. Keep doing this with the goal of totally swapping ground and truck bags.

Eventually, you'll reach a point where moving a "magic" bag causes the truck to have more apples than the ground. At this point, both the ground plus the magic bag has at least half the apples, AND the truck plus the magic bag has at least half the apples. Either the ground or the truck ( plus the magic bag ) has at least half the oranges too.

$\endgroup$
1
$\begingroup$

I will provide a probabilistic proof. By demonstrating that picking randomly has a nonzero chance of success, we can show that a solution exists. (http://en.m.wikipedia.org/wiki/Probabilistic_method)

Claim: A random subset of 50 bags has over 50% chance of having more than half the apples. (Chosen uniformly over all size 50 subsets.)

Proof: For each "losing" size 50 subset, flip it around to get a (unique) winning size 49 subset. This means there are at least as many size 49 winning sets as size 50 losing sets. There are multiple ways to extend these to size 50 sets, so there's strictly more ways to win than lose. (Hand waving a bit)

This argument applies symmetrically to the oranges. Since each probability is over 1/2, they must have a nonzero intersection.

Thus there is a positive probability of picking a subset with at least half of each, so a solution exists.

Nonconstructively useless, but QED :)

Edit: looking back, this is just saying that the intersection of sets larger than 50% is nonempty, so the probabilistic part is just fluff.

$\endgroup$
  • 1
    $\begingroup$ It's far from trivial that you can extend all 49-subsets of a 99-set into 50-subsets by addition of a single element in such a way that you don't accidentally extend two 49-subsets into the same 50-subset (it's certainly impossible to extend 50-subsets into 51-subsets this way, for example, because there aren't as many of them). $\endgroup$ – Ben Millwood May 26 '15 at 16:26
  • 1
    $\begingroup$ I mean, it IS true. But it requires Hall's Marriage Theorem, unless you have an ingenious construction. $\endgroup$ – Ben Millwood May 26 '15 at 16:29
0
$\begingroup$

Suppose we choose 50 of the bags at random. We are choosing more than half of the bags, so the probability that the bags we selected contain at least half of the apples is strictly greater than 50%. Similarly, the probability that the bags we selected contain at least half of the oranges is also greater than 50%. This means there is a positive probability that the bags we selected contain at least half the apples and at least half the oranges. In particular, there must be some combination of 50 bags containing at least half the apples and at least half the oranges.

Edit: As pointed out in the comments, it is not obvious why the bags we select will have at least half the apples with probability greater than 50%. This actually follows from the argument in my other answer: one way to choose 50 bags at random is first to choose a cyclic ordering of the bags, then to choose 50 consecutive bags. My other answer shows that for whichever cyclic ordering we choose, a random choice of 50 consecutive bags contains at least half the apples with probability at least $\frac{50}{99}$. This means that a random selection of 50 bags contains at least half the apples with probability at least $\frac{50}{99}$. The same is true for oranges, so a random selection of 50 bags contains at least half the apples and at least half the oranges with probability at least $\frac{1}{99}$.

$\endgroup$
  • 1
    $\begingroup$ I think the statement We are choosing more than half of the bags, so the probability that the bags we selected contain at least half of the apples is strictly greater than 50%, needs more justification. $\endgroup$ – Mike Earnest May 23 '15 at 19:44
  • $\begingroup$ This isn't a very rigorous proof. First of all, you must justify your probability statements, then you might provide an algorithm of optimal choosing (not required, but strongly suggested). $\endgroup$ – leoll2 May 23 '15 at 20:52
  • $\begingroup$ I was expecting it to be clear why the probability of getting at least half the apples was bigger than 50%, but I didn't think this part through and I agree that it isn't clear why this is the case. $\endgroup$ – Julian Rosen May 24 '15 at 3:40
  • $\begingroup$ Using the probabilistic approach, leaves a possibility that there will not be a desired solution. We need to have 100% probability that a desired case will be found. $\endgroup$ – Moti May 25 '15 at 17:59
  • $\begingroup$ @Moti If the probability that a random object has a certain property is greater than 0, then it is certain there is at least one object with that property. $\endgroup$ – Julian Rosen May 25 '15 at 18:54

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.