Introduction
The American novelist Ben Ames Williams frequently contributed short stories, serials, and articles to the periodical The Saturday Evening Post. While themes in mathematics were seldom featured in Williams’ writings, a remarkably difficult word problem was presented within the short story Coconuts (Williams, 1926). The consequences of burdening an unsuspecting American middle class with a problem they were ill-equipped to handle were borne out over the 20 years following its publication. During this time Williams was inundated with angry letters and, worse, the occasional tedious solution to the problem he wrote into the pages of The Post (Gardner, 2001).
A quick survey of the internet reveals, irritatingly, just how pedestrian the Williams coconuts problem is to those with a natural intuition in mathematics (Padilla, McPartlan & Haran, 2016). The American Mathematical Monthly (Underwood & Moritz, 1928; Kirchner, 1960), College Mathematics Journal (Singh & Bhattacharya, 1997), and Crux Mathematicorum (Shima & Salvatore, 1978) have each published clever and succinct solutions to the Williams coconuts problem. While the established methods are perfectly ample, they have each been offered exclusively by scholars of mathematics. It is sometimes the case that non-experts are able to offer new insight by approaching problems in an unconventional manner, and one that would not have occurred to someone proficient in the field. Such insights can be valuable in and of themselves, and can sometimes lead to new discoveries. The solution offered herein satisfies the above presuppositions; it was created by a non-expert (this will soon become obvious) and is unlike any other solution published online or in print. Disappointingly it does not appear to have any value at all and is in fact hopelessly inferior compared with the literature standards.
Five Men, a Monkey and Coconuts
The following text has been plagiarized verbatim from the original short story (Williams, 1926).
[…]
The little man still hesitated, said at last reluctantly, "Why, I had it at noon from a man uptown. Haven't been able to get it yet." Marr made an impatient, peremptory gesture; and Wadlin said vaguely, "It's just a problem in indeterminates, I think."
"What is it, man?" Marr cried. "Let me in on it. I'll straighten you out in no time."
"I don't want to bother you," Wadlin argued. "It's not as simple as it looks. I've been at it six hours and more."
"What is it? What is it?" Marr demanded. "You act as though it were confidential."
So at last Wadlin told him. "Well," he explained, "according to the way the thing was given to me, five men and a monkey were shipwrecked on a desert island, and they spent the first 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 he gave that to the monkey, and he hid his pile and put the rest all back together."
He looked at Marr; the man was listening attentively. "So by and by the next man woke up and did the same thing," Wadlin continued. "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 a 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." He added morosely, "Of course each one must have known there were coconuts missing; but each one was guilty as the others, so they didn't say anything."
Marr asked sharply, "But what's the question?"
"How many coconuts were there in the beginning?" Wadlin meekly explained.
Marr laughed. "Why, that's simple enough. You just ----"
But their victuals were served; the table was filled with viands; they could find no room for calculations. So when they were done Marr said, "Here, you come upstairs to the office and we'll work this out. It won't take long."
"I'd like to get it," Wadlin agreed, "before I go to sleep. There must be a formula, some way to work it."
Some Way to Work It
The number of coconuts that remain after the sailors have each stashed their piles has two properties: 1) it is divisible by five, and 2) it is divisible four. The first property is plainly apparent from the text, but the second requires an appreciation for the fact that the pile that was discovered in the morning is the result of a pool of four equal piles left by the last sailor to have hidden their stash of coconuts. Therefore, the number of coconuts left in the pile that was equally distributed among the five sailors is some whole integer (µ) multiplied by 20. This is not an entirely satisfactory start. The number of sailors marooned on the island is arbitrary; the riddle could have just as easily involved any number of sailors (n). The number of coconuts that awaits the sailors as they wake the following morning, then, is µ multiplied by n × (n – 1), or n2 – n:
Beginning at this term, an expression can be derived for the
total number of coconuts in the original pile by recursively reversing the acts
of stashing and discarding coconuts by each of the sailors. The number of
coconuts discarded by each sailor in each iteration, however, is also
arbitrary. Just as any version of Williams’ problem can exist for n
sailors, similarly, the problem can include any number of coconuts (k)
handed to the monkey. Reversing the stashing and discarding step for the last
sailor, S1, gives:
Repeating the process for the previous sailor, S2,
gives:
And the process can be repeated up to S5:
Each iteration of this process produces a new equation that
would solve for a version of Williams’ problem for that particular number of
sailors; S5 is the number of coconuts that the
5-sailors collected in the problem presented in Williams’ short story. This is
not yet a general solution until the Sn of any n can
be calculated without having to iterate these equations step-by-step. Some
general patterns are beginning to emerge that would allow for the equation for Sn
to be determined much more efficiently. For example, the first and last
coefficients for µ are always 1, the powers in the denominators increase by 1
moving left-to-right, and the µ and k coefficients in the middle parts
of the equation appear to be binomial. Rearranging equation [6] to isolate µ
and reorganizing the binomial coefficients such that they appear in the same
order as they would in the 5th row of Pascal’s triangle gives:
The equation can then be represented in a general form:
In equation [8], A, B ,C... represent the
0th, 1st, 2nd… elements of the nth
row of Pascal’s triangle, each of which can be calculated using existing
methods. Within the large set of parentheses, the signs in the numerator will
always alternate, meaning that for problems involving an odd number of sailors
the Z term is always positive, and for problems involving an even number
of sailors the Z term is always negative. In either case the last term Zn(n
– n) can only be equal to 1. With these shortcuts, writing an
expression for Sn of any n is simple enough. Every
term in the general equation can then be substituted with the appropriate value
obtained directly from the word problem, except for µ, which can be any
integer. Substituting the appropriate values from the 5-sailor problem gives:
In order for the value S5 to resolve to a
whole number, the sum of the fractions in parentheses must be equal to 1. Thus
the problem becomes: what value of µ gives a result for the fraction in the
first set of parentheses that compliments the fraction in the other set of
parentheses? To the mathematically naïve, including and especially the
author of this article, this problem can perhaps be best understood with an
analogy. Imagine a special clock with 256 minutes to every hour. The minute
hand, which is broken and can only move in 9 minute intervals, currently rests
at 53 minutes past the hour. How many 9-minute intervals (µ) must pass before
the minute hand comes to rest on midnight, 203 minutes from its current
position? This situation can be expressed as:
Note that it is not important what value a takes.
Equation [11] can be checked for a solution very easily, as the
only meaningful values for a are between 0 and 9, and only one of those
possibilities can give an integer value for µ. The reason for this might not be
obvious. The value a can be thought of as the number of hours that pass
on the 256-minute clock mentioned above. It is clear that the number of
9-minute intervals (µ) required to reach midnight must be less than 256, as
this would bring the minute hand all the way around back to where it started, 9
hours later. In this analogy a is the number of hours that pass before
the hand reaches midnight. As 9 hours brings the minute hand back to where it
started, the solution must have occurred at a < 9. Astoundingly, this
uneducated and fumbling approach is actually faster to solve than the linear
Diophantine method, and arrives at the lowest integer for µ without correction.
Substituting the numbers 0 to 9 into a and searching for an integer
value of µ results in µ = 51 at a = 1; substituting 51 into equation [9]
gives the solution to the coconuts problem:
It is fortuitous that a has so few possible values in
the 5-sailor problem, and which has made this solution possible despite its
inelegance. Unfortunately, this methodology quickly becomes useless in problems
involving larger values of n. For example, when n = 14 there are
~200 trillion possible values for a that must be searched. Fortunately,
µ can be determined with significantly fewer calculations, and for any number
of discarded coconuts (k). In the next section, an examination of the
relationship between µ and k reveals that the number of calculations
required to solve any version of Williams’ coconuts problem can be reduced to
the number of sailors that washed ashore (n).
The Monkey Variable
The number of coconuts the sailors each provide to the monkey is arbitrary. Williams’ problem is told such that the actions of each sailor is intuitive; the fair thing to do with the indivisible coconut is to discard it. But what if the monkey demanded a substantial bribe to not wake the other sailors? Provided the monkey variable, k, remains constant (i.e. does not change between sailors as they wake up), then the equation continues to perform under the same conditions. It is admissible to propose an infinite number of variations on the 5-sailor problem where the bribe paid to the monkey, k, gets larger with each iteration. While the bribe can have an infinite number of different values, the resulting values for µ cycle around within a confined space. In fact, there are only 256 possible values for µ in the 5-sailor problem, each of which are grouped with an infinite number of possible k values. The cyclic nature of these numbers is derived from the fraction that is under the influence of k in equation [7]. The infiniteness of all possible k values can be condensed into a more manageable term, κ, for which there are also only 256 possible values:
A regular modulus function would return a value for κ between
0 and 255. Unfortunately, for κ to satisfy its purpose, it must take a value
between 1 and 256. Thus wherever k mod 256 = 0, let it equal 256
instead. This is the equivalent of saying “twelve o’clock” instead of “zero
o’clock” when referring to the time. The tilde in equation [13] is only to
signify that solutions of 0 should be changed to 256. In spreadsheet programs
the tilde-mod function can be created easily by subtracting 1 from k and
then adding it back after the mod function. For example, in Microsoft Excel,
equation [13] can be written as “= MOD (k – 1, 256) + 1”. The
relationship between µ and κ for the 5-sailor problem is represented in figure
1:
Figure 1: All possible values of mu and kappa for the 5-sailor problem. The five displayed equations describe the five apparent trend lines through the scatter plot.
Figure 1 contains all values for µ plotted against their cognate κ values. Five distinct trend lines are apparent, each with the same slope, and each separated from its neighbours by the same amount. This pattern can be expressed in a more general form:
where b is any number between 1 and n. The
benefit of this relationship is that for any number of sailors discarding any
number of coconuts, the value for µ required to solve the problem can be
determined by checking a very small number of equations, in this case only
five, for integer answers. While this method is serviceable for small groups of
sailors, it is very tedious for large values of n. In the following
section, exploration of the relationship between n, b and κ
exposes a shortcut that allows b to be determined quickly and accurately
without testing all of its possible values, and which effectively allows µ to
be calculated in a single equation.
Mu In One
As with a, b does not reflect any real part of the word problem; it was created to represent the n different µ-intercepts apparent in figure 1, and denotes which trend line the integer solution belongs to. Quickly determining which line an integer value for µ exists on for any value of κ is the same as determining which value of b is required for equation [14] to resolve to a whole number. Since b can only be an integer between 1 and n, it is a simple matter to set up a spreadsheet and determine its value for a large number of different situations where n and k are varied systematically. What precipitates from this exercise is a helpful relationship between n, κ and b:
Table 1: All b values determined for n = 3 to n =15 for kappa = 1 to kappa = 12.
The b values change in a regular and predictable way as
κ gets larger. When n is odd, the b values tick up
by 1 moving across the row. After b = n occurs, the next b
value will be 1, and the cycle continues on that way for all values of κ. When
n is even the pattern is reversed. As κ increases, b
ticks down by 1 and resets to n after b = 1. Another modulus term
is then required to describe the cyclic patterns in this data:
As was the case for equation [13], the tilde in equation [15]
is to signify that solutions of 0 should be changed to n. When n
is even there is no such problem, and so no tilde appears in equation [16].
Substitution of equations [15] and [16] into equation [14] yields the two
expressions that allow µ for any n and κ to be determined in a
single step:
With these two equations in hand, it is relatively straight-forward
to calculate µ in situations that otherwise might have seemed insurmountable.
For example, determining µ for the 19-sailor version of the Williams problem
(where k = 1) by systematically checking all possible values beginning
at 1 requires more than 2 sextrillion iterations. However, recognizing that n
is odd, and applying equation [17] delivers µ effortlessly:
And if the monkey demands a 24-coconut bribe (k = 24):
Even though they were designed specifically with this purpose
in mind, it is eerie to see that these manipulations always generate integer
answers.
Problems Worth Ignoring
The astute reader will have noticed that in table 1, the first entry is at n = 3. This is not a mistake; versions of the Williams problem involving 1 or 2 sailors deserve to be omitted from the list. Their crime is that they are so easy to solve that lumping them together with all other values for n seems silly. This is easy enough to demonstrate. Consider the term in the first set of parentheses in equation [8], which is reproduced here as a function of n:
This function is basically the source of all the trouble with
the Williams coconuts problem, except when n =1 and 2. When n =
1, the denominator becomes the undefined number 00, and so f (1)
is also undefined. This might actually be appropriate when considered in the
context of the word problem. One sailor washes up on a desert island and
collects coconuts. It’s not clear why, but he wakes up in the night and decides
to take his fair share of the coconuts, which is all of them, minus whatever he
gives to the monkey. In the morning he wakes up and divides the remaining pile
of nothing evenly by 1. This actually works, but it does not matter how many
coconuts there were to start with. In short, S1 can be any
integer of your choosing, just make sure the sailor has at least enough
coconuts to pay the monkey.
The case for n = 2 is slightly different. In this situation the denominator is 11, and so f (2) is an integer. This is important because it disconnects the first set of parentheses from the second set in equation [8], meaning that µ is not required to obtain a whole number solution for S2. The consequences are that for any value of k chosen for a 2-sailors problem, µ will be zero every time. There may be other values of n that behave this way. Any number of sailors that produces an integer for f (n) will also give µ = 0 for any chosen value of k. The author of this article is ill-equipped, both intellectually and technologically, to determine if this situation will occur for any number other than 2.
The especially perceptive reader might have noticed an apparent mistake in figure 1, where a µ value at κ = 0 is included on the plot, which the text strictly forbids. In reality there are an infinite number of potential µ values for any situation, and they occur in (n – 1)n –1 intervals (the solution provided here always gives the lowest positive integer for µ). This is fortunate, because there is a very boring solution to problems where the monkey never receives a coconut (k = 0). Strictly speaking, the aim is to seek out the lowest integers for µ and Sn from their infinite distribution. When the monkey is denied receipt of a coconut, the lowest integers for µ and Sn are both 0, suggesting that the sailors either arrived dead on the island or quickly starved to death, as no coconuts were ever collected. Increasing µ from 0 to 256 encourages better engagement with the spirit of the problem, and also a less bleak deduction for the immediate survival of the marooned sailors, thus earning its place on figure 1.
Conclusion
Chemists are awful mathematicians (Winter, 2015). It should come as no surprise, then, that a scholar of organic synthesis approached the Williams coconuts problem completely backwards. A cursory review of any of any of the solutions offered by the internet community reveal that the most direct approach to solving this problem requires an expression that sums each sailor’s hidden stash beginning from the first sailor to have woken during the night (Padilla, McPartlan & Haran, 2016). Such an approach taken to its conclusion will deliver an elegant and serviceable formula. Instead, the focus of the solution detailed here is on the number of coconuts that remains the following morning. While the utility of this approach is admittedly quite terrible, it does work, and may qualify as a general solution.
Running a search on the word “coconuts” in The On-Line Encyclopedia of Integer Sequences returns several entries that relate to the Ben Ames Williams problem (Sloane, A002021; Sloane, A006091; Pol, A193871). An integer sequence for µ at k = 1 has been calculated* for the first 100 meaningful iterations of the same problem (table 2 contains the first 45), and now awkwardly invites itself for inclusion alongside the other entries in the OEIS.
Table 2: All values for mu at k = 1 up to n = 45.
n |
µ |
1 |
0 |
2 |
0 |
3 |
1 |
4 |
20 |
5 |
51 |
6 |
2604 |
7 |
6665 |
8 |
720600 |
9 |
1864135 |
10 |
348678440 |
11 |
909090909 |
12 |
261535698060 |
13 |
685853880635 |
14 |
281241170407092 |
15 |
740800455037201 |
16 |
410525522232055664 |
17 |
1085102592571150095 |
18 |
781282469559318055056 |
19 |
2070863582910344082917 |
20 |
1879498672877297909667780 |
21 |
4993219047619047619047619 |
22 |
5577014881186619679500164220 |
23 |
14844690320183459017245509721 |
24 |
20010448499854249032923573205960 |
25 |
53349431074011364977963258913751 |
26 |
85401771125012041571048589853140024 |
27 |
228004428896561381881358306977785325 |
28 |
427589827948643563878669286668465968060 |
29 |
1142949072870806029743887181150503648715 |
30 |
2482096614722504096743100607573315588934020 |
31 |
6641649422408032258064516129032258064516129 |
32 |
16535762439138134834904060434401211169918336480 |
33 |
44287928403966755097081358567160091504725228575 |
34 |
125312685967532762314921440818939108023474325045792 |
35 |
335903968724817600326115728608867301560512625987701 |
36 |
1071882291038755676619792365818688671828971968756781684 |
37 |
2875334024965311481289553398715037668653185287293494355 |
38 |
10277368246415210166339426662680153131755622502228878404556 |
39 |
27587482102051127745139211611695481515781727405908104220777 |
40 |
109780268775519412726294712764166833431937302588716604084703160 |
41 |
294859956003568091391750243902439024390243902439024390243902439 |
42 |
1299190067998599808267842116178504678462415774681611684936444192840 |
43 |
3491417152216199357134231910796615298001115594621832028741710070141 |
44 |
16949596699597761439905968077702667791073788390398180772325999762654700 |
45 |
45572751634680223414337902426052800788581774144902389939887043693097051 |
References
Gardner, M. (2001) Chapter 1: The Monkey and the Coconuts In The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems, W. W. Norton and Co.
Goldberg, D.(1991) What Every Computer Scientist Should Know About Floating-Point Arithmetic ACM Computing Surveys, 23, 5-48. doi: 10.1145/103162.103163
Kirchner, R. B. (1960) The Generalized Coconut Problem The American Mathematical Monthly, 67, 516-519. doi: 10.2307/2309167
Padilla, T.; McPartlan, P.; Haran, B. (2016) Monkeys and Coconuts Numberphile (numberphile.com)
Shima, T.; Salvatore, G. (1978) Of Coconuts and Integrity Crux Mathematicorum, 4, 182-185.
Singh, S.; Bhattacharya, D. (1997) On Dividing Coconuts: A Linear Diophantine Problem College Mathematics Journal, 28, 203-204. doi: 10.2307/2687525
The OEIS Foundation, On-Line Encyclopedia of Integer Sequences (oeis.org), entries: a) Sloane, N. J. A., A002021; b) Sloane, N. J. A., A006091; c) Pol, O. E., A193871
Underwood, R. S.; Moritz, R. E. (1928) Problem 3242 The American Mathematical Monthly, 35, 47-48. doi: 10.2307/2298601
Williams, B.A. (1926) Coconuts The Saturday Evening Post, Oct. 9
Winter, A. (2015) Computational Chemistry: Making a Bad Calculation Nature Chemistry, 7, 473-475. doi: 10.1038/nchem.2267
Appendix
* Most spreadsheet programs, such as Microsoft Excel, can only store up to 15 significant digits due to the IEEE-754 standard for floating point numbers (Goldberg, 1991). Xnumbers is a free plugin for Microsoft Excel that allows for 32,760 significant digits to be stored and used in calculations, and works extremely well despite it being unsupported. A similar plugin, xlPrecison is also available and is still supported, and was used to calculate all µ values in table 2.
Xnumbers is available at www.thetropicalevents.com/Xnumbers60.htm
xlPrecision is available at precisioncalc.com/xlprecision.html
n |
number of sailors |
k |
number of coconuts claimed by the monkey during each sailor’s dividing and stashing sequence |
Sn |
total number of coconuts in the beginning for n sailors |
µ |
an integer, when multiplied by (n2 – n) gives the number of coconuts that were divided evenly n ways |
κ |
|
a |
in the clock analogy, a represents the number of hours that pass before the minute hand comes to rest on midnight |
b |
an integer between 1 and n, and represents the n different trend lines that appear when µ is plotted against κ. |
Showing 1 Reviews
-
0
Hi Mark!
From a fellow chemist posing as an amateur mathematician:
I like your article - an interesting bit of history behind
the problem too!Being set up as a ‘story-telling problem’ with a single case
of five sailors, one coconut leftover it is an easily accessible puzzle (even
for lapsed maths students like me!) and leads in nicely to the more complex
general solution.The biggest leap for me was how you jumped from the
relatively easy to follow iterations from S1 to S5 in equation 6 and then came
straight to the general solution in equation 7. If I put everything over a
common denominator of (n-1)n-1 and start expanding the terms in the
numerator I can see that you get binomial coefficients for both μn2
and (n-1)x expanded terms which cancel and can sort of understand
how you might be able to use this pattern to derive the general equation - but
would be interested to see your explanation of how you worked through this?I like your analogy for time in solving for μ, and the
figure and table which give the patterns a visual description.You must be logged in to comment
License
This article and its reviews are distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and redistribution in any medium, provided that the original author and source are credited.