Five men, a monkey, and some coconuts
Five men crash-land their airplane on a deserted island in the South Pacific. On their first day they gather as many coconuts as they can find into one big pile. They decide that, since it is getting dark, they will wait until the next day to divide the coconuts.
That night each man took a turn watching for rescue searchers while the others slept. The first watcher got bored so he decided to divide the coconuts into five equal piles. When he did this, he found he had one remaining coconut. He gave this coconut to a monkey, took one of the piles, and hid it for himself. Then he jumbled up the four other piles into one big pile again.
To cut a long story short, each of the five men ended up doing exactly the same thing. They each divided the coconuts into five equal piles and had one extra coconut left over, which they gave to the monkey. They each took one of the five piles and hid those coconuts. They each came back and jumbled up the remaining four piles into one big pile.
What is the smallest number of coconuts there could have been in the original pile?
Let the original pile have n coconuts. Let a be the number of coconuts in each of the five piles made by the first man, b the number of coconuts in each of the five piles made by the second man, and so on.
Writing a Diophantine equation to represent the actions of each man, we have
n = 5a + 1
n + 4 = 5(a + 1)
4a = 5b + 1
4(a + 1) = 5(b + 1)
4b = 5c + 1
4(b + 1) = 5(c + 1)
4c = 5d + 1
4(c + 1) = 5(d + 1)
4d = 5e + 1
4(d + 1) = 5(e + 1)
Hence n + 4 = 5 × (5/4)4 (e + 1), and so n = (55/44) (e + 1) − 4.
Note that, since 5 and 4 are relatively prime, 55/44 = 3125/256 is a fraction in its lowest terms. Hence the only integer solutions of the above equation are where e + 1 is a multiple of 44, whereupon d + 1, c + 1, b + 1, and a + 1 are all integers.
So the general solution is n = 3125r − 4, where r is a positive integer, giving a smallest solution of 3121 coconuts in the original pile.
Remarks
It's clear from the form of the equations that we can generalize this result. Given m > 2 men in the airplane, the smallest solution would be mm − (m−1) coconuts. This follows because, for m > 2, m and m−1 are always relatively prime. (Any divisor of m and m−1 must also divide their difference.)
