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

Home > Numbers
Bananas II (Posted on 2006-11-13) Difficulty: 4 of 5
44 monkeys have a total of 1407 bananas. No two monkeys have the same number of bananas. Show that there is a monkey that has exactly twice as many bananas as another one.

  Submitted by JLo    
Rating: 3.6667 (3 votes)
Solution: (Hide)
This is following Gamer's solution, but it's a bit more formal. Let's call a set of positive integers double-free if it does not contain integers x and 2x at the same time. Now fix an integer m and let S be a minimal double-free set of m numbers. Minimal means that any other double-free set S' of m numbers would have a larger sum of its elements. We show how S can be constructed and that it contains exactly 1408 elements for m=43 (The 44th monkey gets no banana).

Let M be the largest number in S. These two statements are easily proven:

1. Every odd number x<M is in S.
Proof: Say x is not in S. Then 2x must be in S, because otherwise we could replace M by x to obtain a smaller set. But again, if 2x is in S, we can replace 2x by x to obtain a smaller set.

2. If x is in S and if 4x<M, then 4x is in S.
Proof: Say 4x is not in S. We know 2x is not in S, because x is. Therefore, the only reason that could prevent us from replacing M by 4x to obtain a smaller set S', is if 8x is in S. But if 8x is in M, we can replace it by 4x to obtain a smaller set S'.

From these two statements, it follows that our set S must contain all numbers smaller than M of the following sets:
S_0 = {1, 3, 5, 7, 9, 11...} = { x | x odd}
S_1 = {4, 12, 20, 28, 36...} = { 4x | x odd}
S_2 = {16, 48, 80, 112...} = {16x | x odd}
generally S_i = {4^i x | x odd}

Can S contain any other number? Such a number would be of the form 2*4^k*x, with odd x. But then 4^k*x could not be in S, contradictory to what we have just shown. I.e. the set S is in fact exactly the union of all numbers in S_i which are smaller than M. Therefore, to construct a minimal set S, we simply collect the smallest m numbers in the union of S_0, S_1, S_2,... When doing so, we obtain the following sequence:

1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19...

The sum of the first 43 integers is in fact 1408.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re: Solution by groupingbrianjn2006-11-14 02:26:00
re(3): Solution, sort of...brianjn2006-11-14 01:14:03
re: Solution by grouping (include zero)Gamer2006-11-14 00:55:45
SolutionSolution by groupingGamer2006-11-14 00:52:50
re(3): Solution, sort of...Gamer2006-11-14 00:03:00
Hints/Tipsre(2): Solution, sort of...tomarken2006-11-13 20:44:00
re: Solution, sort of...brianjn2006-11-13 19:50:10
SolutionSolution, sort of...tomarken2006-11-13 12:13:30
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 (8)
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