A Needlessly Complicated and Unhelpful Solution to Ben Ames Williams’ Famous Coconuts Problem

  1. 1.  University of California, Irvine

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 n2n:


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(nn) 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 (n2n) gives the number of coconuts that were divided evenly n ways

κ

; the number that remains after k has been divided by (n – 1)n –1, where answers of zero are substituted for (n – 1)n –1

 

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 κ.

 

Reviews

Showing 2 Reviews

  • Placeholder
    Tessa Young
    Confidence in paper
    Quality of figures
    Quality of writing
    Originality of work
    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.

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.