The Monkey and the Coconuts
The puzzle
Five sailors gather a pile of coconuts and agree to divide it in the morning. In the night each sailor wakes in turn, divides the pile into five equal parts with one coconut left over, gives that one to the monkey, hides his own fifth and pushes the remaining four fifths back into a pile. In the morning the pile that is left divides exactly into five with nothing over.
What is the smallest number of coconuts the sailors could have gathered?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Each night the pile goes from N to (4/5)(N - 1). That has to be a whole number five times running.
Hint 2
Try working backwards from a morning pile that is a multiple of 5.
Show the answer Hide the answer
3,121 coconuts.
How to get there
Run it forwards from 3121. First sailor: 3121 - 1 = 3120, a fifth is 624, leaving 2496. Second: 2496 - 1 = 2495, a fifth is 499, leaving 1996. Third: 1996 - 1 = 1995, a fifth is 399, leaving 1596.
Fourth: 1596 - 1 = 1595, a fifth is 319, leaving 1276. Fifth: 1276 - 1 = 1275, a fifth is 255, leaving 1020. In the morning 1020 / 5 = 204 each, with nothing for the monkey. Every step worked out whole, which is the whole requirement.
Finding it: each step maps N to (4/5)(N - 1), so after five nights the pile is (4^5 * N - something)/5^5, and demanding a whole number throughout forces N to satisfy a congruence modulo 5^5 = 3125. The smallest positive solution is 3121 - which is 3125 - 4, and that is no accident: starting with -4 coconuts would let the process run forever, and all solutions are 3121 plus a multiple of 3125.
The technique worth keeping
When each step demands exact divisibility, the whole chain becomes a single congruence. Working backwards from the final condition, or spotting the convenient negative solution, beats searching forwards through the integers.