Saturday, September 14, 2002
M I N D  G A M E S


Nemo's sailors and the monkey
Aditya Rishi

Why wait, let's play

Solutions are given two to three weeks after a problem is presented to accommodate entries from remote villages and states, most of which come through snail mail. Do this while you wait: Using one phone call, convey a news to at least 14 persons in 3 minutes, with 1 minute "for each call".

GIVEN n sailors and a pile of coconuts, each man in sequence takes (1/n)th of the coconuts left after the previous man has removed his share (i.e. a_1 for the first man, a_2 for the second,...a_n for the last) and gives m coconuts (same number for each man), that do not divide equally, to a monkey. When all n men have so divided, they divide the remaining coconuts, that are leftover, to the monkey. If m is the same at each division, then, how many coconuts N were there originally? The solution is equivalent to solving the n+1 Diophantine equation (one whose solution must be given in terms of integers).

N=na_1+m

N-a_1-m=na_2+m

N-a_1-a_2-2m=na_3+m...(1)

N-a_1-a_2-a_3-...-a_n-nm=na+m,

which can be rewritten as

N=na_1+m

(n-1)a_1=na_2+m

(n-1)a_2=na_3+m...(2)

(n-1)a_n-1=na_n+m

(n-1)a_n=na+m

 


Since there are n+1 equations in the n+2 unknowns, a_1, a_2,... a_n, a, and N, the solutions span a one-dimensional space (there is an infinite family of solutions parameterised by a single value). The solution to these equations can be given by N=kn^n+1-m(n-1)...(3), where k is an arbitrary integer. For the particular case of n=5 men and m=1 leftover coconuts, six equations can be combined into a single diophantine equation 1,024N =15,625a+11,529...(4), where a is the number given to each man in the last division.

The smallest positive solution in this case is N=15,621 coconuts, corresponding to k=1 and a=1,023. The coconuts are divided as follows:

Removed(r)=0, given to monkey(g)=0, left (l)=15,621; r=3124, g=1, l=12496; 2499, 1, 9996; 1999, 1, 7996; 1599, 1, 6396; 1279, 1, 5116; 5x1023, 1, 0. If no coconut is left for the monkey after the final n-way division, then, the original number of coconuts is

(1+nk)n^n-(n-1)...n odd

(n-1+nk)n^n-(n-1)...n even...(5) The smallest positive solution for case n=5 and m=1 is N=3121 coconuts, corresponding to k=1 and 1020 coconuts in the final division. The coconuts are divided as follows:

Removed(r)=0, given to monkey(g)=0, left(l)=3121; r=624, g=1, l=2496; 499, 1, 1996; 399, 1, 1596; 319, 1, 1276; 255, 1, 1020; 5x204, 0, 0.

The general solution is n = 3 121 + 15625 p with p integer = or > 0, so, the smallest number of coconuts is 3121. Alternative solution: If N is the total number of coconuts, then, let a, b, c, d and e be the size of the piles, respectively, built by the pirate sailors 1, 2, 3, 4 and 5 and r be the size of the piles at the end. We have the following relations: N=5a+1; 4a=5b+1; 4b=5c+1; 4c=5d+1; 4d=5e+1; 4e=5r. By eliminating a, b, c, d and e, we get 1024N=15,625 r + 8404, with N and r integers. The smallest values of N and r are, respectively, 3121 and 204. The solutions to the two problems that sailors faced can be: 3121+15625k coconuts and 12499+15625m coconuts respectively. Equally acceptable are 3121 and 12499.

Readers who got it right were Saurabh Sood, Shruti Bansal, Ravinder Mittal, Munish Kumar Goyal of Maur Mandi at Bathinda, Pankaj Atri, Dr Tarsem Lal of Khanna, Varun Bhardwaj of the PEC, Dr Gurcharna Singh of Ludhiana, S.K. Sood of the NDRI at Karnal and Iqbal Saini. Write at The Tribune or adityarishi99@yahoo.co.in.