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 chcossaboom@gmail.com), 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, we normally want the number of coconuts to be positive, but sometimes, a detour is all we need to get a full picture of the situation. These negative solutions won't be answers to the problem, but they will be solutions to our equation, and they will reveal something rather elegant about our problem.
Fascinatingly, we do have a relatively simple answer when we subtract just one multiple of 5^6 from our minimum answer of 15621 coconuts. Here, N = -4. Having already come up with a formula that includes an n-1 term in general, you probably expected this, but it still begs the question: why -4?
Our goal in math is not only to find a formula and prove that it is true but to also fully understand why it behaves the way it does. Why is -4 important? What about the pirates' process causes an n-1 term to appear? How can we understand why this emerges?
Whitehead comes up with a model using negative coconuts to help him understand why -4 is a solution—and thus why 5^6 - 4 = 15621 is the answer to our puzzle. Before I show you, I'll give you a chance to think about it. What would a pile of -4 coconuts look like? You'll need to use negative and positive coconuts, and your goal is to create a process that shows why -4 works for our situation.
Martin Gardner explains this beautifully, so I'll give him credit where credit is due and show you his explanation of the process verbatim:
"The first sailor approaches the pile of -4 coconuts, tosses a positive coconut to the monkey (it does not matter whether the monkey is given his coconut before or after the division into fifths), thus leaving five negative coconuts. These he divides into five piles, a negative coconut in each. After he has hidden one pile, four negative coconuts remain - exactly the same number that was there at the start! The other sailors go through the same ghostly ritual, the entire procedure ending with each sailor in possession of two negative coconuts, and the monkey, who fares best in this inverted operation, scurrying off happily with six positive coconuts."
Each step of this process is a perfect integer division; no fractional coconuts are required because each pirate ends up with -2 and the monkey receives 6! Thus, we know -4 is a proper answer, and it's as simple as it possibly can be. Not only is each division straightforward and easy to complete, but each division also looks exactly the same: the pirate's role involves taking one coconut for himself and tossing one to the monkey, and this keeps the pile at exactly -4 coconuts the entire time, making it extremely easy for the spectator to see how efficiently the scheme works.
But why -4? As explained above, we want the pirate to be able to take one for himself while giving one to the monkey, so that we can have this fabulous technique of keeping our coconut pile at a constant value. Only with -4 does this work: with -4, the pirate tosses one to the monkey and creates a pile of -5, which is perfectly divided into 5 negative coconuts, where the pirate can take exactly one for himself.
In general, this explains why the n-1 term exists the way it does. Only with n-1 coconuts in the pile to start can the pirate take one for himself and give one to the monkey. This is the only scenario that has no effect on the pile.
Because we discussed above that all of our solutions are multiples of n^(n+1) away from one another, we know that the minimum positive solution is n^(n+1) - (n-1).
Thus, we just proved our formula of n^(n+1) - (n-1) for the minimum number of coconuts for all values of n with this little stroke of genius.
I'll take one more opportunity to summarize what we just did. For the most part, we reasoned backward above, but we need to write our mathematical arguments forward, so I'll present this explanation from the beginning: Idealistically, we would love for our pile to never decrease in size—as then, it could, of course, continue to be divided into perfect integer divisions as much as we would like. What we did was create a scenario where this must happen, even if it required wandering into the negatives. Then, we figured out the number of coconuts that allows us to create this scenario: -4 or more generally, n-1. Next, we found our solution set: k(n^(n+1)) - (n-1) for the number of coconuts we could begin with that work for our pirates and monkeys. [Here, k is a parameter that can take on any integer value, and it symbolizes all the multiples of n^(n+1).] Finally, we realized that the minimum positive solution (and the answer to our puzzle) occurs when k = 1. Thus, our formula is n^(n+1) - (n-1).
That's it! I hope this method was as exciting for you to read as it was for me when I first discovered it. If you'd like to read more of Martin Gardner's commentary, click here. (He has an analogous proof using blue (instead of negative) coconuts that you might want to read.) And remember: if you decide to take on my challenge, I'd love to receive your version of a Monkey-Coconut Proof.
Before we wrap up, it's important to note that this is actually not the original Monkey-Coconut Problem. Here is the actual October 9, 1926 Saturday Evening Post story word for word:
"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.
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?"
Spot the difference? Other than a few grammatical disparities, the only difference here is that the five pirates do not give a coconut to the monkey when they divide up the coconuts in the morning. In the scenario we just worked out, they do.
Thus, the system of equations we use is as following—with no +1 on the last term.
N = 5A + 1
4A = 5B + 1
4B = 5C + 1
4C = 5D + 1
4D = 5E + 1
4E = 5F
The essence of this variation lies in the fact that you now are only making five divisions that involve the monkey and act exactly as they did above, so you now care more about 5^5 (or generally, n^n) than 5^6 (or generally, n^(n+1)). In addition, after those five divisions, your pile must now be a multiple of five. Use those facts and see if you can come up with the numerical answer for the 1926 problem—and also the more general formula in terms of n for this variation.
It's important to discuss why we altered the problem. The altered puzzle that we looked at above ended up being a lot simpler to crack than this variation, and it revealed so much that this one should now be able to fall apart easily. With the previous version under our belt, we now recognize why this one became more complex. Without that version, we might become overwhelmed by the additional complexity here, but with it, we feel equipped and prepared.
In today's article, I went ahead and altered the problem for us at the start, but often, you will have to discover what the simpler version is and change and solve it for yourself. Stay resilient, and always look out for ways that you can make your life easier by removing conditions that you can add back later.
I left the answers to this variation at the bottom of the article.
When you're investigating a problem, you should never stop at simply solving what was originally given to you. Here are a couple of additional questions to answer on your own time:
What if the monkey takes away a different number of coconuts? What if he takes away 2 coconuts at each pirate? What if he takes away 3?
What if the monkey takes away a sequence of some sort? Maybe the first pirate gives him 1 coconut, the second one gives him 2, and so on. What happens then?
Come up with your own sequences, and see if you solve for a formula in terms of the number of pirates for the minimal number of coconuts in your scenarios.
What other ways can you expand the Monkey-Coconut Problem? What questions can you ask, and what answers can you find?
CONCLUSION:
Thank you so much for reading this month's article! I've been working very hard to bring you detailed content that I care about, and this monthly format has given me the ability to focus even more closely on the quality of my articles. I've been running a little more behind schedule than I would like, but I hope this article has been worth the wait! I’m also super excited for you to see what’s in store for July! As always, I am more than willing to receive feedback, questions, and comments about anything in the comment section, in the forum, or in my inbox (chcossaboom@gmail.com). I would also like to take this opportunity to remind you that I am still offering online mentoring sessions to anyone that reaches out over email.
SOURCES:
This article would not have been possible without Martin Gardner's The Second Scientific American Book of Mathematical Puzzles and Diversions, mostly because Martin Gardner was the main mathematician who popularized the problem in the first place but also, of course, because I referred to it a lot throughout my writing process. I highly recommend it—and all of Martin Gardner's books.
If you would like, check out this Numberphile video for more about the Monkey-Coconut Problem. It manages to include many of the same concepts I included in this article and that Martin Gardner discussed in his book:
Thank you again, and see you for the next article!