Negative Coconuts

This is an ancient problem - probably more than a 1000 years old. The incarnations are many; some appeared in fine literature. This is how Ben Ames Williams (1889-1953) presents the story:

Five men and a monkey were shipwrecked on a desert island, and they spent the first day day gathering coconuts for food. Piled them all up together and then went to sleep for the night.

But when they were all asleep one man woke up, and he thought there might be a row about dividing the coconuts in the morning, so he decided to take his share. So he divided the coconuts into five piles. He had one coconut left over, and gave it to the monkey, and he hid his pile and put the rest back together.

By and by, the next man woke up and did the same thing. And he had one left over and he gave it to the monkey. And all five of the men did the same thing, one after the other; each one taking the fifth of the coconuts in the pile when he woke up, and each one having one left over for the monkey. And in the morning they divided what coconuts were left, and they came out in five equal shares. Of course each one must have known that there were coconuts missing; but each one was guilty as the others, so they didn't say anything. How many coconuts there were in the beginning?

Solution

References

  1. B. A. Williams, Coconuts, in C. Fadiman, The Mathematical Magpie, Copernicus, 1997, 196-214

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Five men and a monkey were shipwrecked on a desert island, and they spent the first day day gathering coconuts for food. Piled them all up together and then went to sleep for the night.

But when they were all asleep one man woke up, and he thought there might be a row about dividing the coconuts in the morning, so he decided to take his share. So he divided the coconuts into five piles. He had one coconut left over, and gave it to the monkey, and he hid his pile and put the rest back together.

By and by, the next man woke up and did the same thing. And he had one left over and he gave it to the monkey. And all five of the men did the same thing, one after the other; each one taking the fifth of the coconuts in the pile when he woke up, and each one having one left over for the monkey. And in the morning they divided what coconuts were left, and they came out in five equal shares. Of course each one must have known that there were coconuts missing; but each one was guilty as the others, so they didn't say anything. How many coconuts there were in the beginning?

Solution

Martin Gardner notes that Williams has modified the ancient variant to make it more confusing. The modification relates to what happened at the morning stage. In the original problem, in the morning - after the sixth division - one coconut was still left over and was handed to the monkey. He also observes that Williams omitted to mention any numerical data, like say how many coconuts has received each of the men from the last division. As it is, the problem has an infinite number of solution; Gardner suggests to find the smallest. He starts with the older problem.

Assuming N is the total number of the coconuts the fellows gathered before going to bed, the first man to wake up took away A coconuts, where N = 5A + 1, and left over in a pile 4A coconuts. Denoting by successive letters the portions taken by the other men, we get a system of six equations with 7 unknowns:

N = 5A + 1,
4A = 5B + 1,
4B = 5C + 1,
4C = 5D + 1,
4D = 5E + 1,
4E = 5F + 1.

There is a direct link between N and F obtained by eliminating the intermediate unknowns:

1024N = 15625F + 11529.

This is a formidable equation to be solved in integers. Gardner found a beautiful and a short solution that was attributed to Paul Dirac. However Dirac had referred Gardner to J. H. C. Whitehead - a nephew of the famous philosopher - who also refused to acknowledge the authorship. So, no one knows the source of that solution.

The solution starts with the observation that if the pair (N, F) solves the equation then so does the pair (N + 15625, F + 1024), and vice versa. In particular, if the equation has an integer solution at all, it is bound to have negative integer solutions as well. Surprisingly, accepting a negative number of coconuts and fostered by an elegant insight one obtains an easy solution.

Two observations play a crucial role. First, one needs to realize that it does not matter when the monkey receives its coconut - before or after the division of the pile. Second, which is more insightful, is that the number N = -4 fits snugly into the conditions of the problem. Indeed, facing -4 coconuts the first shipwreck tosses to the monkey 1 (positive) coconut and is left with a pile of -5. Of these, he takes -1, leaving -4, which is exactly the number he started out with. (This is a reflection of the fact that the equation y = 5x + 1 has a solution (-1, -4).)

Now it's clear that the other 5 divisions all lead to the same result. So, at the end, F = -1 and N can be taken to be -4. To make it positive we add 15625 and obtain N = 15621 as the smallest solution to the old problem.

Gardner finds a pattern: if there are n men and the monkey receives m coconuts at every division then the original number of coconuts has to be N = knn+1 - m(n - 1), where k is an arbitrary parameter. (With m = 1, n = 5, k = 1, N = 15621).

For William's problem, Gardner gives the solution as N = 55 - 4 = 3121. The idea is the same. For the first five steps proceed as before; the subsequent pile sizes will become

3121 → 2496 → 1996 → 1596 → 1276 → 1020.

Luckily, 1020 is divisible by 5 which allows for the morning division.

Remark

There is a straightforward procedure for solving linear Diophantine equations that could be applied to solving 1024N = 15625F + 11529. Recollect the extension of Euclid's algorithm that, for given a and b, finds x and y such that ax + by = gcd(a, b). The procedure may be used to find the multiplicative inverse of a modulo b - if such exists. For a = 1024 and b = 15625, gcd = 1, so that the equation 1024x ≡ 1 (mod 15625) is solvable, viz., x = 10849. Modulo 15625 me get

1024 × 10849 N = 11529 × 10849 = 125078121 ≡ 15621 (mod 15625), or
N ≡ 15621 (mod 15625),

confirming that 15621 is the minimal solution.

For William's problem, 1024N = 15625F + 8404 so that

N ≡ 8404 × 10849 = 91174996 ≡ 3121 (mod 15625),

as expected.

References

  1. M. Gardner, The Colossal Book of Mathematics, W. W. Norton & Co, 2001, Ch. 1: The Monkey and the Coconuts


Related material
Read more...

  • Diophantine Equations
  • Finicky Diophantine Equations
  • Diophantine Quadratic Equation in Three Variables
  • An Equation in Reciprocals
  • A Short Equation in Reciprocals
  • Minus One But What a Difference
  • Two-Parameter Solutions to Three Almost Fermat Equations
  • Chinese Remainder Theorem
  • Step into the Elliptic Realm
  • Fermat's Like Equation
  • Sylvester's Problem
  • Sylvester's Problem, A Second Look

    • |Contact| |Front page| |Contents| Arithmetic |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    72187030