Problem
Five sailors are shiporecked on a desert island . The spend all day collecting
coconuts which they put into a large pile. When they are asleep one awakes
and decides to take his share i.e., one fifth. Unfortunately there is monkey
watching so he tosses one to the monkey and then finds the pile divides evenly
for his fifth. he takes his share and hides it. Each sailor then does exactly the
same (including one to the monkey). What is the minimum number of coconuts
needed so this can be done?
Solution
Let total number of coconuts be of the form 5m1+1.
After the first sailor there are 4m1 left.
Let 4m1=5m2+1
After the second sailor there are 4m2 left.
Let 4m2=5m3+1
Let 4m4=5m5+1
After fifth sailor there are 4 m5 left.
Thus we have a reccurence relation
5mi+1-4m1+1=0
with solution
mi=A(4/5)i-1-1.
Using the initial conditions, m1=n, we get
mi=(n+1)(4/5)i-1-1.
m5=(n+1)(256/625)-1 and is an integer. Thus (n+1) must be a multiple
of 625. The smallest multiple is when (n+1)=625 => n=624=m1
Total number of coconuts is 5m1+1=3121
This proof can be extended to "p" sailors, each throwing "q" coconuts to the monkey.
The reccurence relation is then
pmi-(p-1)mi-1+q=0