Coconut Piles

Date: 10/12/98 at 20:47:02
From: Fallon Stillman
Subject: Algebra Puzzle Problem

Here's the problem:

Gilligan and his buddies were stranded on a desert island. Gilligan, 
the professor, Ginger, Mary Anne, the Skipper, and Fred the monkey were 
gathering coconuts. One evening they all rounded up all the coconuts 
they could find and put them in one large pile. Being exhausted from 
working so hard they decided to wait and divide them up evenly in the 
morning. 

During the night Gilligan awoke and separated the nuts into five equal 
piles, with one left over which he gave to Fred the monkey. Gilligan 
took one pile, hid it, pushed the other four back together, and went 
back to his hut. He was followed by Ginger, Mary Ann, the Professor, 
and the Skipper, each dividing them up equally with one remaining nut 
going to Fred. The next morning the remaining nuts were divided up 
equally with one remaining going to Fred. What is the least number of 
coconuts they could have started with?

Date: 10/13/98 at 13:17:58
From: Doctor Rob
Subject: Re: Algebra Puzzle Problem

Hello Fallon,

See the following web page for a related, but not identical(!) 
problem:

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

The difference is that in this problem, the monkey gets his coconut 
before the five-way split, and in the problem on the other Web page, he 
gets it after. Subtle, but important. The equations for your problem 
are these.

Let a be the number of coconuts to start with. After the first person 
and the monkey take their coconuts, the number left is b = (4/5)*(a-1).
After the second person and the monkey take their coconuts, the number 
left is c = (4/5)*(b-1). The third person leaves d = (4/5)*(c-1) 
coconuts. The fourth person leaves e = (4/5)*(d-1) coconuts. The fifth 
person leaves f = (4/5)*(e-1) coconuts. At the end, f = 5*g + 1, where 
g is the number of coconuts each person gets in the morning.

Now when you perform the chain substitution to find the equation 
relating a and g, you get:

   4*(4*[4*(4*[4*(a-1)/5-1]/5-1)/5-1]/5-1)/5 = 5*g + 1

                            1024*a - 15625*g = 11529

For this you have to find the smallest positive integer solution. You 
can follow the model in the cited problem to figure this out. Note 
that g has to be odd, so g = 2*h+1, and:

   512*a - 15625*h = 13577

Now h must be odd, so h = 2*i + 1, and:

   256*a - 15625*i = 14601

You can continue in this way, reducing one or the other of the 
coefficients on the lefthand side until one of them is reduced to 1.  
Then that variable can be expressed as an integer times the remaining 
variable (say z), plus another integer. Undoing all the substitutions 
will express everything as an integer function of z, and the value of 
z which gives the smallest positive a is the one you want. Then you can 
compute that smallest positive value of a.

There is another way, using the Extended Euclidean Algorithm. You can 
use that to find that:

   1024*10849 - 15625*711 = 1

Now multiply by 11529, and reduce the a-value modulo 15625 to get the
answer.

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