Coconuts of Diophantus; a computer solution of a classic problem. Carl J. Patterson.
One of the more delightful aspects of computing is that it can be an artful blend of analytical problem formulation and elegant number crunching. A clear illustration is given in the famous problem of the castaways and the coconuts. There are many variations of the problem, and I shall present here a representative version and a general algorithm to solve it.
Coconut Problem
Five men were stranded on a desert island where the only food they could find was coconuts. These were gathered all day, and by nightfall the men were so tired that, rather than eating, they decided to wait till the next day to split up the coconut feast. The most suspicious member of the lot arose after he was certain his fellows were asleep and divided the pile of coconuts into five equal shares, took his share and hit it. To conceal his act he pushed the other shares back into one large pile. But lo, a single coconut remained. This one he gave to the only other being the men had found on the island, a monkey. One by one, (in order of how suspicious each was), the other men arose and repeated the actions of the first man, each giving a single remaining coconut to the monkey. (The monkey learned quite quickly to stay around as each man arose.)
Upon arising the next day the pile of coconuts was divided into five equal shares, but the monkey was disappointed: there was no coconut remaining. Our problem is to find out just how many coconuts there were and how many each man got.
Formulate
OK, hackers, don't start writing code just because you can visualize a couple of FOR loops to get you started. Instead try making some observations about the problem. For example, the solution requires integers (the men didn't have a machete with which to make fractional coconuts).
Another observation: maybe the solution isn't unique, so we should look for the smallest number that satisfies the problem. Next, one might consider how the problem should be formulated: by congruences (for number theorists); by trial and error (for hardcore computerists); or by considering steps taken in the course of the problem and carrying them, by pencil and paper, as far as they will lead. This last approach is the method we shall use.
If there were X coconuts at the beginning, it is clear that after the first man took his share, 4/5(X-1) coconuts remained. This remaining amount becomes a new X for the second man. If we call this X', then after the second man takes his share there remain 4/5(X'-1) or 4/5 (4/5(X-1)-1) coconuts. If we continue in this manner we will generate the information in Table 1.
Because the men were able to divide the remaining coconuts evenly in the morning, we know that the last expression is divisible by 5. So with a little algebra we determine that (4/5).sup.5.X-4(1-(4/5).sup.5 = 5Y
The term 5Y expresses the divisibility of the righthand side by 5. Also, since the righthand side of the equation represents a number and the 5 in the lefthand side represents the number of men, Y represents the number of coconuts per man in the final division of coconuts. Simplifying the above equation a bit 1024X-15625Y = 8404 with X, the original number of coconuts, and Y, the number each man gets in the final division, both being integers.
Solve It
Rather than a trial and error or brute force technique, I wrote a program to solve the problem based on Diophantine analysis. In particular, the algorithm the program uses is based on continued fractions. The program can handle equations of the form AX+BY = C or AX-BY = C with minor restrictions on A, B, and C. The program listing offers a bit of explanation, but for now it suffices to say that the second alternative is selected by inputting a problem type of 0. The variables A, B, and C are given by 1024, 15625, and 8404, respectively. The answer is given by X = 91174996+t15625 and Y = 5975244+T1024 where t is any integer, including negative. If this seems to imply that there is an infinite number of solutions, there is. For all equations of this form there is either an infinite number of solutions or there is none, and the program is capable of informing you if there is none. To find the smallest number of coconuts that satisfies the problem, we look for t to satisfy t >-91174996/15625 = -5835.2 and t>-5975244/1024 = -5835.2. Picking t equal to 5835 and using it in the expression for X and Y we get, X = 3121 and Y = 204. So originally there were 3121 coconuts.
Solve It Completely
To complete the solution, the first man received 1/5(3121-1) or 624 coconuts plus the 204 he received in the final division, or 828 coconuts. (The second man received 1/5(4/5(3121-1)) or 499, plus 204 for 703 coconuts. If we continue like this, we generate the information in Table 2.
For those of you who added up the column under total share and noticed the total was only 3116, don't forget the monkey, who got five coconuts, bringing the total of 3121.
Keep Going
The problem is now completely solved, and its formulation as well as its solution affords pleasurable musings. You may wish to look at variations on the theme--more men or more monkeys, for example. If the problem is properly formulated, the program should be able to handle these versions also.
The program is written in DEC's Basic Plus, but I tried not to use too many implementation-dependent features. Two sections, with line numbers 960 to 1010 and line numbers 1080 to 1150 were necessary because integers are limited to 32,768 on the system I was using. The function NUM1$(X) is a system function that takes the numeric value of X and makes a string containing numerals that represent that value. The function PROD$ takes the product of its first two arguments, which must be strings, and returns a string with the number of significant places determined by its third argument.