The monkey and the coconuts is a mathematical puzzle in the field of Diophantine analysis that originated in a short story involving five sailors and a monkey on a desert island who divide up a pile of coconuts; the problem is to find the number of coconuts in the original pile (fractional coconuts not allowed). The problem is notorious for its confounding difficulty to unsophisticated puzzle solvers, though with the proper mathematical approach, the solution is trivial. The problem has become a staple in recreational mathematics collections.
General description The problem can be expressed as:
There is a pile of coconuts, owned by five men. One man divides the pile into five equal piles, giving the one left over coconut to a passing monkey, and takes away his own share. The second man then repeats the procedure, dividing the remaining pile into five and taking away his share, as do the third, fourth, and fifth, each of them finding one coconut left over when dividing the pile by five, and giving it to a monkey. Finally, the group divide the remaining coconuts into five equal piles: this time no coconuts are left over. How many coconuts were there in the original pile?
The monkey and the coconuts is the best known representative of a class of puzzle problems requiring integer solutions structured as recursive division or fractionating of some discretely divisible quantity, with or without remainders, and a final division into some number of equal parts, possibly with a remainder. The problem is so well known that the entire class is often referred to broadly as "monkey and coconut type problems", though most are not closely related to the problem.
Another example: "I have a whole number of pounds of cement, I know not how many, but after addition of a ninth and an eleventh, it was partitioned into 3 sacks, each with a whole number of pounds. How many pounds of cement did I have?"
Problems ask for either the initial or terminal quantity. Stated or implied is the smallest positive number that could be a solution. There are two unknowns in such problems, the initial number and the terminal number, but only one equation which is an algebraic reduction of an expression for the relation between them. Common to the class is the nature of the resulting equation, which is a linear Diophantine equation in two unknowns. Most members of the class are determinate, but some are not (the monkey and the coconuts is one of the latter). Familiar algebraic methods are unavailing for solving such equations.
History The origin of the class of such problems has been attributed to the Indian mathematician Mahāvīra in chapter VI, § 131, 132 of his Ganita-sara-sangraha (“Compendium of the Essence of Mathematics”), circa 850CE, which dealt with serial division of fruit and flowers with specified remainders.Chronology of Recreational Mathematics by David Singmaster That would make progenitor problems over 1,000 years old before their resurgence in the modern era. Problems involving division which invoke the Chinese remainder theorem appeared in Chinese literature as early as the first century CE. Sun Tzu asked: Find a number which leaves the remainders 2, 3 and 2 when divided by 3, 5 and 7, respectively. Diophantus of Alexandria first studied problems requiring integer solutions in the 3rd century CE. The Euclidean algorithm for greatest common divisor which underlies the solution of such problems was discovered by the Greek geometer Euclid and published in his Elements in 300 BC.
Prof. David Singmaster, a historian of puzzles, traces a series of less plausibly related problems through the middle ages, with a few references as far back as the Babylonian empire circa 1700 BC. They involve the general theme of adding or subtracting fractions of a pile or specific numbers of discrete objects and asking how many there could have been in the beginning. The next reference to a similar problem is in Jacques Ozanam's Récréations mathématiques et physiques, 1725. In the realm of pure mathematics, Lagrange in 1770 expounded his continued fraction theorem and applied it to solution of Diophantine equations.
The first description of the problem in close to its modern wording appears in Lewis Carroll's diaries in 1888: it involves a pile of nuts on a table serially divided by four brothers, each time with remainder of one given to a monkey, and the final division coming out even. The problem never appeared in any of Carroll's published works, though from other references it appears the problem was in circulation in 1888. An almost identical problem appeared in W.W. Rouse Ball's Elementary Algebra (1890). The problem was mentioned in works of period mathematicians, with solutions, mostly wrong, indicating that the problem was new and unfamiliar at the time.
The problem became notorious when American novelist and short story writer Ben Ames Williams modified an older problem and included it in a story, "Coconuts", in the October 9, 1926, issue of the Saturday Evening Post.Pleacher (2005)
Williams had not included an answer in the story. The magazine was inundated by more than 2,000 letters pleading for an answer to the problem. The Post editor, Horace Lorimer, famously fired off a telegram to Williams saying: "FOR THE LOVE OF MIKE, HOW MANY COCONUTS? HELL POPPING AROUND HERE". Williams continued to get letters asking for a solution or proposing new ones for the next twenty years.
Martin Gardner featured the problem in his April 1958 Mathematical Games column in Scientific American. According to Gardner, Williams had modified an older problem to make it more confounding. In the older version there is a coconut for the monkey on the final division; in Williams's version the final division in the morning comes out even. But the available historical evidence does not indicate which versions Williams had access to.Antonick (2013) Gardner once told his son Jim that it was his favorite problem.Antonick (2013): "I then asked Jim if his father had a favorite puzzle, and he answered almost immediately: 'The monkeys [sic] and the coconuts. He was quite fond of that one.'" He said that the Monkey and the Coconuts is "probably the most worked on and least often solved" Diophantine puzzle.Pleacher (2005) Since that time the Williams version of the problem has become a staple of recreational mathematics.Wolfram Mathworld The original story containing the problem was reprinted in full in Clifton Fadiman's 1962 anthology The Mathematical Magpie,KIRKUS REVIEW of The Mathematical Magpie July 27, 1962 a book that the Mathematical Association of America recommends for acquisition by undergraduate mathematics libraries.The Mathematical Magpie, by Clifton Fadiman, Mathematical Association of America, Springer, 1997
Numerous variants which vary the number of sailors, monkeys, or coconuts have appeared in the literature.Pappas, T. "The Monkey and the Coconuts." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 226-227 and 234, 1989.
Solutions
Numerous solutions starting as early as 1928 have been published both for the original problem and Williams modification.Underwood, R. S., and Robert E. Moritz. "3242." The American Mathematical Monthly 35, no. 1 (1928): 47-48. doi:10.2307/2298601.Kirchner, Roger B. "The Generalized Coconut Problem," The American Mathematical Monthly 67, no. 6 (1960): 516-19. doi:10.2307/2309167.S. Singh and D. Bhattacharya, “On Dividing Coconuts: A Linear Diophantine Problem,” The College Mathematics Journal, May 1997, pp. 203–4G. Salvatore and T. Shima, "Of coconuts and integrity," Crux Mathematicorum, 4 (1978) 182–185
Before entering upon a solution to the problem, a couple of things may be noted. If there were no remainders, given there are 6 divisions of 5, 56=15,625 coconuts must be in the pile; on the 6th and last division, each sailor receives 1,024 coconuts. No smaller positive number will result in all 6 divisions coming out even. That means that in the problem as stated, any multiple of 15,625 may be added to the pile, and it will satisfy the problem conditions. That also means that the number of coconuts in the original pile is smaller than 15,625, else subtracting 15,625 will yield a smaller solution. But the number in the original pile is not trivially small, like 5 or 10 (that is why this is a hard problem) – it may be in the hundreds or thousands. Unlike trial and error in the case of guessing a polynomial root, trial and error for a Diophantine root will not result in any obvious convergence. There is no simple way of estimating what the solution will be.
The original version
Martin Gardner's 1958 Mathematical Games column begins its analysis by solving the original problem (with one coconut also remaining in the morning) because it is easier than Williams's version. Let F be the number of coconuts received by each sailor after the final division into 5 equal shares in the morning. Then the number of coconuts left before the morning division is ; the number present when the fifth sailor awoke was ; the number present when the fourth sailor awoke was ; and so on. We find that the size N of the original pile satisfies the Diophantine equation
Gardner points out that this equation is "much too difficult to solve by trial and error," but presents a solution he credits to J. H. C. Whitehead (via Paul Dirac): The equation also has solutions in negative integers. Trying out a few small negative numbers it turns out is a solution.Bogomolny (1996) We add 15625 to N and 1024 to F to get the smallest positive solution: .
Williams version
Trial and error fails to solve Williams's version, so a more systematic approach is needed.
Using a sieve The search space can be reduced by a series of increasingly larger factors by observing the structure of the problem so that a bit of trial and error finds the solution. The search space is much smaller if one starts with the number of coconuts received by each man in the morning division, because that number is much smaller than the number in the original pile.
If F is the number of coconuts each sailor receives in the final division in the morning, the pile in the morning is 5F, which must also be divisible by 4, since the last sailor in the night combined 4 piles for the morning division. So the morning pile, call the number n, is a multiple of 20. The pile before the last sailor woke up must have been 5/4(n)+1. If only one sailor woke up in the night, then 5/4(20)+1 = 26 works for the minimum number of coconuts in the original pile. But if two sailors woke up, 26 is not divisible by 4, so the morning pile must be some multiple of 20 that yields a pile divisible by 4 before the last sailor wakes up. It so happens that 3*20=60 works for two sailors: applying the recursion formula for n twice yields 96 as the smallest number of coconuts in the original pile. 96 is divisible by 4 once more, so for 3 sailors awakening, the pile could have been 121 coconuts. But 121 is not divisible by 4, so for 4 sailors awakening, one needs to make another leap. At this point, the analogy becomes obtuse, because in order to accommodate 4 sailors awakening, the morning pile must be some multiple of 60: if one is persistent, it may be discovered that 17*60=1020 does the trick and the minimum number in the original pile would be 2496. A last iteration on 2496 for 5 sailors awakening, i.e. 5/4(2496)+1 brings the original pile to 3121 coconuts.
Blue coconuts