The monkey and the coconuts
The problem is notorious for its confounding difficulty to unsophisticated puzzle solvers, though with the proper mathematical approach, the solution is trivial.
The origin of the class of such problems has been attributed to the Indian mathematician Mahāvīra in chapter VI, § 1311⁄2, 1321⁄2 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.
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.
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.
[citation needed] 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.
The Post editor, Horace Lorimer, famously fired off a telegram to Williams saying: "FOR THE LOVE OF MIKE, HOW MANY COCONUTS?
[3] Martin Gardner featured the problem in his April 1958 Mathematical Games column in Scientific American.
[8] Numerous variants which vary the number of sailors, monkeys, or coconuts have appeared in the literature.
The monkey and the coconuts reduces to a two-variable linear Diophantine equation of the form where d is the greatest common divisor of a and b.
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.
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.
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.
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.
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.
Then the first sailor to wake up will find the pile to be evenly divisible by five, instead of having one coconut left over.
The device of using additional objects to aid in conceptualizing a division appeared as far back as 1912 in a solution due to Norman H.
The smallest such multiple is 3125 · 1, so N = 3125 – 4 = 3121; the number left in the morning comes to 1020, which is evenly divisible by 5 as required.
A formal way of stating the above argument is: The original pile of coconuts will be divided by 5 a total of 5 times with a remainder of 1, not considering the last division in the morning.
Substituting into (1) The Euclidean algorithm is quite tedious but a general methodology for solving rational equations ax+by=c requiring integral answers.
(see (3) in the previous subsection) that will make both N and F positive is 2569, so: Alternately, one may use a continued fraction, whose construction is based on the Euclidean algorithm.
The first step is to obtain an algebraic expansion of the recurrence relation corresponding to each sailor's transformation of the pile,
times yields: Factoring the latter term, The power series polynomial in brackets of the form
is any non-negative integer): Other variants, including the putative predecessor problem, have related general solutions for an arbitrary number of sailors.
When the morning division comes out even, the general solution reduces via a similar derivation to: For example, when
Other post-Williams variants which specify different remainders including positive ones (i.e. the monkey adds coconuts to the pile), have been treated in the literature.
Other variants in which the number of men or the remainders vary between divisions, are generally outside the class of problems associated with the monkey and the coconuts, though these similarly reduce to linear Diophantine equations in two variables.
