Monkey and the coconuts puzzle with solutions

Submitted by Atanu Chaudhuri on Thu, 27/12/2018 - 23:43

Monkey and coconuts puzzle monkey and the coconuts puzzle

Monkey and the Coconuts, the evergreen math puzzle

The monkey and the coconuts puzzle is among the most popular and actively pursued math puzzles over nearly a century after short story writer Ben Williams modified an older puzzle to make it more difficult and published the modified version as part of a story as far back as 1926 in Saturday Evening Post.

We will first solve the original puzzle that was modified and made more difficult by Ben Williams.

This is according to the well-known problem solving technique of solving a simpler problem first.

Monkey and the coconuts puzzle, Original version

From the Wikipedia version of the puzzle, we produce the older original puzzle as,

Five men and a monkey were shipwrecked on an island. They spent the first day gathering coconuts. During the night, one man woke up and decided to take his share of the coconuts. He divided them into five piles. One coconut was left over so he gave it to the monkey, then hid his share and went back to sleep.

Soon a second man woke up and did the same thing. After dividing the coconuts into five piles, one coconut was left over which he gave to the monkey. He then hid his share and went back to bed. The third, fourth, and fifth man followed exactly the same procedure. The next morning, after they all woke up, they divided the remaining coconuts into five equal shares. This time also 1 coconut was left. What is the smallest number of coconuts that could have been there in the original pile?

While you enjoy solving the simpler version of the puzzle, we will tell you a little more about the life history of the Ben Williams version of the puzzle in which he made the slight change in the final stage. Instead of 1 coconut left over at the end, he changed it to "with no coconut left over" (Wikipedia reference: The coconut and the monkey puzzle). This made the puzzle more difficult and intriguing to solve.

Try to solve this version of the puzzle also.

Writer Ben Williams didn't include the answer or the solution to the puzzle that was reportedly very difficult but interesting, so much so that,

The magazine was inundated by more than 2,000 letters pleading for an answer to the problem. The Post editor, Horace Lorimer, famously fired off a telegram to Williams saying: "FOR THE LOVE OF MIKE, HOW MANY COCONUTS? HELL POPPING AROUND HERE". Williams continued to get letters asking for a solution for the next twenty years. (ref: Wikipedia).

The puzzle was highly valued by the legendary mathematician and puzzler Martin Gardner who contributed to the popularity by featuring it in Scientific American and in some of his famous books. He went on to say that, The Monkey and the coconuts puzzle is "probably the most worked on and least often solved" algebraic puzzle. It is classified as a Diophantine algebraic puzzle.

Following is our solution of the original puzzle. But remember: being a classic math puzzle, there can be other ways to arrive at the solution, and more importantly, if you have really tried to solve the puzzle, you would enjoy the solution more.

Solution to the Monkey and the coconuts puzzle, original version

The solution we are going to present occurred to us while going through the puzzle for a short time. We had recently published multiple solutions of the popular Counting eggs puzzle based on Euclid's division lemma in our Brain teaser section. Perhaps, that was the reason behind this solution of the relatively complex Monkey and the coconuts puzzle occurring to us quickly.

Let us mention here, we are averse to deeper mathematics and so we always try to find out solutions based on simpler patterns and methods that would be clear to most people.

Let us repeat the puzzle for ease of reference.

The puzzle again

Five men and a monkey were shipwrecked on an island. They spent the first day gathering coconuts. During the night, one man woke up and decided to take his share of the coconuts. He divided them into five piles. One coconut was left over so he gave it to the monkey, then hid his share and went back to sleep.

Soon a second man woke up and did the same thing. After dividing the coconuts into five piles, one coconut was left over which he gave to the monkey. He then hid his share and went back to bed. The third, fourth, and fifth man followed exactly the same procedure. The next morning, after they all woke up, they divided the remaining coconuts into five equal shares. This time also 1 coconut was left. What is the smallest number of coconuts that could have been there in the original pile?

Solution stage 0: Division concepts and Division lemma in brief

