Puzzle 1: 15 coconuts.
Sailor 1 takes 7.5 + 0.5 = 8, leaving 7.
Sailor 2 takes 3.5 + 0.5 = 4, leaving 3.
Sailor 3 takes 1.5 + 0.5 = 2, leaving 1.
The monkey gets the final coconut.
Puzzle 2: the original pile had 15621 coconuts:
Time Starting Pile = Monkey + Share + New Pile
---- ------------- ------ ----- --------
1 15621 = 1 + 3124 + 12496
2 12496 = 1 + 2499 + 9996
3 9996 = 1 + 1999 + 7996
4 7996 = 1 + 1599 + 6396
5 6396 = 1 + 1279 + 5116
6 5116 = 1 + 1023 + 4092
(In the last line, note that 1023 represents one sailor's share,
and the 4092 coconuts are divided equally among the other four.
We write the results this way to make the pattern more clear.)
Now that we have the answer handed to us, it's hard to see how we could have found it on our own. But let's try at least to write down the equations that describe the problem. We might want to use the letters A through G to represent the sizes of the pile of coconuts, with A the beginning size, B through F the sizes after each sailor takes a share. To preserve the pattern, we will let G be the number of coconuts left in the final pile after the monkey and the first sailor have taken theirs.
In that case, the following relationships hold:
B = A - 1 - ( A - 1 ) / 5 = (4/5) * ( A - 1 )
C = B - 1 - ( B - 1 ) / 5 = (4/5) * ( B - 1 )
D = C - 1 - ( C - 1 ) / 5 = (4/5) * ( C - 1 )
E = D - 1 - ( D - 1 ) / 5 = (4/5) * ( D - 1 )
F = E - 1 - ( E - 1 ) / 5 = (4/5) * ( E - 1 )
G = F - 1 - ( F - 1 ) / 5 = (4/5) * ( F - 1 )
We can rewrite this system as:
[ 4 -5 0 0 0 0 0 ] [A] [4]
[ 0 4 -5 0 0 0 0 ] [B] [4]
[ 0 0 4 -5 0 0 0 ] * [C] = [4]
[ 0 0 0 4 -5 0 0 ] [D] [4]
[ 0 0 0 0 4 -5 0 ] [E] [4]
[ 0 0 0 0 0 4 -5 ] [F] [4]
[G]
Using standard linear algebra techniques of matrix elimination (but
always using integer arithmetic!) this set of equations yields a
direct relationship between A and G:
4096 * A - 15625 * G = 46116which can then be solved in integers using techniques for Diophantine equations.
To find all integer solutions of the equation, we first note that the coefficients of A and G are relatively prime, so there is a solution. Then we seek solution of the equation with right hand side 1:
4096 * A - 15625 * G = 1by writing the continued fraction:
4096/15625 = 1/(3+1/(1+1/(4+1/(2+1/(1+1/(1+1/(11+1/13)))))))and forcing it to have an odd number of terms:
4096/15625 = 1/(3+1/(1+1/(4+1/(2+1/(1+1/(1+1/(11+1/(12+1/1))))))))and then taking the next to last convergent:
1/(3+1/(1+1/(4+1/(2+1/(1+1/(1+1/(11+1/(12+1/1))))))) = 3783 / 14431whence
4096 * 14431 - 15625 * 3783 = +1
To get a solution to our original problem, we multiply the solution by 46116:
A = 14431 * 46116 = 665499996
G = 3783 * 46116 = 174456828
This is only a particular solution. If (a1,g1) is a solution, then
so is (a1+15625,g1+4096), for example. This means that we can whittle
down our particular solution until we get the smallest solution for
which both values are still positive. Essentially, by whittling
down our solution, we arrive at the smallest solution, which is
(-4,-4), and the smallest positive solution, which is (15621,4092).
The smallest positive solution is what we really want. It says we start with 15621 coconuts, and that in the morning, in the final sharing out, the monkey gets 1, the first sailor gets 1024, and the other four get 4092 coconuts.
The minimal solution is arithmetically legitimate. The first sailor gets up, sees -4 coconuts, gives one (a positive coconut) to the monkey, leaving -5, takes his fair share, which is -1, (a negative) coconut) and goes to bed. This continues all night, and in the morning there are still -4 coconuts, the monkey gets one more (for a total of 6) and each sailor collects -1 coconut. They end up with -2 each, and the monkey has 6, which sums to the original -4.
Puzzle 2 can be generalized. If there are N sailors, and after each division the monkey receives M coconuts, then for any positive K, the number of coconuts could have been:
Number = K * N^(N+1) - M * ( N - 1 )with the smallest positive solution for K=1. Thus, for our original problem, with N=5 and M=1, our solution has the form:
Number = 5^6 - ( 5 - 1 )
Puzzle 3: the original pile had 3121 coconuts:
Time Starting Pile = Monkey + Share + New Pile
---- ------------- ------ ----- --------
1 3121 = 1 + 624 + 2496
2 2496 = 1 + 499 + 1996
3 1996 = 1 + 399 + 1596
4 1596 = 1 + 319 + 1276
5 1276 = 1 + 255 + 1020
6 1020 = 0 + 204 + 816
To solve this problem, we note that the same linear algebra techniques can be used. The left hand side of the defining equation is the same, but the right hand side is different:
4096 * A - 15625 * G = 33616
References: