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

 Monkeys and Coconuts w/unknown variables (Posted on 2005-05-08)
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. :)

 Subject Author Date Re: Official Solution K Sengupta 2008-06-28 17:05:08 Solution (possibly and without help) Cougar Draven 2005-06-07 00:42:30 re: meh Bractals 2005-05-12 22:51:34 meh yocko 2005-05-11 21:11:22 re: ok then...correction... Bractals 2005-05-09 15:24:00 ok then...correction... yocko 2005-05-09 04:52:25 re: close, but not quite... Federico Kereki 2005-05-09 03:09:57 close, but not quite... yocko 2005-05-09 02:10:29 Solution Penny 2005-05-08 19:54:43 Nice problem Bractals 2005-05-08 18:42:48

 Search: Search body:
Forums (0)