Monkeys And Coconuts
May 8, 2015
We have today a famous puzzle:
Five sailors are shipwrecked on a desert island. They quickly determine that the only other inhabitant of the island is a monkey and that the only food is coconuts. They set about collecting as many coconuts as they can and put them all in a pile. By nightfall they are too tired to divide the harvest; so they agree to go to sleep and divvy up the coconuts the next morning.
During the night one sailor awakens, suspicious that the others might try to cheat him, and desides to take his portion then and there and not wait until morning. He divides the coconuts into five piles and finds there is one coconut left over, which he gives to the monkey. He hides one of the five piles, then puts the rest of the nuts together and returns to sleep. About an hour later a second sailor awakens with the same suspicions and does the same thing: He divides the coconuts into five piles, leaving one extra, which he gives to the monkey. Then he hides what he thinks is his share and goes back to sleep.
One after another the rest of the sailors do the same: they each take one fifth of the coconuts in the pile (after giving the extra one to the monkey) and then return to sleep.
When the sailors awaken the next morning they all notice the coconut pile is much smaller than it was the night before, but since each man is as guilty as the others, no one says anything. They divide the coconuts (for the sixth time), but this time there is no coconut left for the monkey.
How many coconuts were in the original pile?
Your task is to determine how many coconuts were in the original pile; first solve the problem for 5 sailors, then again for 6 sailors, and finally for 30 sailors. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Bruteforce in Python..
With all the stealing, better call them pirates..
3 25
4 765
5 3121
6 233275
7 823537
8 117440505
9 387420481
..
This site interests me. Are you collecting answers to problems? Can a robot solve these problems?
I am very put off by the way the questions are worded – “your task is to …”. It reminds me of lunatics who write on a blog demanding that people sent them answers to problems.
You can solve the difference equation and apply a divisibility condition to get a formula for the least number of coconuts:
We start with C coconuts and N sailors.
Let C_0 = C be the initial number of coconuts.
From the problem’s description, C_n = (C_n – 1) * (N – 1) / N, and this is a positive integer.
The final condition is that N | C_N.
The solution to the difference equation is C_n = (C+N-1)((N-1)/N)^N + 1 – N.
Since C_n needs to be an integer for each n, and hcf(N-1,N) = 1, we need N^n | (C+N-1), hence N^N | (C+N-1).
Rewrite to C+N-1 = kN^N for some integer k.
The final condition means that N | k(N-1)^N +1 – N.
Rewriting again, k(N-1)^N +1 -N ≡ 0 (mod N)
so k ≡ (-1)^(N-1) (mod N)
Choosing k to minimise C, then, k = 1 if N is odd, and N-1 if N is even.
So C = N^N -N +1 if N is odd, (N-1)N^N -N +1 if N is even.
I get 5.970842831×10^45 on my calculator for 30 sailors. Which is a lot of coconuts! But the monkey only gets 30 of them.
@namako – Nice.
I started with the number of coconuts in the morning (base) and worked backwards to see how many would be in the original pile (pile).
We know that base is divisible by the number of sailors (nsailors). We also know that it is divisible by nsailors-1, because the last sailor pile*(nsailors-1)/nsailors after he took his cut. So, base is a multiple of nsailors*(nsailors – 1).
To find the size of the pile before the sailor gave one to the monkey and took a cut: pile = pile * (nsailors) // (nsailors – 1) + 1. Each time, the pile must be divisible by nsailors – 1. If not, increase base and try again. Each time, I printed the base number of coconuts and the number of sailors before the test failed. Observing patterns in the printout, I figured out how to increase the step size fairly rapidly.
def how_many_coconuts(nsailors=5): seen = [None]*nsailors base = nsailors*(nsailors - 1) seen[0] = base step = base best = 0 while True: pile = base #print('\n', pile, end=' ') for sailor in range(nsailors): pile = pile * nsailors // (nsailors - 1) + 1 # note: // is integer division if pile % (nsailors - 1): #print(sailor, end=' ') if sailor > best: if seen[sailor]: step = base - seen[sailor] best = sailor #print(step, '<- new step', end=' ') else: seen[sailor] = base #print('<- first seen', end=' ') break else: return pile base += step print(how_many_coconuts(6))Another approach: we can find a Diophantine equation of the form Ax = By + C where x is the initial number of coconuts, and y is the number of coconuts given to each pirate at the end, and A, B and C are some constants depending on the number of pirates. So for 5 pirates we have 1024x = 15625y + 8404. We can solve such equations in a standard way using the extended Euclidean algorithm:
def egcd (a,b): x,y,z,w = 1,0,0,1 while b != 0: q,r = divmod(a,b) a,b = b,r x,y,z,w = z,w,x-q*z,y-q*w return a,x,y def monkey(n): A,B,C,m = 1,n,0,n-1 for i in range(n): # Ax = By + C where: # x is number of coconuts when i pirates are yet to chose A,B,C = m*A,n*B,n*C+m*A return A,B,C for n in range(1,31): A,B,C = monkey(n) # For A,B find Ax + By = d = gcd(A,B) (d,x,y) = egcd(A,B) assert(d == 1) # A and B are co-prime # Cx + kB is general solution, find smallest positive print(n,C*x%B)Rutgers solution is bad, only the first result is good:
java:
public int calcNumberOfCoconutsFor(int sailors) {
for (int i = sailors; i < 240000; i++) {
System.out.println(“current number: ” + i);
int remaining = i;
int withoutMonkeyShare = remaining – 1;
for (int j = 0; j < 5; j++) {
if (withoutMonkeyShare % sailors == 0) {
int oneOfFullPart = withoutMonkeyShare – withoutMonkeyShare / sailors;
if (((oneOfFullPart / (sailors – 1)) * sailors) % sailors == 0) {
remaining = oneOfFullPart;
withoutMonkeyShare = remaining – 1;
System.out.println(“remaining number: ” + remaining);
if (j == 4 && remaining % sailors == 0) {
return i;
}
}
}
}
}
return 0;
}
results:
5 – 3121
6 – 7771
7 – 16801