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

Home > Numbers
Monkeys and Coconuts w/unknown variables (Posted on 2005-05-08) Difficulty: 3 of 5
This is a variation on a classic number theory problem, originally submitted by Ravi Raja here.

There are n men and k monkeys shipwrecked on an island. The men have collected a pile of coconuts which they plan to divide equally among themselves the next morning. Not trusting the rest of the group, one of the men wakes up during the night and divides the coconuts into n equal parts leaving k left over, which he gives to the monkeys. He then hides his portion of the pile. During the night, each of the other men does exactly the same thing by dividing the pile he finds into n equal parts leaving k coconuts for the monkeys and hiding his portion. In the morning, the men gather and split the remaining pile of coconuts into n parts and k is left over for the monkeys. What is the minimum number of coconuts, C, the men could have collected for their original pile?

See The Solution Submitted by yocko    
Rating: 4.4444 (9 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Nice problem | Comment 1 of 10
 
Let C_p be the number of coconuts in the pile.
We have the difference equation C_(p+1) = (n-1)*(C_p - k)/n.
This gives the closed form
C_p = { C_0*(n-1)^p - (n-1)*[n^p - (n-1)^p]*k }/n^p,
where C_0 is the number of coconuts in the starting pile.
Since we perform the operation for each man and once in the morning,
C_n = q*n + k, for some integer q. 
This gives the Diophantine equation in q and C_0:
C_0*(n-1)^n - q*n^(n+1) = k*[n^(n+1) - (n-1)^(n+1)].
Which has the following solutions:
C_0 = m*n^(n+1) - k*(n-1) and q = m*(n-1)^n - k,
for any integer m.
Since C_0 is to be minimized and q must be greater than zero,
n = 2   ==>  C_0 = 15
n > 2   ==>  C_0 = n^(n+1) - k*(n-1).
 

  Posted by Bractals on 2005-05-08 18:42:48
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 (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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