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.

Let's have a non-decreasing set (S) of integers 1, a(2), a(3) ... a(n) so that a(k)<=2*a(k-1). Then it's easy to prove that any positive integer N<2*a(n) can be represented as a sum of a subset (S1) of S. Let's say N is between two elements: a(k)>N>=a(k-1). Since 2*a(k-1)>=a(k) then 2*a(k-1)>N>=a(k-1) then  a(k-1)>N-a(k-1)>=0.  a(k-1) is the largest  element of S1. We repeat the same for N-a(k-1) to find the next element and continue until we get 0.

Edited on December 23, 2006, 8:28 pm

Posted by Art M on 2006-12-23 03:57:36