|
We prove the following statement which is slightly stronger and slightly more general:
Let a1=1,a2,a3,.. be a sequence of positive integers such that an<=a<=2a for all n. Then for each n, every integer between 1 and a1+..+an can be represented as the sum of some ai's (with one or more summands) with 1<=i<=n whereby each a shows up at most once in the sum.
For our monkey problem, we can disregard all monkeys without bananas because they can be assigned to either group. If we sort the other monkeys by number of bananas, we get an integer sequence as described above. Therefore, for each number between 1 and 8888 there is a group of monkeys having this exact amount. For the monkey problem, we simply chose the number 4444.
Proof: First we show that for each n
(1) an+1<=1+a+..+an
This is obvious for n=0 (because a1=1<=1) and n=1 (because a<=2a=2=1+a1) For n=2,3.. it follows per induction because
an+2<=2a<=a+1+a1+..+an
We do the main proof also by induction over n. It is clear for n=1. Now assume it is true for some n. Then S1:={1,..,a1+..+an} is the set of all sums of a1,..,an. By adding an+1 to all those sums, we can obtain the sums S2:={1+an+1,..,a1+..+an+an+1}. Because of (1), the only "gap" between the largest member of S1 and the smallest member of S2 is an+1. But an+1 itself is a one-summand sum and therefore fills this gap.
|
