“Sailor, Coconuts and Monkeys”– Continued Fractions
This puzzle has appeared in many forms but here is one variant:
Five sailors were cast away on an island. To provide food, they collected all the coconuts they could find. During the night one of the sailors awoke and decided to take his share of the coconuts. He divided the nuts into five equal piles and discovered that one nut was left over, so he threw this extra one to the monkeys. He then hid his share and went back to sleep. A little later a second sailor awoke and had the same idea as the first. He divided the remainder of the nuts into five equal piles, discovered also that one was left over, and threw it to the monkeys. Then he hid his share. In their turn the other three sailors did the same thing, each throwing a coconut to the monkeys. The next morning the sailors, all looking as innocent as possible, divided the remaining nuts into five equal piles, no nuts being left over this time. The problem is to find the smallest number of nuts in the original pile.
There are many ways to solve the above. One way is to express the initial number of nuts in a way that makes it easy to guess the number via trial and error. Another way is to use brute force. Have a counter for the number of nuts and keep incrementing the counter till one reaches a point where the conditions in the puzzle are satisfied.
An elegant way to solve the puzzle is to use “continued fractions”. Let X be the number of nuts in the original pile and let a, b, c, d, e be the # of nuts each sailor takes before the final distribution, next morning. It can be easily seen that the relation between X and e can be written as
256 X = 3125 e + 2101
In the above equation both X and e are integers. Obviously the equation has infinite solutions but the puzzle asks you to get the minimum possible value of X. These type of equations are called “Diophantine equations”, in honor of Diophantus a Greek mathematician of about the third century A.D., who wrote a book about such equations.
In general, to solve an equation of the type ax+by = c, one needs to express a/b as a continued fraction. The penultimate convergent gives the specific solution for the equation, based on which one can write down the general solution. For this puzzle, one needs to determine the general solution for the indeterminate equation 256X-3125 e = 2101.
The following piece of code gives the solution to the above puzzle and all its variants: