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?

  Submitted by yocko    
Rating: 4.4444 (9 votes)
Solution: (Hide)
This problem is best dealt with by working backwards. Start with some minimum number of coconuts, C. If, hypothetically, the pile was only split in the morning, the resulting congruence would be:

C º k mod n

If the pile was split twice...

(n-1/n)(C-k) º k mod n

...and if the pile was split three times...

(n-1/n)((n-1/n)(C-k)-k) º k mod n

Keeping in mind that if there are n men, the pile is split n+1 times (once for each man plus an additional time in the morning), we can follow the pattern beginning to form above (you can write out the congruence for if it's split four or five times if you still can't see it) and then distribute to get:

(n-1/n)nC - k(å{i=1 to n} {(n-1/n)i}) º k mod n

Using the rules for summations and modular arithmetic...

(n-1/n)nC - k(n-1)(1-(n-1/n)n)/(n(1-n-1/n) - k = nx ; x Î Z+

Throw in a healthy dose of algebra...

C = (k+x)nn+1/(n-1)n - k(n-1)

And now the fun part. By assumption, C must be an integer. Since n-1 and n can share no common factors--except when n equals 2, but this case is trivial--and k(n-1) is an integer, C is an integer iff (n-1)n divides k+x.

Define a to be a non-negative integer such that a(n-1)n £ k < (a+1)(n-1)n. Since x must be positive, the smallest possible value for C will occur when k+x = (a+1)(n-1)n. Thus we have:

C = (a+1)nn+1 - k(n-1)

Now, back to that inequality from before. Dividing through by (n-1)n, we get a £ k/(n-1)n < a+1. Since a was defined as an integer, this inequality gives us a = [k/(n-1)n], which yields the final answer of:

C = nn+1 - k(n-1) + nn+1[k/(n-1)n]

Damn the HTML on this solution was a pain...hope you enjoyed. :)

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Re: Official SolutionK Sengupta2008-06-28 17:05:08
Solution (possibly and without help)Cougar Draven2005-06-07 00:42:30
re: mehBractals2005-05-12 22:51:34
mehyocko2005-05-11 21:11:22
Solutionre: ok then...correction...Bractals2005-05-09 15:24:00
ok then...correction...yocko2005-05-09 04:52:25
Some Thoughtsre: close, but not quite...Federico Kereki2005-05-09 03:09:57
close, but not quite...yocko2005-05-09 02:10:29
SolutionSolutionPenny2005-05-08 19:54:43
SolutionNice problemBractals2005-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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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