I was reading through Martin Gardner’s Colossal Book of Mathematics recently, and thought I’d share an antriguing puzzle he gave and also, what I think to be an interesting way to solve it. The puzzle goes a little something like this
” Five men and a monkey were shipwrecked on a dessert island and they spent the first day gathering cooconuts for food, piled them all up together and then went to sleep for the night.
But during the night, one man wakes up while the others are sleeping. He becomes suspicious of his friends and fears that come morning he won’t get his proper share. So he sneaks off and divides the coconuts into 5 even groups, but finds one left over, so he gives that to the monkey. He takes one of the groups and hides it, puts all the rest of the coconuts back together and goes to sleep. A second man wakes up, also becomes suspicious, and repeats the same procedure, and also having a remainder of one coconut. This happens again with the third, fourth, and fifth men. The next morning they gather round to split the remaining cocounts into five groups, and once again they have a coconut left over, which they give to the monkey. How many coconuts did they start off with?”*
*Actually, Gardner’s version had the last division come out even. The above is the original version of the riddle.
Now, one can use this information to generate a system of equations. Let N be the total number of coconuts, and A, B, C, D, E represent how much each person took as the others slept and let F represent the number distributed to each person at the very end. Using the fact that each was a division of 5 with remainder 1, we can see that.
Using the above equations, one can obtain the following
Which, is actually a very simple Diophantine equation with a well known method of solving which involves utilizing the Euclidean Algorithm
However, I noticed that for this particular problem a much simpler and far less computationally intensive approach exists. I thought to myself, what if I had written the number of coconuts in base 5, and performed all division and subtraction in base 5. So, what can you get from this view point?
Well, firstly, since the first division by 5 leaves a remainder of 1,the number written in base 5 must end with a 1. Yes, that’s all well and good, but that’s not telling us a whole lot. The real advantage of writing in base 5 comes when you go to subtract the first set of numbers the first man hides. First, remember that he gave one coconut to the monkey, changing the last digit 1 into a 0. And then note that dividing by 5 in base 5 simply shifts the digits. Finally, since the second man also gets a remainder of one when trying to divide the coconuts, when one subtracts the number the first man took for himself from the number, the final digit must be 1. Putting all this together, one can determine the second base 5 digit of the solution.
Above is a visual representation of the subtraction. Dashes represent unknown digits involved in the computation. Now, I’m not saying the answer will be 5 digits long. It doesn’t really matter how many dashes you put as the reasoning will be the same. Anyways, what we’re really interested in is the “?”. Now,the question is simple, what can you take from 0 and get 1? Keep in mind that this subtraction is taking place in base 5. If you try 1 you’ll borrow 5 from the next highest digit and subtract to get 4.Similarly, if you try 2 you’ll get 3. Obviously, the only proper value of “?” is 4. Thus,the last two digits of the solution in base 5 are 41.
Now, take a step back and see what we have just concluded. What we have a assumed so far is that two men, one after the other, tried to divide the coconuts into groups of 5, but they each got a remainder of 1 before they took their share. Therefore, what we have just said is that for two men to go through this process and get a remainder of 1,the initial number of coconuts must end in 41 in base 5.
Now, let’s add the third guy in the mix. We know that he too received a remainder of 1. Note that this is the same as saying after the first guy took his share, the next two attempts to divide the coconuts also had a remainder of one. From our conclusion from before, this means that after the first guy takes his coconuts, the remaining number of coconuts must end in 41 base 5. This information allows us to figure out the the third digit of the answer. Keep in mind that the original number of coconuts must also end in 41, and the the first man removed one coconut before taking his share.
So, what replaces the question mark? One might be tempted to answer “0”, but remember that one must be borrowed from 4 to perform the subtraction. Thus the right replacement for “?” is once again”4″.
By now you should see a pattern cropping up in the base 5 representation of the answer. After the last digit is 1, the following digits are 4 for each attempt to divide the coconut resulting in a remainder of 1. Since there were in total 6 attempts to divide the coconuts, we can conclude that the base 5 representation of the answer is 444441, which is 15,621 in base 10. And that’s that.