Monkeys and Coconuts w/unknown variables (Posted on 2005-05-08)

	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