Look for 4th (Final) Solution ? “The Monkeys and Coconuts” Problem

image

The Monkeys and Coconuts Problem

image
Source:
https://tomcircle.wordpress.com/2013/03/30/monkeys-coconuts-problem/

This famous problem was said to be created by the Nobel Physicist (Quantum Physics) Prof Paul Dirac,  which he told another Chinese Nobel Physicist Prof Li ZhengDao (aka T.D. Lee 李政道)。
Prof Li wanted to test the Chinese young students in the first China Gifted Children University of 13 year-old kids, but none of them could solve this problem.

The first 2 solutions were given by Prof Paul Richard Halmos,  the 3rd solved by myself using the Singapore Modelling Math (a modified graphical version of Arithmetics “算术” from the traditional Chinese Math taught in late 1960s Singapore Chinese Secondary 1 “中学数学”).

1st Solution: Higher Math (Sequence)

https://tomcircle.wordpress.com/2013/03/30/solution-1-monkeys-coconuts/

2nd Solution: Linear Algebra (Eigenvalue and Eigenvector)

https://tomcircle.wordpress.com/2013/03/30/solution-2-monkeys-coconuts/

Prof Halmos did not explain well his eigenvalue equation. I try below to explain his beautiful solution.

Notice the 5 iterations (from inner brackets to outer brackets) of the linear transformation
\boxed {S(x) = \frac {4}{5} (x -1)}

image

It means:

Let x (the coconuts) be the vector under the transformation of S(x), which simply is
coconuts less 1, then give 4/5 of remaining coconuts to next monkey”.

Since before and after each iteration (transformation), the coconut ‘state’ remains unchanged (analogy: a balloon before and after the ‘transformation’ deflation is still a balloon), because the next iteration is still the same as before as:
coconuts less 1, then give 4/5 of remaining coconuts to next monkey”.

By Linear Transformation definition:
Ax= \lambda x
where the transformation matrix A here is S(x).
The ‘unchanged’ transformation implies the vector x is unaffected, its eigenvector (x) after S(x) is neither shortened nor lengthened by the eigenvalue \lambda.
that is \boxed {\lambda = 1}

Hence,
S(x) = 1.x = x

\frac {4}{5} (x -1) = x
Solving this equation, we get
\boxed {x = -4}

But coconuts cannot have -4 quantity!

The 5th iteration, S^{5}(x) is:
image

This whole expression must give a whole number for coconuts, then the inner x divided by 5^5 must be also a whole number.
That is possible only if x is multiple of 5^5

The solution (x = – 4) is therefore amongst the multiples of 5^5.
We write in Modular math expression:
\boxed {x \equiv -4 \mod (5^5)}

The minimum positive x :
\displaystyle x = 5^{5} - 4 = 3121 [QED]

Note:
I have a revelation just now on the “Monkeys & coconuts” — subconscious at work 🙂
\boxed{x = - 4} is really the answer from Prof Halmos’s 2nd solutions, because it tells us that we need, at the initial stage, to ‘borrow’ 4 ” ( the meaning of – 4 ) more coconuts to be divided into 5 groups.

If go 6 iterations, then
x =5^{6} - 4 = 15,625 - 4 = 15,621

In General, for m monkeys (iterations) is
x = 5^{m} - 4
or
\boxed { x = - 4 \mod (5^m) }

https://tomcircle.wordpress.com/2013/03/30/solution-2-monkeys-coconuts/

Ref: Intrinsic meaning of eigenvectors and eigenvalues

3rd Solution: Singapore Modelling Math for PSLE (Primary 6)

https://tomcircle.wordpress.com/2013/03/30/solution-3-best-monkeys-coconuts/

4th Solution:
From the 2nd solution, we can deduce the general solution for:
m Monkeys (iterations)
c number of Coconut groups at each iteration
r Remaining coconuts at each iteration (r < c) thrown to sea

The initial quantity of coconuts (x) :

\boxed { x = - (c - r) \mod (c^{m}) }

Verify: m =7, c = 6 , r =3
x = - (6-3) \mod (6^{7}) = - 3 \mod (6^7)
Minimum x = 6^{7} - 3  =279,933

Ref: here is another version of the same problem:
http://qedinsight.wordpress.com/2011/05/13/the-coconut-problem/

Application:

