08 May 2015 05:00

In the past week, Numberphile, a YouTube channel for math nerds like myself, released a video about a rather interesting numerical challenge that first appeared in a newspaper in 1926. This "Coconut Problem" is a classic puzzle for math students due to the problem's simplicity, yet still requiring a non-trivial method in order to be solved.

The problem goes thus, quoted from this paper by William Chen, but modified in the end in order to correspond with Numberphile's video:

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.

B‌y a‌n‍d ‌by ‌t‌he‍‌ ne‍x‍t‍ ma‍‌n‍ ‍wok‌‌‍e u‌p a‌n‍d d‍id‍ t‌h‍e ‍‍s‍ame‌ th‍‍‌ing‌. ‌An‍d ‌he ‍‍ha‍d ‌o‌ne ‌l‌e‍f‌t o‍‍v‌er,‍ an‌‌‍d ‍he ‍ga‍ve ‌i‌t t‌‌o‌ t‌h‍e‌ ‌mon‌key‌. A‌nd‍ al‌l ‍f‍‌i‍ve‌ ‌of‌ ‌t‍he ‍‌‍‍m‌en‌ di‍d t‍he‍‌ s‌am‌e‌ ‌thi‌ng‍, ‌on‌e‌ a‌f‍‍‌te‍‍r‌‍ ‌‍th‌e ‌oth‍er‍; ‌eac‌h o‍n‍e ‌tak‌ing‍ a ‍f‌i‌‌ft‍h‌ of‍ ‍the‍‌ co‌‌c‌onu‌ts‌ ‍‌in ‌the‌‌ ‍p‌‍ile‍‍ wh‌en ‌h‌e ‌wo‍‌k‍e u‍p‌,‍ a‌nd‍‌ ea‌ch‍ ‍on‌e ‌ha‌v‌i‌ng ‌o‍‌ne‌ l‌e‍‍ft‍‌‍ ‍ove‌r‍ fo‌r‍ ‌‌t‍he‍ m‌onk‍e‍y.‌ A‌nd ‍in ‍‍t‌h‌e‌ m‍o‌rn‍in‍g t‍‌hey divided what coconuts were left, and they came out in five equal shares, [but this time, there was none left for the monkey]. 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?

At first, the problem seems deceptively simple. Immediately, we can define a few rules:

  • At each step, the number of coconuts, call it $c_n$, when divided by five must have a remainder of 1. This translates to the expression $c_n \mod 5 = 1$.
  • At the last step, the modulus is actually 0.
  • In the end, the monkey has 5 coconuts.

As simple as the rules may be, it turns out that the overall process needed for solving this problem is not as nice. Finding the original number of coconuts requires solving a Diophantine equation, which is an equation with two or more unknown variables whose solutions are constrained to the set of integers.

In all honesty, it would be redundant for me to simply repost the solution method given that Chen's paper and the Numberphile video explain it rather well. So instead, I'm going to take you through a different way of approaching the problem.

Before reading the below, try solving this yourself!

Another Way of Thinking About It

I should make a disclaimer: I am not trying to show you a deterministic way of solving this problem nor a formal mathematical proof. So yes, the method is sloppy, but it works. And if anything, it can show you the power of finding patterns and making hypotheses.

What is a "Transaction"?

From now on, whenever one of the sailors does the division at night, I will call that a "transaction". Given an original pile, a transaction will result in a new, smaller pile after the sailor takes his share and gives a coconut to the monkey.

But, can we describe this "transaction" mathematically?

Of course! All we need to do is follow the steps:

  1. First, we start off with an original pile with $n$ coconuts in it.
  2. We know we are going to give a coconut to the monkey, so subtract 1 from the original number to get $n-1$ coconuts. The result should be divisible by 5.
  3. Now, we find out how big the sailor's share is by dividing by 5: $(n - 1) \div 5$
  4. Finally, find the amount of coconuts in the remaining pile. We know that this will be four times the size of the sailor's share (since there are four other sailors), so multiply by 4: $(n - 1) \div 5 \times 4$

Following the above steps will give us the size of the new coconut pile after a sailor performs a transaction. For demonstration, let's assume that the number of original coconuts was 26.

  1. Start with 26 coconuts.
  2. $26 - 1 = 25$ coconuts for the sailors
  3. $25 \div 5 = 5$ coconuts per sailor
  4. $5 \times 4 = 20$ coconuts in the new pile after the sailor stashes his share

Ok, so a transaction is simple a mathematical process. Now what?

Only One Sailor

Now we consider a simpler problem and see if we can find any patterns. In the story, all five sailors perform a "transaction" one at a time, but for now, let's say that only one sailor does this. What do we know?

  • The original number of coconuts in the pile must be some number that is 1 greater than a multiple of 5 (like 6, 11, 16, 21, etc), otherwise the monkey would not get a leftover coconut
  • After the transaction, the number of remaining coconuts must be divisible by 5.

What number(s) of original coconuts does this? Well, we've already found one! If we consider the number 26 in the example in the previous section, we ended up with a new pile with 20 coconuts in it. Since 20 is divisible by 5, 26 works as a viable number of starting coconuts.

Note that numbers like 21 do not work; in that case, a transaction would result in 16 remaining coconuts, and this is not divisible by 5.

So, 26 coconuts work for one sailor. Are there any other numbers? As a matter of fact, there are infinitely many! How can we find them?

Working Backwards

Let's try working backwards. Pretend like we know that the size of the pile after a transaction was 20. Now, let's do the transaction backwards:

  • First, divide by 4 (since the opposite of multiplying is dividing). This yields 5.
  • Multiply by 5, yielding 25
  • Add 1, giving 26, the original number of coconuts.
