“The Coconut Problem”; Updated With Solution

This is a famous old problem. I shall just state the problem here for you, and will follow up in a day or two with a solution and some of its amusing history. Update: Scroll down for a straightforward solution and a “trick” solution.

There are also, by now, various generalizations and different versions. Here’s a basic version:

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 very large pile. By nightfall they are too tired to divide the harvest; so they agree to go to sleep and share the coconuts equally the next morning.

During the night one sailor awakens, suspicious that the others might try to cheat him, and decides 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 coconuts back into a pile and returns to sleep. 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, puts the remaining coconuts into a pile and goes back to sleep.

One after the other, the rest of the sailors do the same: They each take one fifth of the coconuts in the pile (there is always an extra one, which is given 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) and again there is one left for the monkey.

How many coconuts were in the original pile?

If you’re interested, give it a good try, and resist the temptation to scour the internet for the solution.

Update: Here is a solution to the problem and a few comments.

Let x represent the number of coconuts in the original pile, and let y represent the number of coconuts that each sailor takes away in the morning.

Now, consider how many coconuts remain in the pile after the first sailor secretly takes a portion away to hide in the night. He tosses one coconut to the monkey, then takes a fifth of the rest, so the number of coconuts remaining in the pile is

\dfrac{4}{5} ( x - 1)

Using the same reasoning, the number of coconuts that remains in the pile after the second sailor secretly removes some coconuts in the night is

\dfrac{4}{5} \left [ \dfrac{4}{5} ( x - 1) - 1 \right ]

Repeating the same argument three more times, the number of coconuts left in the pile in the morning, before the final sharing, is

\dfrac{4}{5} \left [ \dfrac{4}{5} \left ( \dfrac{4}{5} \left \{ \dfrac{4}{5} \left [ \dfrac{4}{5} ( x - 1) - 1 \right ] -1 \right \} - 1 \right ) - 1 \right ]

In the morning, one coconut gets thrown to the monkey, and the remaining coconuts are shared equally five ways. Thus, each sailor receives (besides the ones taken in the night) an additional y coconuts, where

y = \dfrac{1}{5} \left \{ \dfrac{4}{5} \left [ \dfrac{4}{5} \left ( \dfrac{4}{5} \left \{ \dfrac{4}{5} \left [ \dfrac{4}{5} ( x - 1) - 1 \right ] -1 \right \} - 1 \right ) - 1 \right ] - 1 \right \}

So, we end up with one equation for two unknowns, which seems not to be solvable. Or rather, there are an infinite number of solutions, about which it seems that no more can be said. However, we have one additional piece of information that has not been used yet: The values of x and y must be whole numbers. That is, the number of coconuts in the pile, and the number taken at any stage, is assumed to be a whole number.

This is part of the reason that mathematics problems are difficult. There are tacit assumptions that one must identify and then translate into mathematical language.

Equations such as the one under consideration are called Diophantine equations, and were studied in antiquity.

I first learned about this problem from a colleague about 25 years ago, when he gave it to me as a challenge. A few years ago I bought the wonderful Martin Gardner book entitled The Colossal Book of Mathematics, and I was delighted to see this problem was the subject of his very first item. He mentions that the problem was first published as part of a short story in the 9 October 1926 issue of The Saturday Evening Post, written by Ben Ames Williams. The offices of the periodical were inundated by 2000 pieces of mail in the first week alone, prompting the editor to send a famous telegram to the author, which read

For the love of Mike, how many coconuts? Hell popping around here.

Gardner goes on to say that the author continued to receive letters about the problem for more than twenty years!

Gardner boils down the last equation above to

1,024x = 15,625y + 11,529

and goes on to say that the equation is far too difficult to solve unless a clever trick is used. But there is a nice way to solve the equation, which I will now show you. Expand the equation to get

y = \dfrac{4^5}{5^6} x - \dfrac{4^5}{5^6} - \dfrac{4^4}{5^5} - \dfrac{4^3}{5^4} - \dfrac{4^2}{5^3} - \dfrac{4}{5^2} - \dfrac{1}{5}