Before we go any further, let us briefly remind you the age-old concept of division of one integer by a second, formally stated in his division lemma by Euclid,

$a=bq+r$,

where $a$, the larger number is the dividend, $b$, the smaller number is the divisor, $q$ is the quotient and $r$ is the remainder that can be 0 but must always be less than $b$, the divisor.

In a division of two integers, effectively we count number of times $b$ occurs in $a$. Naturally, in a division ALL occurrences of $b$ are taken out of $a$ and that's why the remainder $r$ must always be less than $b$. If remainder is 0, we say, $b$ divides $a$ fully leaving no remainder and so is a factor of $a$.

Briefly this is what happens in a division of two integers.

This much math is to be absorbed to understand the solution. It can't be helped—after all, monkey and the coconuts is declared to be one of the least number of times unsolved puzzles! Isn't it?

Let's now get going with the solution.

Solution Stage 1: Problem analysis and broad definition

Technique of any problem solving is to get to the heart of the problem, shedding all details that are not necessary for the solution.

So we ask our first question, "What did actually happen on six events of divisions?" This is the key question to answer.

If you think clearly with a neutral mind, you will quickly home in to the core activity that is repeated six times,

Six times, a number is divided by 5 with remainder 1.

Now we will ask the second question, "What is the number being divided?" The answer is also simple,

Four times the quotient of the previous division is the number that is divided in the current division, and at the start, the total number of coconuts itself is divided.

With these two facts in mind, we will quickly form the six simple equations representing the six divisions as,

$N=5q_1+1$, divided by the 1st man, one share of $q_1$ taken, leaving $4q_1$.

$4q_1=5q_2+1$, divided by the 2nd man.

$4q_2=5q_3+1$, divided by the 3rd man.

$4q_3=5q_4+1$, divided by the 4th man.

$4q_4=5q_5+1$, divided by the 5th man.

$4q_5=5q_6+1$, divided in 5 equal shares among the five men, each getting their final share as $q_6$ number of coconuts leaving 1 even at this stage.

The $q$'s are the quotients suitably named and the original number of coconuts named as $N$.

Solution stage 2: Identification of Key pattern and key method

Now stop briefly to analyze the six equations. Can you find a common pattern? Yes, each of the six equations has 1 coconut as the remainder.

This gives rise to the immediate possibility of,

Adding 4 to make any of the six numbers on the left hand side, say, $4q_4$ plus 4, a factor of 5.

We identify this as the key method based on the key pattern. We will explain shortly why.

Solution stage 3: Use of key method based on key pattern: Working backwards approach as the key strategy

Any difficult problem needs to be approached with proper strategy, and not randomly. We identify working backwards from the final sixth division towards the original first division following the powerful working backwards approach as the key strategy in this case.

Accordingly, we first add 4 to the sixth equation applying the key method to get,

$4q_5=5q_6+1$,

Or, $4q_5+4=5q_6+5$,

Or, $4(q_5+1)=5(q_6+1)$.

This is the crucial relation from which we conclude from factors multiples concepts, that $(q_5+1)$ must have a factor of 5.

Moving up to the fifth equation and adding 4 to it again we have,

$4q_4=5q_5+1$,

Or, $4q_4+4=5q_5+5$,

Or, $4(q_4+1)=5(q_5+1)$.

On the right hand side, the coefficient 5 contributes one 5 and $(q_5+1)$ contributes a second factor of 5. So, $(q_4+1)$ must have a factor of $5^2=25$.

Continuing this way we conclude,

$(q_3+1)$ must have a factor of $5^3=125$,

$(q_2+1)$ must have a factor of $5^4=625$,

$(q_1+1)$ must have a factor of $5^5=3125$.

Now adding 4 to the first equation we have,

$N+4=5(q_1+1)$.

Solution final stage: Mathematical reasoning

We already know $(q_1+1)$ must have a factor of 3125. So $(N+4)$ must have a factor of $5\times{3125}=15625$.

If $(q_1+1)$ had factors other than 3125, all the conditions would still be valid, but in that case value of $(N+4)$ would be larger than when $(q_1+1)$ consists of only the single factor of 3125.

