Updated: Aug 1
Welcome to the June edition of GLeaM! Today, we'll be exploring one of my very favorite investigative problems, the Monkey-Coconut Problem (aka The Monkey and the Coconuts). This is actually one of the first problems I delved into at my earliest math summer program, Emory Math Circle's Week of Mathematical Exploration, and I'm so excited to re-examine it this month with all of you.
Today's article is a 'solve-as-you-go' article, meaning that we'll be modeling our own math circle experience virtually. Throughout your read, you'll be asked to test out ideas, solve little pieces of the puzzle, and make conjectures (or guesses) about our solution. Each time you see an image of a monkey, stop scrolling and experiment a little before you continue reading. The image should block the answer before you see it. My goal is to guide you through the process of creative exploration it takes to become the best critical thinker you can be and to show you a little piece of what mathematicians do every day. To take full advantage of this, go grab a pencil and a piece of paper, and get ready to test your wits against one of the most fun recreational math puzzles out there!
Here are a few other solve-as-you-go articles that you are welcome to check out after this one:
The Four Fours Puzzle: To Infinity and Beyond! (Also my most popular article!)
That's all for today's intro, so let's jump into the article itself!
The Monkey-Coconut Problem
Primary Source: The Second Scientific American Book of Mathematical Puzzles and Diversions by Martin Gardner
The problem you're about to read has been in the recreational math canon for quite some time, so you'll see many variations of it. The version below is based on the October 9, 1926 issue of The Saturday Evening Post, but I have altered it slightly to make the math a little more straightforward. We'll look back at the verbatim version towards the end of the article.
"Five men and a monkey were shipwrecked on a desert island, and they spent the first day gathering coconuts for food. They piled the coconuts 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 an argument 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.
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.
In the morning, they divided what coconuts were left, and they came out in five equal shares plus one coconut (which was, of course, given to the monkey). Each one must have known there were coconuts missing, but each one was guilty as the others, so they didn't say anything. What is the smallest number of coconuts that could have been there in the beginning?"
And here's my follow-up question: What about the general case? We certainly do not have to have five pirates, so what about n pirates? Can you express the minimum number of coconuts in a formula in terms of n?
Before you continue reading, see if you can begin to answer the problem yourself. What approaches can you come up with? How do you think you should start?
Here are a couple good problem-solving strategies:
Set up a series of equations that represents the situation—where all your variables must be integers.
Start with small and specific cases. Try it for the original statement of five pirates and go even smaller with four, three, two, or even one pirate. What patterns can you find?
When you're ready, scroll past the image and keep reading.
The Monkey-Coconut Problem itself has only been around for about a hundred years, but the math behind it is actually quite old. It is based on a system of so-called 'Diophantine' equations—named after Diophantus of Alexandria who was the first to considerably tackle equations that required integer (or rational) solutions. Diophantus was born in the 200s AD, and thus, the stage for our thieving monkeys was set almost 2000 years ago.
If you followed through and came up with a system of Diophantine equations, you hopefully created something along these lines:
N = 5A + 1
4A = 5B + 1
4B = 5C + 1
4C = 5D + 1
4D = 5E + 1
4E = 5F + 1
Here, N represents the total number of coconuts, A through E represent the amount the first through fifth sailor took for themselves, and F is the amount each sailor receives in the division at the end.
For a little more explanation, notice where the coefficient of 4 comes from: After the straightforward division of N into 5 piles of A with 1 left over, the first sailor takes A away and the monkey takes 1 away. This leaves 4A coconuts for the new pile, which is then divided as if it were the original pile. Take a moment to convince yourself that these equations are indeed correct for the situation.
Now, go ahead and solve them using basic system-of-equation methods, like elimination and substitution. This equation has an infinite number of solutions, so your goal is to come up with a setup for N in terms of just one variable that you can vary to get all of the solutions. (The most natural variable to use is F.) When you're ready, continue reading.
I won't show you the entire process of substituting, so we'll go ahead and skip to the solution:
The equation for N in terms of F is 1024N = 15625F + 11529.
Our goal is to find the smallest possible value of N that satisfies the equation for some value of F.
Though this is a linear equation (involving two variables that are not raised to any powers), it is very difficult to solve because the coefficients are quite huge.
At this point, our best course of action is to experiment and see if there is a more effective way to solve the problem.
Don't worry though, this did grant us some extremely valuable insight into the nature of the problem. Notice that 15625 = 5^6, 1024 = 4^5, and 11529 = 5^6 - 4^6.
It is clear that the problem is intrinsically exponential. After all, we are dividing a pile into the same number of piles over and over again (even if we are setting one aside for the monkey). Now, we have even more evidence to support the fact that the solution will likely come as a combination of relatively simple powers.
From here, go through the same process of solving this setup for two, three, and four pirates. (You can even try just one pirate, but be careful with your definitions because it's more difficult to define the appropriate situation when there's no competing pirates.)
You'll be able to solve the smaller equations more easily by simple trial-and-error. Can you write your answers in terms of simple powers as well?
Once you start to see the pattern, try writing the equation in N and F in terms of n pirates. Is there a general solution that you can write in?
When you're ready, keep reading.
While you're thinking about the above two questions, I'd like to present an important sidenote.
There is a standard method for solving linear Diophantine equations involving a process called the Euclidean algorithm, a method that is traditionally used to find the greatest common factor of two integers.
This algorithm would allow us to solve 1024N = 15625F + 11529 directly off the bat without going through the more trial-and-error experimentation method.
For the most part, this computation is extremely helpful, but there is very important insight to be gained from other methods.
If you know how to solve via this method, you might want to go ahead and work out the answer and possibly even larger examples to build your idea of the problem. This will give you an advantage in finding the pattern. You might even want to plug in n to the Euclidean algorithm and see if you can find the general case answer more directly.
I'm not going to go over the entire process because it does require some knowledge about a concept called modular inverses to fully understand it, and the explanation would be more of a detour than necessary for this article. However, I'd be happy to discuss these ideas with anyone who reaches out, and if there's enough demand, I might write a later article about the Euclidean Algorithm.
If you'd like to read up on it yourself, here are a couple of links:
I'll give you a chance to test out and add to your specific cases using the Euclidean Algorithm if you'd like. When you're ready, keep reading.
Here is a table of some of the smaller examples you hopefully were able to find. I included up to 6 pirates, but as you know, the numbers do get disproportionally large rather quickly, so don't worry if you were only able to come up with one or two entries in the table.
I'll also let you think about why one pirate might give the answer of one coconut. It's rather difficult to decide what actually makes sense in the case of one pirate, and it is possible to write the equation set as N = A + 1, 0A = 0F + 1, in which case there is no solution. This is where definitions get hazy, so it's honestly up to you and what you think fits the best into the overall picture of the problem. I'd love to hear your thoughts about this as well.
This is where we're first going to extract what we think the formula is. If you remember from above, we realized that 5^6 and 4^5 were both important numbers in the solution of five pirates. This points to the fact that the n^(n+1) structure is most likely critical to the solution. Let's make another table of these values.
Wow, look how similar they are! A little inspection shows us that the difference between the entries in the two tables is always n-1, so we now propose that the formula is n^(n+1) - (n-1).
Of course, this is not necessarily the most elegant way of solving the problem, but testing numbers and experimenting is often the best method to start to figure out what you're working with. It's also important to realize that this is by no means a proof. We've simply found a formula that we believe will hold throughout all n, but we've only actually proven it works (through long computation) for n = 1,2,3,4,5,6.
This is where I'll toss it back to you once again. How would you prove this formula?
Time for a Challenge! Here is where we must come up with a full proof of the Monkey-Coconut Problem. You have absolutely all the tools to write up a solution now, and to properly model a math investigation here, I want you to put down the finishing touches.* If you would like to write a proof up and send it to me (at firstname.lastname@example.org), I'd be more than happy to review it for you :)
Here are a few questions to help you build your argument:
Can you prove that every equation in terms of N and F can be written in the following form, just like 1024N = 15,625F + 11,529 above?
(n-1)^n N = n^(n+1) F + n^(n+1) - (n-1)^(n+1)
If so, can you prove that N = n^(n+1) - (n-1) and some corresponding value of F is always a solution?
If so, can you prove that that value of N is always the smallest possible solution? (All the solution values of N occur with regularity; in fact, they form an arithmetic sequence. See if you can use this fact.)
If you want tips as to how to write a proof, feel free to reach out directly to me, or you can read Richard Rusczyk's article "How to Write a Solution" here.
*SPOILER ALERT: I do outline one method of proving our formula below, so keep reading (after you work on your own proof)!
I want to take this opportunity to outline the most elegant, clever method of solving this problem that I've found. This is Professor J.H.C. Whitehead of Oxford University's 'negative coconut' method. If you'd like, you can choose to include some of the elements of this argument in your proof. This is actually a full outline of a proof to the Monkey-Coconut Problem, but it is not the standard proof you would most likely write for the challenge above, so I like to think I'm not really giving anything away. After all, the insight behind what I'm about to show you more than makes up for it. (Once again, I am using Martin Gardner's The Second Scientific American Book of Mathematical Puzzles and Diversions as my source.)
Let's think about our case of five pirates. As we've pointed out, the number 5^6 is extremely important for our solution, but we haven't yet explained fully why it is so critical. Perhaps you've already noticed that we are dividing our N coconuts into five piles six different times: once for each of our five pirates and once in the final division in the morning. This creates our number 5^6—and in general, it justifies the importance of n^(n+1) in this problem as a whole.
In addition, this not only explains why 5^6 is important, but it also justifies the following fact: If N = x corresponds to a solution to our equation 1024N = 15625F + 11529, then any multiple of 5^6 can be added to x and the sum will still be a solution for N. This is because the new 5^6 term is exactly divided into integer values throughout each of our pirates' six divisions, and thus, it has no additional remainders that mess with our scheme.
In fact, this also implies that all solutions are of the form x + k(5^6) where k is any integer. This is a direct consequence of the structure of our linear Diophantine equation, but it is slightly less intuitive when you're thinking solely about pirates, so take a moment to convince yourself this is true.
With this initial groundwork out of the way, we can understand Whitehead's brilliance. We know the smallest positive number of coconuts is rather large and challenging to comprehend, so what if we look elsewhere for relatively "small" values? What if we go into the negatives? Of course,