 Log in Help AAABIT
Coconut palms
2008-09-18 10:19
Rajaraman Sundaram
CC-BY-3.0

# Coconuts by Ben Ames Williams — general solution

This problem was taken from a story published on 9th October 1926, by Ben Ames Williams in The Saturday Evening Post

## Coconut Problem for Five Men (as originally defined)

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

So by and by the next man woke up and did the same thing. 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.

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.

How many coconuts were there in the beginning?

### Algebraic solution by Professor Lynn Garner

let n be the original number and let Ai be the amount left by the ith man.      where k is each man's share of the pile of coconuts remaining in the morning; since the amount left in the morning was a multiple of 5 — therefore, expressing n in terms of k: The smallest value of k that makes n an integer is k = 51, for which n = 3121.

### Example (systematic information-based) solution by Matthew Slyman

The obvious approach is to work the problem backwards.

Each time a man wakes up in the night, he effectively removes one coconut (for the monkey) = the remainder, and then reduces the number of coconuts to of the previous number. (Before and after this procedure, there is a natural number of coconuts.) The final number is divisible by five.
Five and four are coprime. 5×4=20. If only one man had woken up in the night, this is the smallest number that could have been left at the end of the night (since it’s the smallest number divisible by five, multiplied by the numerator of the fraction ). So if only one man had woken in the night, there would have been at least 26 coconuts when he first woke during the night — but there could equally well have been some multiple of 20 coconuts remaining in the morning: the set of possible values is: 26+25ℕ. This is what we know so far, about the number of coconuts remaining when the 5th man awoke in the night.

Only, since another man (the 4th) had previously awoken during the night, this natural number must be the result of another natural having been multiplied by . So to get the previous natural number in the sequence, we need to multiply by 5/4. 26/4=6r2 (26 is not divisible by four), so this won’t do. We need the next number to have a remainder of 0 when divided by 4. 25 has a remainder of 1 when divided by 4, so we just need to add 2×25 to 26, to get the smallest number that will satisfy the constraints we have applied so far (the set of possible values for the number of coconuts remaining in the morning, is now 76+100ℕ). Therefore, the set of possible values for the number of coconuts remaining when the 4th man wakes up during the night, is:

5(76+100ℕ)/4+1 = 96+125ℕ

Only, since another man (the 3rd) had previously awoken during the night, this natural number must be the result of another natural number having been multiplied by . So to get the previous natural number in the sequence, we need to multiply by 5/4. This is no problem for the offset 96, but the wavelength 125 (which has remainder 1 when divided by 4), will need to be multiplied by four. Therefore, the set of possible values for the number of coconuts remaining when the 3rd man awoke in the night must have been in:

5(96+500ℕ)/4+1 = 121+625ℕ

Only, since the 2nd man had previously awoken during the night, this must have already been multiplied by . So to get the previous number in the sequence, we need to multiply this by 5/4, resulting in another natural number… 121/4 = 30r1, 625/4=156r1 — so we need at least three 625’s to bring the remainder when divided by 4 around to zero, and also, the step (wavelength) must be multiplied by 4. Therefore, we must modify the constraint for the start of Step 3 (previous paragraph), as follows:

(121+3×625)+(4×625)ℕ = 1996+2500ℕ

Therefore, 5(1996+2500ℕ)/4+1 gives the number at the start of Step 2:. So to get the previous number in the sequence, we need to multiply by 5/4, resulting in another natural number… 2496/4 = 624r0, 3125/4 = 781r1. So the constraint for the beginning of Step 2 must be modified again, taking into account this further constraint. (1×4=0 in arithmetic modulo 4. So we need to multiply the step/wavelength, once again, by four; in order to satisfy the whole set of constraints.)

2496+3125ℕ

Only, since the 1st man had previously awoken during the night, this must already have been multiplied by

2496+12500ℕ

We can now calculate the number of coconuts prior to the 1st man awaking during the night.

5(2496+12500ℕ)/4+1 = 3121+15625ℕ

In other words, there were at least 3121 coconuts in the evening before the men & monkey went to sleep. (There could have been 3121, plus any multiple of 15625.)

When the men woke up in the morning, there were just 1020 left!

## Coconut Problem for m Men (Professor Lynn Garner)

A group of men, m in number, and a monkey spent a day on an island gathering coconuts. At the end of the day there was a large pile of coconuts, but they were tired and decided to wait until the next day to divide them up.

During the night, a man awoke and decided to take his share right then. He divided the pile into m piles, finding one left over, which he threw to the monkey. He then hid one of the piles for himself, put the other piles back together into one pile, and went back to sleep.

A second man awoke, and did the same thing. He also divided the pile of coconuts into m piles, found one coconut left over, which he threw to the monkey, hid one of the piles for himself, reassembled the main pile, and went back to sleep.

Well, each man in the group awoke, in turn, and did the same thing, each finding one more coconut than a multiple of m, throwing the extra coconut to the monkey, hiding his share, and rebuilding the pile.

In the morning, the pile was much diminished, but since each man was guilty, no one said anything. They divided the pile into m piles exactly (no extra coconut this time) and each took his share.

This is the question: What is the smallest number of coconuts that could have been collected initially?

### General algebraic solution by Professor Lynn Garner

Let nk be the number of coconuts left by the kth man during the night. Let n(= n0) be the initial number of coconuts gathered. Then:    Rewriting this last expression, we have: Summing the geometric progression, using 1+r+r²+…+r(m−1) = (1−rm) / (1−r) and simplifying, we get: But this is the number of coconuts left in the morning, so is a multiple of m. Let q be a positive integer, and set: Solving for n, we eventually get : In order for n to be an integer, we only need [m−1+qm] / (m−1)m to be an integer. So let r be an integer and set: Isolating the qm term, we get ✻✻: Because m and m−1 are relatively prime, it must be that (m−1)m−1r−1 is divisible by m, so that for some s:  That is, some multiple of (m−1)m−1 is also one more than a multiple of m. That such integers r and s exist follows from the fact that m and m−1 are relatively prime. For example,

mcalculationrs
31×2² = 4 = 1×3+111
43×3³ = 81 = 20×4+1320
51×4⁴ = 256 = 51×5+1151
65×5⁵ = 15625 = 2604×6+152604
71×6⁶ = 46656 = 6665×7+116665
87×7⁷ = 5764801 = 1×3+17720600

Conjecture: {if m is even, r = m−1; if m is odd, r = 1}.

Using ✻✻ to replace , we eventually get: The conjecture is easy to prove: m−1 is congruent to −1, so to an even power (m odd) is congruent to 1, and to an odd power (m even) is still −1, so needs another factor of m−1 to square it.