A Needlessly Complicated and Unhelpful Solution to Ben Ames Williams' Famous Coconuts Problem
Mark Richardson · 2016
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 of the coconuts, which is all of he gives to the monkey. In the morning he wakes up and the pile of by 1. This actually but it does not matter how many coconuts there were to In can be any integer of just the sailor has at enough coconuts to the monkey. The case for n = 2 is In this situation the denominator is and so f is an integer. This is important it the first set of parentheses from the second set in equation [8], meaning that µ is not required to a whole number solution for The consequences are that for any value of k for a problem, µ will be every time. There be other values of n that this number of sailors that produces an integer for f will also give µ = 0 for any value of The author of this is and to determine if this situation will for any number other than 2. The especially reader might have noticed an apparent in figure 1, where a µ value at κ = 0 is on the which the text In there are an infinite number of µ values for any and they in (n – intervals solution here always gives the lowest integer for This is there is a very solution to problems where the monkey a coconut (k = the is to out the lowest for µ and Sn from their infinite When the monkey is of a the lowest for µ and Sn are 0, that the sailors either on the island or quickly to as no coconuts were µ from 0 to 256 with the of the problem, and also a less for the of the marooned sailors, its on figure 1. are It should come as no then, that a of the Williams coconuts problem A of any of any of the solutions offered by the internet that the approach to this problem requires an expression that each hidden stash beginning from the first sailor to have the night (Padilla, McPartlan & Haran, 2016). Such an approach to its will an and serviceable the of the solution here is on the number of coconuts that remains the following While the of this approach is it does and as a general a on the word in The of that to the Ben Ames Williams problem integer for µ at k = 1 has been for the first meaningful of the same problem 2 contains the first and for the other in the Table All values for mu at k = 1 up to n = n µ 1 0 2 0 3 1 20 51 9 14 20 1: The Monkey and the Coconuts In The of and and What Every Kirchner, The The American Mathematical Haran, and Coconuts Salvatore, Coconuts and Crux Bhattacharya, A Diophantine College Mathematics The of Moritz, The American Mathematical Coconuts The Saturday Evening 9 a spreadsheet such as Microsoft Excel, can only up to to the for numbers is a for Microsoft that allows for to be and in calculations, and despite it A is also and is still and was to calculate all µ values in table 2. is at is at n number of sailors k number of coconuts by the monkey each dividing and stashing Sn total number of coconuts in the beginning for n sailors µ an when multiplied by – n) gives the number of coconuts that were divided n κ the number that remains after k has been divided by (n – where of are substituted for (n – a in the clock a the number of hours that pass before the minute hand comes to rest on midnight b an integer between 1 and n, and the n different trend lines that appear when µ is plotted against κ.