This problem can be extended to the division of heritage (H units of assets) of a richman to m closed relatives, at each iteration divide H into c groups, left 1 unit for Charity.

Then
H = - (c - 1) \mod (c^{m})

If 3 relatives, divide into 2 groups left 1 unit to Charity,
Minimum H[ -(2-1) \mod 2^{3} ] = 2^{3} -1 = 7 units

1st: wife : 7/2 = 3 …1
2nd: son: 7 – 3 -1 = 3 => 3/2= 1…1
3rd: grand-son: 3-1-1= 1 => 1/2 = 0 …1

Left: 7 – 3 – 1- 0 – (1+1+1) = 0

If 1 unit = $1,000,000
The min. heritage is $7 million:
Wife gets $3 m,
Son gets $1 m,
nothing for Grandson (not to spoil him),
Charity benefits $3 m.

Advertisements

Solution 3 (Modelling): Monkeys & Coconuts

Let x the min number of coconuts initially.

1st monkey took “a” coconuts away, 2nd monkey “b” coconuts….5th monkey took “e” coconuts.

[a][a][a][a][a] + 1 =x

Loan 4 coconuts to the initial pool of x coconuts to divide by 5 evenly at each monkey.

[a][a][a][a][a] + 1 + 4 = [a][a][a][a][a] + 5 = x+4 = X (inflated x by 4 )
1st Monkey: [a’][a’][a’][a’][a’] = X
a’ = \frac {1}{5} X

… Left 4a’= \frac {4}{5} X
[a’][a’][a’][a’] => [b][b][b][b][b]

b= \frac{1}{5} .4a’ = \frac{4}{25}X

… Left 4b= \frac {16}{25}X
[b][b][b][b] => [c][c][c][c][c]
c=\frac {1}{5} .4b= \frac {16}{125}X
… Left 4c= \frac {64}{125}X
[c][c][c][c] => [d][d][d]d][d]
d= \frac {1}{5}.4c= \frac {64}{625}X
… Left 4d= \frac {256}{625}X
[d][d][d]d] => [e][e][e][e][e]
e= \frac {1}{5}.4d= 256.(X/3125)
Since e is integer
=> X = 3125 or multiples of 3125
Minimum X=3125
x+4 = 3125
x= 3121 = minimum Coconut initially.

Note: This solution used the Singapore Modelling Math taught in all Primary Schools for 11-year-old pupils.

Solution 2 (Eigenvalue): Monkeys & Coconuts

Solution 2: Use Linear Algebra Eigenvalue equation: A.X = λ.X

A =S(x)= \frac{4}{5}(x-1)  where x = coconuts

S(x)=λx

Since each iteration of the transformation caused the coconut status ‘unchanged’, which means λ = 1 (see remark below)

\frac{4}{5}(x-1)=x
We get
x = – 4

Also by recursive, after the fifth monkey: S^5 (x) = (\frac{4}{5})^5 (x-1)- (\frac{4}{5})^4-(\frac{4}{5})^3- (\frac{4}{5})^2- \frac{4}{5}

S^5 (x) = (\frac{4}{5})^5 (x) - (\frac{4}{5})^5 - (\frac{4}{5})^4 - (\frac{4}{5})^3+(\frac{4}{5})^2 - \frac{4}{5}

 

5^5 divides (x)

Minimum positive x= – 4 mod (5^{5} )= 5^{5} - 4= 3,121 [QED]

 

Note: The meaning of eigenvalue  λ in linear transformation is the change  by a scalar of λ factor (lengthening or shortening by λ) after the transformation. Here

λ = 1 because “before” and “after” (transformation A)  is the SAME status (“divide coconuts by 5 and left 1”).

Monkeys & Coconuts Problem

5 monkeys found some coconuts at the beach.

1st monkey came, divided the coconuts into 5 groups, left 1 coconut which it threw to the sea, and took away 1 group of coconuts.
2nd monkey came, divided the remaining coconuts into 5 groups, left 1 coconut again thrown to the sea, and took away 1 group.
Same for 3rd , 4th and 5th monkeys.

Find: how many coconuts are there initially?

Note: This problem was created by Nobel Physicist Prof Paul Dirac (8 August 1902 – 20 October 1984). Prof Tsung-Dao Lee (李政道) (1926 ~) , Nobel Physicist, set it as a test for the young gifted students in the Chinese university of Science and Technology (中国科技大学-天才儿童班).