More Monkeys and Nuts

Date: 06/07/99 at 20:29:17
From: Michael Holt
Subject: Further monkey puzzling - point raised

Dear Dr(s) Math,

I have looked through your archive and found a couple of variants on 
the monkeys sharing nuts theme. None is specifically the same as the 
problem I have (I don't think) although it is very similar to one 
that is answered at some length with formulae and substitution, etc. 
The person who set me this puzzle suggested that it was possible to 
deduce the answer without going to this trouble, and gave me a clue 
which I will add at the end of the puzzle.  

The puzzle:

Five monkeys collect nuts, which they leave in a pile. During the 
night one wakes up and divides the pile into 5. There is one left 
over. He eats the remainder nut and his 1/5 share, and mixes the nuts 
together. The second monkey comes down, divides the pile into 5 with 
one left over, and so it goes on; each left pile divides into 5 with 
one left over and each monkey eats its share plus one. The question 
is, what is the least number of nuts that they had amassed in order 
for this to work? 

The clue:

Apparently, by asking what would have happened if there were 4 more 
nuts collected, the answer can be found without lengthy calculations - 
in fact I am told of somebody who solved it in his head over lunch 
given this advice. I have played around with the idea at length but 
have grown frustrated, as I have not yet solved the problem. What do 
you think?

Thanks for your help; I look forward to hearing from you.

Yours sincerely, 
Michael Holt

Date: 06/10/99 at 12:42:20
From: Doctor Peterson
Subject: Re: Further monkey puzzling - point raised

Hi, Michael. I've been playing with this off and on for a few days, 
and getting confused because of the variations among versions of the 
puzzles! My biggest frustration has been trying to make my answer 
agree with one of the others.

Yes, this clue does help, at least with your version of the puzzle.

Let's suppose that the initial number of nuts is X_0. I divide the 
pile by five and have one left over, so each pile is (X_0-1)/5, and 
the number I leave is

    X_1 = (X_0 - 1) * 4/5

The same process is repeated five times until I have a fairly 
complicated expression for X_5, the number left at the end.

Suppose we set 4 nuts next to the pile and don't touch them through 
the whole process (so they AREN'T part of the dividing by five - 
although that's not quite how you described the hint). The total 
number of nuts is

    Y_0 = X_0 + 4

    Y_1 = X_1 + 4
        = (X_0 - 1) * 4/5 + 4
        = (Y_0 - 4 - 1) * 4/5 + 4
        = (Y_0 - 5) * 4/5 + 4
        = Y_0 * 4/5 - 4 + 4
        = Y_0 * 4/5

So at each step, the total number of nuts is just multiplied by 4/5, 
and we can easily see that

    Y_5 = Y_0 * (4/5)^5

For this to be a whole number, Y_0 must be a multiple of 5^5, and the 
smallest possible value would be exactly that, or 3125. Then X_0 is 
four less than this, or 3121.

Now let's try it out:

    X_0 = 3121
    X_1 = (3121 - 1) * 4/5 = 2496
    X_2 = (2496 - 1) * 4/5 = 1996
    X_3 = (1996 - 1) * 4/5 = 1596
    X_4 = (1596 - 1) * 4/5 = 1276
    X_5 = (1276 - 1) * 4/5 = 1020

This final number, of course, is 4^5 - 4.

This problem is NOT the same as

  http://mathforum.org/dr.math/problems/koestler12.18.97.html   

where the recursion equation is

    X_1 = X_0 * 4/5 - 1

and there is an extra round at the end in which the pile is divided 
into five openly. I don't know whether there's a similar trick here.

Your problem IS, however, the same as

  http://mathforum.org/dr.math/problems/stillman10.12.98.html   

except that there we have the extra round, so the answer using our 
method should be 5^6 - 4 = 15621, and the number each one gets at the 
end should be 4^6 - 4 = 4092.

The equation found there is

    1024*a - 15625*g = 11529

Plugging in our values for a = X_0 and g = X_6/4 (the number each gets 
at the end), we see

    1024*15621 - 15625*1023 = 15995904 - 15984375 = 11529

and we have it.

The trick amounts to a change of variables that simplifies the 
equation. To find such a change, you could try Y = X + a, and see what 
value of a will help:

        X_1 = (X_0 - 1) * 4/5
    Y_1 - a = (Y_0 - a - 1) * 4/5
        Y_1 = Y_0 * 4/5 + a - (a + 1)*4/5

To make the equation simpler, we want

    a - (a + 1)*4/5 = 0
                 5a = 4(a + 1)
                  a = 4

Or, you can just have a flash of insight and try adding four nuts for 
no reason at all.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/