So, the smallest value of $N$ will be given by,

$N+4=15625$,

Or, $N=15621$.

Testing the solution

By first division by 5,

$15621=5\times{3124}+1$.

Four shares of 3124 each, that is, 12496 is divided into 5 shares by the second man,

$12496=12495+1=5\times{2499}+1$.

Four shares of 2499 each, that is, 9996 is divided into 5 shares by the third man,

$9996=9995+1=5\times{1999} +1$.

Four shares of 1999 each, that is, 7996 is divided into five shares by the fourth man,

$7996=7995+1=5\times{1599}+1$.

Four shares of 1599 each, that is, 6396 is divided into five shares by the fifth man,

$6396=5\times{1279}+1$.

At the last stage, remaining four shares of 1279 each, that is, 5116 is divided into five shares by all the five men together with 1 left out even at this last stage,

$5116=5115+1=5\times{1023}+1$.

Note that this division of 5 equal shares leaving 1 cannot be continued any further.

Now we are in a position to take on the modified version of the puzzle as published by Ben Williams.

Solution to monkey and the coconuts by Ben Williams

We will now produce the puzzle published by Ben Williams,

Five men and a monkey were shipwrecked on an island. They spent the first day gathering coconuts. During the night, one man woke up and decided to take his share of the coconuts. He divided them into five piles. One coconut was left over so he gave it to the monkey, then hid his share and went back to sleep.

Soon a second man woke up and did the same thing. After dividing the coconuts into five piles, one coconut was left over which he gave to the monkey. He then hid his share and went back to bed. The third, fourth, and fifth man followed exactly the same procedure. The next morning, after they all woke up, they divided the remaining coconuts into five equal shares. This time no coconuts were left over. What is the smallest number of coconuts that could have been there in the original pile?

In the same line as above we will present the six division relations as before. Only change will be in the last division.

$N=5q_1+1$, divided by the 1st man, one share of $q_1$ taken, leaving $4q_1$.

$4q_1=5q_2+1$, divided by the 2nd man.

$4q_2=5q_3+1$, divided by the 3rd man.

$4q_3=5q_4+1$, divided by the 4th man.

$4q_4=5q_5+1$, divided by the 5th man.

$4q_5=5q_6$, divided in 5 equal shares among the five men, each getting their final share as $q_6$ number of coconuts leaving no coconuts at this last stage.

Solution by Mathematical Reasoning and systematic enumeration

Disregarding at the moment the last equation, if we consider the problem to continue for five stages of division and not six, the first five equations will represent the solution.

In this case, $N$ will be $5^5-4=3121$, and not $5^6-4=15621$.

Taking this cue, we shift our focus to the sixth equation,

$4q_5=5q_6$.

From factors multiples concepts, we conclude that $q_5$ must be a multiple of 5 as well as $q_6$ must be a multiple of 4.

Working down from minimum value of $N=3121$ for satisfying first five conditions, if we can satisfy the last stage binding condition for solution, we know we got the answer.

The series of values for six stages with the smallest value of $N$ satisfying the first five relations we get,

$3121=5\times{624}+1$

$4\times{624}=2496=2495+1=5\times{499}+1$

$4\times{499}=1996=1995+1=5\times{399}+1$

$4\times{399}=1596=1595+1=5\times{319}+1$

$4\times{319}=1276=1275+1=5\times{255}+1$

$4\times{255}=5\times{204}$.

$q_5=255$ has a factor 5 as well as $q_6=204$ has a factor 4 and 3121 is the smallest number that satisfies all the rest 5 conditions.

So 3121 is indeed the solution to the monkey and coconuts puzzle as released by Ben Williams.

End note

The solution to the first original problem largely follows mathematical reasoning whereas for the modified version, not only did we take help of the experience of solving the more straightforward original puzzle but also had to take recourse to systematic enumeration along with mathematical reasoning. On the whole though none of the solutions is based on random approach or an approach based on guesswork. Additionally, the solutions should be relatively easy to understand.

Art credit: Anindya Chaudhuri