y = \dfrac{4^5}{5^6} x - \dfrac{1}{5} \left [ \left ( \dfrac{4}{5} \right )^5 + \left ( \dfrac{4}{5} \right )^4 + \left ( \dfrac{4}{5} \right )^3 + \left ( \dfrac{4}{5} \right )^2 + \left ( \dfrac{4}{5} \right ) + 1\right ]

Notice that the quantity in square brackets is a geometric series, and can be expressed in a compact and useful form using the results of my previous post. The result is

y = \dfrac{4^5}{5^6} x - \dfrac{1}{5} \left [ \dfrac{1 - \left ( \dfrac{4}{5} \right )^6}{1 - \dfrac{4}{5}} \right ]

A little algebraic manipulation, including clearing the fractions, will be helpful:

y = \dfrac{4^5}{5^6} x - \left [ 1 - \left ( \dfrac{4}{5} \right )^6 \right ]

y = \dfrac{4^5}{5^6} x - 1 + \dfrac{4^6}{5^6}

5^6(y + 1) = 4^5 x + 4^6

5^6(y + 1) = 4^5(x + 4)

OK, this looks a lot simpler, but it still may not be clear how to make progress. But remember, x and y must be whole numbers. This means that each side of the previous equation is a whole number. How can the two whole numbers represented by each side of the equation possibly be equal? There are six factors of 5 on the left side of the equation, but where are they on the right? The only way this will work is that

(x + 4) must be a multiple of 5^6.

And this solves the problem. There are indeed an infinite number of solutions, but we now know all of them. The smallest solution is

x = 5^6 - 4

the next largest is

x = 2(5^6) - 4

and so on. For each value of x, the corresponding value of y is obtained by solving the equation

5^6(y + 1) = 4^5(x + 4)

An alternative “trick” solution

Gardner’s solution involves the following trick. Notice that if it were possible to find one solution, all other solutions would differ from it by a multiple of 5^6. Then (and this is the genius part), notice that x = -4 is a solution. What?? A negative number of coconuts??

I don’t think I would ever have noticed this, but once you have been told it, and with the benefit of our equation

5^6(y + 1) = 4^5(x + 4)

it’s clear that x = -4 and y = -1 makes both sides of the equation 0. Does this make sense? Sort of: If there are -4 coconuts in the original pile, and one is thrown to the monkey, leaving -5 in the pile, then when a sailor takes one-fifth of the coconuts (that would be -1 coconuts), then -4 coconuts remain. Each of the sailors do this in turn, and in the morning the sailors are confronted with a pile of -4 coconuts, and after they toss one to the monkey, they can evenly divide the pile by taking -1 coconut each.

But in certain problems a standard idea is to look for “fixed-point” solutions. If we were to do this here (that is, imagine a number of initial coconuts such that after the first sailor’s withdraw yields the same number of coconuts in the pile) we would be led to the equation

x = \dfrac{4}{5}(x - 1)

the solution of which is

5x = 4x - 4

x = -4

So does it require genius or not? I don’t know.

In any case, legend had it that Dirac was the one who thought up this delightful trick, so Gardner wrote to Dirac to inquire whether this was the case. He said that he heard the negative solution from the mathematician J.H.C. Whitehead. Gardner wrote to him as well, but Whitehead said that he had heard the negative solution from someone else, and Gardner gave up the trail at that point.

Check the Gardner book for generalizations and further literature on this problem if you’re interested in digging deeper.

Advertisements

About Santo D'Agostino

I have taught mathematics and physics since the mid 1980s. I have also been a textbook writer/editor since then. Currently I am working independently on a number of writing and education projects while teaching physics at my local university. I love math and physics, and love teaching and writing about them. My blog also discusses education, science, environment, etc. https://qedinsight.wordpress.com Further resources, and online tutoring, can be found at my other site http://www.qedinfinity.com
This entry was posted in Math puzzles and tagged , , , , , . Bookmark the permalink.

