Here is another puzzle we have received and answered many times. (I count 7 that have been archived.) It has several variations, which make it even more interesting. The story varies, too; sometimes the monkeys are the stars, other times they just get the leftovers. Someone could to an interesting folklore study on this one.
Version 1: Long algebraic solution
Here is the first version we got, from a 4th grader in 1997:
Coconut and Monkey Puzzle Please help me solve this puzzle. "Five men were stranded on an island. They went around picking up coconuts for years. One day, they saw a ship coming. They had a radio so they sent a message to come and pick them up. The ship said "yes, tomorrow morning!" The five men went to sleep but the first man woke up and thought "I don't trust my buddies," so he took 1/5 of the pile of coconuts. Then a monkey came down and took 1 coconut. The second man woke up and didn't trust his buddies either, so he took 1/5 of the remaining pile of coconuts. The monkey came down again and took 1 coconut. During the rest of the night, the third, fourth, and fifth men did the same and the monkey took 1 coconut after each man. In the morning, the five men tried to divide the remaining pile of coconuts into five equal portions but had one left over, which they gave to the monkey. How many coconuts were in the original pile?
This is a classic problem; according to Wikipedia, it originated in a form similar to this one in 1926. There are a couple subtle differences, however, which we’ll see later. One defect in this version is that it implies there is only one answer; any correct statement of such a problem will ask for the smallest possible solution.
Doctor Rob answered this one:
This problem, or variants of it, have been around for a long time. This is how you solve it. Let a be the number of coconuts to start with. After the first man and the monkey took their coconuts, the number left was b = (4/5)*a - 1. After the second man and the monkey took their coconuts, the number left was c = (4/5)*b - 1. The third man left d = (4/5)*c - 1 coconuts. The fourth man left e = (4/5)*d - 1 coconuts. The fifth man left f = (4/5)*e - 1 coconuts. At the end, f = 5*g + 1, where g is the number of coconuts each man got in the morning.
After a bit of work substituting each equation in the previous one (which I’ll let you look at in the original), he arrives at this linear Diophantine equation:
1024*a - 15625*g = 13630. Any positive whole numbers a and g which are a solution of this equation will give you a solution to your original problem. The problem has been reduced to finding the value of a.
He then divides successively by 5 and powers of 2, introducing a new integer variable at each step, to arrive at:
h - 3125*r = 2499. One solution to this is r = 0, h = 2499. There are other, larger ones, such as r = 1, h = 5624, and r = 100, h = 314999, but we will stick with the smallest one. The general solution is h = 2499 + 3125*r, r any nonnegative whole number. Backtracking, we get q = 1, p = 3, n = 12, m = 25, k = 51, j = 204, i = 409, h = 2499, g = 818, f = 4091, e = 5115, d = 6395, c = 7995, b = 9995, and a = 12495. Sure enough, 1024*12495 - 15625*818 = 13630.
So we’ve solved the equation, and found that the smallest possible original pile was 12,495 coconuts.
Does this work? Let's check. Starting with 12495: The first man took 2499 coconuts, and the monkey took 1. This left 12495 - 2500 = 9995 coconuts. The second man took 1999 coconuts, and the monkey took 1. This left 9995 - 2000 = 7995 coconuts. The third man took 1599 coconuts, and the monkey took 1. This left 7995 - 1600 = 6395 coconuts. The fourth man took 1279 coconuts and the monkey took 1. This left 6395 - 1280 = 5115 coconuts. The fifth man took 1023 coconuts and the monkey took 1 This left 5115 - 1024 = 4091 coconuts. In the morning, each man got 818 coconuts and the monkey 1 more. It checks! Hooray! If we backtrack using h = 2499 + 3125*r, we will find that the general answer is a = 12495 + 15625*r coconuts, for any nonnegative whole number r. The men must have done a whole lot of counting in the middle of the night!
This would be a lot of work for a fourth grader, too.
Version 2: The standard problem, sorta
Now, in 1998 we got a different version of the puzzle, still with five people and a monkey:
Coconut Piles Here's the problem: Gilligan and his buddies were stranded on a desert island. Gilligan, the professor, Ginger, Mary Anne, the Skipper, and Fred the monkey were gathering coconuts. One evening they all rounded up all the coconuts they could find and put them in one large pile. Being exhausted from working so hard they decided to wait and divide them up evenly in the morning. During the night Gilligan awoke and separated the nuts into five equal piles, with one left over which he gave to Fred the monkey. Gilligan took one pile, hid it, pushed the other four back together, and went back to his hut. He was followed by Ginger, Mary Ann, the Professor, and the Skipper, each dividing them up equally with one remaining nut going to Fred. The next morning the remaining nuts were divided up equally with one remaining going to Fred. What is the least number of coconuts they could have started with?
Do you see the difference? The final division is the same (the one taken by the monkey being a remainder from the division), but the first five here have every step working that way, while the first version had the monkey take one after an even division. (It’s possible that that was a mistake in the wording.)
This version is equivalent to the original from which the 1926 form was derived.
Doctor Rob took this question, too, and after referring to the first one, said:
The difference is that in this problem, the monkey gets his coconut before the five-way split, and in the problem on the other Web page, he gets it after. Subtle, but important. The equations for your problem are these. Let a be the number of coconuts to start with. After the first person and the monkey take their coconuts, the number left is b = (4/5)*(a-1). After the second person and the monkey take their coconuts, the number left is c = (4/5)*(b-1). The third person leaves d = (4/5)*(c-1) coconuts. The fourth person leaves e = (4/5)*(d-1) coconuts. The fifth person leaves f = (4/5)*(e-1) coconuts. At the end, f = 5*g + 1, where g is the number of coconuts each person gets in the morning.
He does not go through all the details of solving this new system of equations in separate steps, but does all the substitutions at once, and leaves us to simplify it:
Now when you perform the chain substitution to find the equation relating a and g, you get:
4*(4*[4*(4*[4*(a-1)/5-1]/5-1)/5-1]/5-1)/5 = 5*g + 1
1024*a - 15625*g = 11529
I’ll let you check that he got that right. He leaves Fallon to carry out the same procedure as before, and find the actual solution.
He also suggests a more standard way to solve the equation:
There is another way, using the Extended Euclidean Algorithm. You can use that to find that: 1024*10849 - 15625*711 = 1 Now multiply by 11529, and reduce the a-value modulo 15625 to get the answer.
Version 3: A virtual solution
In 2001, Doctor Rob answered another question equivalent to the last one except that there are seven monkeys doing the division. For the sake of space, I’ll jump to his answer:
Monkeys, Coconuts, and Seven Piles ... The equations you have to solve are a = starting amt of coconuts b = (6/7)*(a-1) = amt after 1 monkey, c = (6/7)*(b-1) = amt after 2 monkeys, d = (6/7)*(c-1) = amt after 3 monkeys, e = (6/7)*(d-1) = amt after 4 monkeys, f = (6/7)*(e-1) = amt after 5 monkeys, g = (6/7)*(f-1) = amt after 6 monkeys, h = (6/7)*(g-1) = amt after 7 monkeys, i = (1/7)*(h-1) = amt each got at the end. Clearing fractions, these become 6*a - 7*b = 6, 6*b - 7*c = 6, 6*c - 7*d = 6, 6*d - 7*e = 6, 6*e - 7*f = 6, 6*f - 7*g = 6, 6*g - 7*h = 6, h - 7*i = 1.
Watch the next step:
Eliminating in turn b, c, d, e, f, g, and h, these equations give, in turn, 6^1*a - 7^1*b = 6*(7^1 - 6^1), 6^2*a - 7^2*c = 6*(7^2 - 6^2), 6^3*a - 7^3*d = 6*(7^3 - 6^3), 6^4*a - 7^4*e = 6*(7^4 - 6^4), 6^5*a - 7^5*f = 6*(7^5 - 6^5), 6^6*a - 7^6*g = 6*(7^6 - 6^6), 6^7*a - 7^7*h = 6*(7^7 - 6^7), 6^7*a - 7^8*i = 7^8 - 6^8.
It’s not immediately obvious, but by constantly clearing fractions, and writing everything as powers rather than calculating actual values, he has made an ugly thing almost beautiful. In an even simpler solution below, we’ll be seeing equations much like these.
This last equation has a particular solution a = -6 and i = -1. (Check to make sure you see why this works.) The general solution is given by a = -6 + 7^8*t, i = -1 + 6^7*t, where t can be any integer. Putting t = 1 gives you the smallest possible positive answer for a and i. I leave it to you to find the number of coconuts each monkey got.
It is easy to find this solution with negative numbers; what isn’t obvious (unless you’ve done enough work with Diophantine equations) is to think of doing so at all, when the problem assumes positive numbers.
So the pile started with a = 5,764,795 coconuts, and each got i = 279,935 in the final division.
Notice the really nice "virtual solution" starting with a = -6 coconuts: a = b = c = d = e = f = g = h = -6, i = -1, each monkey ends up with -2 coconuts, and 8 end up in the ocean!
Give that some thought!
Version 4: Three monkeys, and number theory
Earlier in 1998, we had received a different version. The wording is very different, with monkeys taking the place of people; but the only real differences are that we have 3 rather than 5, and that there is no final division. The question at the end is different, too.
Monkeys Dividing the Coconut Pile This is a problem I could not solve. Please help me out. Three monkeys spend a day gathering coconuts together. When they have finished, they are very tired and fall asleep. The following morning the first monkey wakes up. Not wishing to disturb his friends, he decides to divide the coconuts into 3 equal piles, but there is one left over, so he throws this odd one away, helps himself to his share, and goes home. A few minutes later the second monkey awakes. Not realizing that the first has already gone, he too divides the coconuts into 3 equal heaps, finds one left over, throws the odd one away, helps himself to his fair share, and goes home. Then the third monkey does exactly the same. What is the smallest possible number of coconuts left?"
Doctor Anthony answered:
If N = original number of coconuts, then the first monkey takes (N-1)/3 as his share, leaving 2(N-1)/3 behind. Then the second monkey takes:
2(N-1)/3 - 1 2(N-1) 1
------------ = ------ - ---
3 9 3
leaving behind:
4(N-1) 2
------ - ---
9 3
The third monkey takes:
4(N-1)/9 - 2/3 - 1 4(N-1) 5
------------------- = ------ - ---
3 27 9
leaving:
8(N-1) 10 8(N-1) - 30
------ - --- = -------------
27 9 27
Here, we assume that the third monkey does not just grab everything left after the other two have gone.
(Yes, since the others have left, we lack the motivation present in other versions!)
We now have an expression for the final amount.
After more work with fractions, he obtains a Diophantine equation as before, and because the numbers are smaller, he suggests just trying numbers.
You’ll see in a moment why I am skipping over all the details.
Version 5: Modular arithmetic
In subsequent years, Doctor Anthony answered many questions of this type, but in a very different way; these answers were never archived. Here is one that should have been, from 2008:
You posted a solution for the three monkeys and the coconuts, subject "Monkey Problem." I wanted to expand that to five monkeys and could not seem to come up with a solution. Can you please shed some light onto it? Here's the three monkey problem and your solution: Monkeys Dividing the Coconut Pile
As this referred to his answer, Doctor Anthony responded to it, by replacing that method with one that is far quicker. He did this for the standard problem, with 5 sailors and a final division:
The solution that I gave 07/29/98 is far too long-winded and I would certainly not use the same method again. It is best to use modular arithmetic and solve the problem in a couple of lines. The normal setting would have 5 sailors on a desert island who collect a pile of coconuts and then go to sleep. During the night the sailors wake up in turn and each divides the pile into 5 taking one portion and in each case have 1 left over which they give to a local monkey. In the morning there are still some coconuts left which they divide again for the last time into 5 and again have 1 left over for the monkey. What is the least number of coconuts in the original pile for this situation to be possible?
Here is the entire solution:
We will divide by 5 a total of 6 times altogether counting the last division in the morning.
Let x = number of coconuts in the original pile
Each division must leave the number of nuts in the same congruence class (mod 5).
So x = (4/5)(x-1) (mod 5) (the -1 is because of the monkey)
5x = 4x - 4 (mod 5)
x = -4 (mod 5)
So if we began in the modulo class -4 nuts then we will remain in the modulo class -4. Since ultimately we have to divide by 5^6 we begin with 5^6 - 4 = 15621 coconuts.
So the original pile had 15621 coconuts.
Let’s think through that!
When he talks about a congruence class, he simply means that the result at each step leaves the same remainder, namely 1; so the number at the start and end of each step must differ by a multiple of 5. At each step, if we start with x, we end up with \(\frac{4}{5}(x-1)\). So the difference of these must be a multiple of 5, which I’ll write as 5k (for some integer k): $$x – \frac{4}{5}(x-1) = 5k$$
Multiplying by 5, $$5x – 4(x-1) = 25k$$ $$x + 4 = 25k$$ $$x = 25k – 4$$
This shows that x must be 4 less than a multiple of 25 [not 5 …].
The rest is hand-waving; I’m not actually sure whether there are sound reasons for ultimately saying that, in order to pass through 6 steps of division, the original number has to be congruent to \(-4 (\!\mod 5^6)\); but even if we just have a feeling that this will work, we can check it! He finished up by doing so, which justifies the answer.
Version 6: A simple trick
Back in 1999 we got the following question, which contained a hint that turns out to be lead to a more elementary version of Doctor Anthony’s method:
More Monkeys and Nuts I have looked through your archive and found a couple of variants on the monkeys sharing nuts theme. None is specifically the same as the problem I have (I don't think) although it is very similar to one that is answered at some length with formulae and substitution, etc. The person who set me this puzzle suggested that it was possible to deduce the answer without going to this trouble, and gave me a clue which I will add at the end of the puzzle. The puzzle: Five monkeys collect nuts, which they leave in a pile. During the night one wakes up and divides the pile into 5. There is one left over. He eats the remainder nut and his 1/5 share, and mixes the nuts together. The second monkey comes down, divides the pile into 5 with one left over, and so it goes on; each left pile divides into 5 with one left over and each monkey eats its share plus one. The question is, what is the least number of nuts that they had amassed in order for this to work? The clue: Apparently, by asking what would have happened if there were 4 more nuts collected, the answer can be found without lengthy calculations - in fact I am told of somebody who solved it in his head over lunch given this advice. I have played around with the idea at length but have grown frustrated, as I have not yet solved the problem. What do you think? Thanks for your help; I look forward to hearing from you.
This is like the classic version, except that it lacks the final division.
I had no special knowledge of the problem, but I had fun figuring out the clue:
Hi, Michael. I've been playing with this off and on for a few days, and getting confused because of the variations among versions of the puzzles! My biggest frustration has been trying to make my answer agree with one of the others. Yes, this clue does help, at least with your version of the puzzle.
I began by setting the stage for the usual procedures:
Let's suppose that the initial number of nuts is X_0. I divide the pile by five and have one left over, so each pile is (X_0-1)/5, and the number I leave is
X_1 = (X_0 - 1) * 4/5
The same process is repeated five times until I have a fairly complicated expression for X_5, the number left at the end.
Can we avoid the big equation?
Suppose we set 4 nuts next to the pile and don't touch them through the whole process (so they AREN'T part of the dividing by five - although that's not quite how you described the hint). The total number of nuts is
Y_0 = X_0 + 4
Y_1 = X_1 + 4
= (X_0 - 1) * 4/5 + 4
= (Y_0 - 4 - 1) * 4/5 + 4
= (Y_0 - 5) * 4/5 + 4
= Y_0 * 4/5 - 4 + 4
= Y_0 * 4/5
So at each step, the total number of nuts is just multiplied by 4/5, and we can easily see that
Y_5 = Y_0 * (4/5)^5
For this to be a whole number, Y_0 must be a multiple of 5^5, and the smallest possible value would be exactly that, or 3125. Then X_0 is four less than this, or 3121.
Do you see that this is essentially the same as Doctor Anthony’s answer, and is easily justified? We can even see that the 4 we added corresponds to his -4: It’s the amount that brings the total up to a multiple of 4. As he had said, the number at every step is congruent to -4, mod 5.
As always, we have to check:
Now let's try it out:
X_0 = 3121
X_1 = (3121 - 1) * 4/5 = 2496
X_2 = (2496 - 1) * 4/5 = 1996
X_3 = (1996 - 1) * 4/5 = 1596
X_4 = (1596 - 1) * 4/5 = 1276
X_5 = (1276 - 1) * 4/5 = 1020
This final number, of course, is 4^5 - 4.
I went on to show that if we modify this to include the sixth round of division in Version 2 above, we get an answer (starting number 15,621, each gets 4092) that satisfies the equation given there.
How would you invent the hint? I gave some suggestions:
The trick amounts to a change of variables that simplifies the equation. To find such a change, you could try Y = X + a, and see what value of a will help:
X_1 = (X_0 - 1) * 4/5
Y_1 - a = (Y_0 - a - 1) * 4/5
Y_1 = Y_0 * 4/5 + a - (a + 1)*4/5
To make the equation simpler, we want
a - (a + 1)*4/5 = 0
5a = 4(a + 1)
a = 4
Or, you can just have a flash of insight and try adding four nuts for no reason at all.
This amounts to Doctor Anthony’s reasoning. Or you could just observe that each division leaves a remainder of 1, so the numbers are obviously all congruent to 1, and therefore to -4 (which differs from it by 5). Therefore adding 4 nuts at every stage will result in a multiple of 5.
I think we have a winner!
A couple variants
Our archives also contain a couple more modified forms of the problem; I’ll just give you the links.
First, from 2004, one that is not looking for the smallest starting number:
The Sailor's Reward Problem and Prime Numbers
Next, from 2010, one that gives the final number, so it is just a matter of working backwards:
Coconuts, Forwards and Backwards
So many puzzles, so little time!