22 monkeys have together 8888 bananas. For each monkey with more than one banana, there is another monkey with fewer, but at least half as many bananas. Prove that the monkeys can be split in two groups with 4444 bananas each.

In every case, there must be a monkey with 1 banana since it doesn't require a monkey with fewer bananas.

Assume set M of monkeys starts out with that monkey, with T the total number of bananas of all monkeys in the set. A prospective monkey with Y bananas can be added if X<Y<=2X, for some monkey in the set with X bananas. (Thus, every monkey in set M will follow the problem's condition as well.)

This means we can add all 21 other monkeys to the set if they are added them from fewest to greatest since every monkey follows the problem's condition.

First we can conclude inductively that Y<=T+1 for each prospective Y.

For the basis case, the first added monkey must have 2 bananas, and 2<=1+1. To prove the inductive step, say the last monkey added has Y bananas, the prospective monkey has Z bananas, and the total before adding monkey Y is T. From the inductive assumption, 2Y<=T+1+Y, (where T is the total before Y was added) and since Z can be added, Z<=2X<=2Y thus Z<=T+1+Y.

Because of this fact, every number from 1 to T in M can be comprised by selecting monkeys in M and this can also be proven inductively.

The initial M of size 1 can make sizes 0 and 1. By the inductive assumption, all values from 0 to T can be made. All values from Y to Y+T can by adding Y to another number from 0 to T, since Y<=T+1. 

Since adding a valid monkey maintains that assumption, after all monkeys are added in M, you can split the monkeys into two groups with the desired number of bananas in each group, including having 4444 in each group.

Posted by Gamer on 2006-12-22 16:09:58