35 Responses to “The Coconut Problem”; Updated With Solution

  1. Lawson says:

    We did this problem at Brock Brain Benders, correct?

    • Santo says:

      I believe so. I have given the problem in a number of first-year math courses, and most have found it quite challenging. In the universities where I’ve taught, first-year students have had very little practice with problems where the solutions must be whole numbers.

      • Lawson says:

        I can definitely attest to that!
        I had a rough time in my Classical Algebra course compared to calculus.

  2. Nick says:

    Here is another approach…

    Let s(n) be the number of coconuts the nth sailor puts aside during the night. So s(6) = y, in your representation. Thus:

    x = 5s(1) + 1 x + 4 = 5(s(1) + 1)
    4s(1) = 5s(2) + 1 4(s(1) + 1) = 5(s(2) + 1)
    4s(2) = 5s(3) + 1 4(s(2) + 1) = 5(s(3) + 1)
    4s(3) = 5s(4) + 1 4(s(3) + 1) = 5(s(4) + 1)
    4s(4) = 5s(5) + 1 4(s(4) + 1) = 5(s(5) + 1)
    4s(5) = 5y + 1 4(s(5) + 1) = 5(y + 1)

    Hence x + 4 = 5 × (5/4)^5 (y + 1) = ((5^6)/(4^5))(y + 1).
    Since (5^6)/(4^5) is a fraction in its lowest terms, the only way x + 4 can be an integer is if y + 1 is a multiple of 4^5.
    So the general solution is given by x = (5^6)t – 4, where t is an integer.
    The smallest solution is given by t = 1, when x = 5^6 – 4 = 15621.

    • Nick says:

      Oops, WordPress has stripped all of the double implication signs in the equations above! Using “iff” instead, the equations should read:

      x = 5s(1) + 1 iff x + 4 = 5(s(1) + 1)
      4s(1) = 5s(2) + 1 iff 4(s(1) + 1) = 5(s(2) + 1)
      4s(2) = 5s(3) + 1 iff 4(s(2) + 1) = 5(s(3) + 1)
      4s(3) = 5s(4) + 1 iff 4(s(3) + 1) = 5(s(4) + 1)
      4s(4) = 5s(5) + 1 iff 4(s(4) + 1) = 5(s(5) + 1)
      4s(5) = 5y + 1 iff 4(s(5) + 1) = 5(y + 1)

      • Nice solution, Nick!

        I also checked your site, and it’s very nice! I’ll put a link to your site on one of my resource pages next time I get a chance to update them.

        All the best,
        Santo

      • Nick says:

        Thanks, Santo! I will add a link to your site, too.

        Best wishes,
        Nick

  3. Mike says:

    Could someone do me an answer to 4 sailers and a monkey please, many thanks in advance.

  4. Rakesh Chandra Joshi says:

    what is the answer for 11

  5. Luciano says:

    A solution of this problem and its general formula can be obtained with Excel, as shown in the Website.

  6. Ritu Muralidharan says:

    Hi Santo! Have you tried solving this problem using continued fractions?
    http://orion.math.iastate.edu/burkardt/puzzles/coconut_puzzle.html
    If you go on the above link, you will find this problem as ‘Version 3’, and the solution (using continued fractions) can be found on the ‘solution’ hyperlink.

  7. Guisseppe says:

    Williams’ problem did NOT have one remaining coconut for the monkey on the last division. The true answer is 3125 (smallest possible).

    http://www.qbyte.org/puzzles/p007s.html

  8. Bala Nair says:

    here is my solution:

    This solution will satisfy any number of sailors & coconuts:

    n= number of sailors

    c= number of coconuts given to monkey by each sailor.

    Initial number of coconuts = [n ^ (n+1)] – [(n-1) * c]

  9. Pingback: Look for 4th Solution ? “The Monkey and Coconuts” Problem | Math Online Tom Circle

  10. tomcircle says:

    See my update of 3 solutions, in particular the 2nd solution on why (-4) coconuts is a ‘valid’ answer (it means “borrow 4” more coconuts initially). I also derive general cases of n monkeys (iterations).

    My friend had verified with spreadsheet for n =6,
    coconuts = 15,621= 5^6 -4

    http://tomcircle.wordpress.com/2014/05/16/look-for-4th-solution-the-monkey-and-coconuts-problem/

  11. Deepu says:

    2496 is the smallest number possible. Try it

  12. seapuppy says:

    After all that math, you got the wrong answer. The right answer is 3,121. I solved it as a series problem.
    If only one person came to the pile the minimum number would be 6. Two would be 21, three 121. Once you figure that relatioship, then solve it for five.

    • Double-check your result. You’ll find that your result fails because you have left out one step in the process of dividing up the coconuts.

      Alternatively, if you try substituting your result into the fundamental equation for x, it does not lead to a whole-number solution for y.

      Note that your proposed solution is 5^5 - 4, whereas the correct solution is 5^6 - 4.

      • Martin says:

        The smallest positive solution for case n=5 is N=3121 coconuts

      • The version of the problem solved in the video clip (a very good site, by the way) is slightly different from the one presented here, in that here a coconut is also thrown to the monkey in the morning.

  13. Masum Billah says:

    Can you solve this problem for me with 3 sailors and a monkey?

  14. X = -4 mod (5^m) where m = number of sailors
    If m = 3,
    x = 5^3 – 4 = 125 -4 =121 (answer).

  15. albattani says:

    Hi Santo!
    Thank you for this solution!
    Actually, I’ve just heard about this problem in its other version(where the 5 sailors wake up and divide the remaining pile equally among themselves without giving one to the monkey). The equation I got for this problem is :
    1024.x -15625.y = 8404
    Now I used a small computer program to find the first solution x = 3121 and y = 204, but how could one solve this equation properly?

    Thanks and regards
    Georges

  16. Leong says:

    The smallest number answer explained above is wrong!

  17. William says:

    The issue is that the problem as stated in the book says: “And in the morning they divide what coconuts were left, and they came out in five equal shares” There is no mention of a leftover for the monkey at the end. Therefore, the solution of -4 is not correct since that is not divisible by 5. My solution was 63281 as the lowest possible positive solution.

    • There are different versions of the problem published in different places. The solution I presented here is correct for the version of the problem stated here.

      Your solution of 63281 can’t be correct. When one coconut is thrown to the monkey by the first sailor, this leaves 63280 coconuts. When the first sailor takes his fifth share, he leaves 50,624 coconuts. When the next sailor throws one coconut to the monkey, the remaining number of coconuts is not divisible by 5.

  18. kesav says:

    There are 10 people. They go to an island and find that there are many coconuts. So they collect all the coconuts and plan to divide them equally among all of them the next day. While they are asleep, one person feels very hungry at night and plans to take his share. So he goes and divides the coconuts equally but finds that he is 1 coconut short of others. He sees a monkey holding a coconut. So he tries to take the coconut from the monkey but he was hit hard by the monkey with the coconut and he died. In the same night, another person too feels hungry and he plans to take his share. He finds that one person is dead. So he divides the coconuts among the rest of the people and finds that he is 1 coconut short of others. He too sees a monkey holding a coconut covered with blood. He tries to get the coconut from the monkey but he too was hit hard and died. One by one started feeling hungry and each one divided the coconuts equally among the remaining people found that his share was 1 coconut short of others and so tried to get the coconut from the monkey and died in the same way.
    Find the minimum number of coconuts that were collected by them initially?

    how do you answer this?

    • Let the original number of coconuts be x. Then the first condition means that x + 1 is divisible by 10. The second condition means that x + 1 is divisible by 9. The third condition means that x + 1 is divisible by 8, and so on. Thus, the minimum number of coconuts in the original pile is 10! - 1 = 3,628,799. The next largest solution is 2(10!) - 1 = 7,257,599, and in general, any number of the form k(10!) - 1 is a solution.

  19. Justin says:

    It cannot be -4 as question says sailors see the pile become small in size in the morning!

  20. Denise Mesias says:

    Five individuals are suddenly stranded in a jungle and decide to collect food (bananas) as group on day one. At the end of day one, the 5 individuals put all of the collected bananas into a pile that they will divide up evenly the following morning. During the night, one individual wakes and decides he wants his share immediately and divides the bananas into 5 equal piles with one left over that he gives to a nearby monkey. He removes and hides his pile and pushes the remaining four piles back together before returning to sleep. This same process is repeated by each individual during the night. The next morning the remaining pile is once again divided equally into 5 piles with one remaining banana which the monkey receives (6 total) and the individuals take their share. How many bananas where there in the beginning?

    This is our extra credit and my professor is looking for a realistic “positive integer” answer.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s