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