All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Bananas III (Posted on 2006-12-22) Difficulty: 3 of 5
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.

See The Solution Submitted by JLo    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Separating the monkeys | Comment 1 of 4

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information