(1)
\begin{align} 26 \xrightarrow{- 1} 25 \xrightarrow{\div 5} 5 \xrightarrow{\times 4} 20 \\ \\ 26 \xleftarrow{+ 1} 25 \xleftarrow{\times 5} 5 \xleftarrow{\div 4} 20 \\ \end{align}

So, to find solutions other than 26, you only need to select some nearly-arbitrary number of coconuts and work the transaction backwards to find out how many coconuts were needed in the original pile. Note, of course, that the number we choose cannot be any old number. For instance, if we chose 25 as the size of the pile, then we immediately run into problems because we cannot divide 25 by 4.

Additionally, we cannot choose something like 16 because 16 is not divisible by 5, thus not satisfying the original problem description. The number we choose must be a multiple of both 4 and 5, which is another way of saying it must be a multiple of 20.

So let's try 40.

  1. $40 \div 4 = 10$ coconuts per sailor
  2. $10 \times 5 = 50$ coconuts for the sailors (the monkey has the last one)
  3. $50 + 1 = 51$ coconuts in the original pile

So 51 works, along with 76, 101, 126, and so on. In fact, all of these answers (for a single sailor) are simply one greater than a multiple of 25! In other words, if only one sailor performs a transaction, then the answer is any integer solution for $25n + 1$.

Great! So, can we do something like this for five sailors? Yes, but it is not so simple…

The Part Where the Algebra Steps In

Our first thought is to simple do this "backwards transaction" five times, but we immediately run into some issues. For instance, we know that a valid pile size for the One-Sailor mini-problem is 26. So if we want to solve the Two-Sailor problem, we only need to go backwards. Unfortunately, 4 does not divide into 26 evenly!

In other words, we would need to find a number from the $25n + 1$ set that is divisible by 4. 76 is, and if we apply the backwards transaction, we get 96. But then we'd have to do this three more times, and each time it must result in a pile size that is divisible by 4. This kind of guess and check will not work.

So what do we do? We will need to use a little bit of algebra.

Back to One Sailor

Let's take a closer look at the One-Sailor problem. We know that the result of the transaction must yield a result that is divisible by 5. In algebra, we can represent this with the fancy fancy math statement below:

(2)
\begin{align} n \in \left\{ 5x \;\; | \;\; x \in \mathbb{Z} \right\} \end{align}

But we'll just use the term $5n$ to represent a number divisible by 5.

Now, all we need to do is apply the "backward transaction" to this mysterious $5n$ number! If you know some algebraic rules, it should be simple to follow:

  1. Divide by 4: $5n \div 4 = \frac{5}{4} n$
  2. Multiply by 5: $\frac{25}{4} n$
  3. Add 1: $\frac{25}{4} n + 1$

This looks ugly, but we can apply a neat trick to simplify this a little. We only care about numbers that are integers. For instance, if $n = 1$, then we would have $7 \; \frac{1}{4}$ coconuts in the pile, and this doesn't make sense. So what can we do? Mathematicians might smite me for this, but we can actually just get rid of that 4 altogether. What does this yield?

(3)
\begin{equation} 25n + 1 \end{equation}

This is the same thing that we got in a previous section! This expression tells us all of the possible answers that solve the One Sailor problem.

Now for Two Sailors

To solve the Two-Sailor problem, we only need to perform the backward transaction again, this time on the expression $25n + 1$. This is because the result of the regular transaction on the original pile must yield a new pile that is a multiple of 25 plus 1, otherwise our final pile after all transactions will not be divisible by 5 like we need it to be.

We perform the same process:

  1. Divide by 4: $(25n + 1) \div 4 = \frac{25}{4} n + \frac{1}{4}$
  2. Multiply by 5: $\left(\frac{25}{4} n + \frac{1}{4}\right) \times 5 = \frac{125}{4} n + \frac{5}{4}$
  3. Add 1: $\left(\frac{125}{4} n + \frac{5}{4}\right) + 1 = \frac{125}{4} n + \frac{9}{4}$

This time, we cannot merely drop the 4 because that would result in $125n + \frac{9}{4}$, and that ending fraction ruins things. Instead, we chose a magical value for $n$ which will yield a nice integer, and that integer will be used instead of $\frac{9}{4}$.

As it turns out, letting $n = 3$ gives us 96, so our final expression is $125n + 96$.

This gives us a solution for the Two-Sailor problem. In other words, if we started off with a pile size of 96 (or 221, 346, etc), and performed a transaction twice, we will end up with a multiple of 5 exactly.

FINALLY, for Five Sailors

Now that we know what to do, we only need to apply this backward transaction process three more times in order to obtain an expression that solves the original Five-Sailor problem. I let you do the math on your own, but your work ought to yield the following expression:

(4)
\begin{equation} 5^6 n + 3121 \end{equation}

And, if we let $n = 0$, we get that there must have been 3121 coconuts in the original pile.

By the way, this isn't how I solved it. I actually used pattern-finding and hypotheses (ie. glorified guess and check).

Or the Easy Way Out

This method is nice because it can be easily written into a program. Sometimes, simply writing up a quick Javascript script is quicker than doing all of the math ;)

var transaction = function(n) {
    return --n / 5 * 4;
};
 
var isCorrect = function(n) {
    for(var i = 0; i < 5; ++i) {
        if(n % 5 != 1)
            return false;
        n = transaction(n);
    }
    return n % 5 == 0;
};
 
var LIMIT = 1000000;
var i = 1;
while(i < LIMIT && !isCorrect(i))
    ++i;
document.write("The answer is: " + i);

References:

Image Courtesy: Numberphile

Comments