05/2/15

# Monkeys and Coconuts

Here is my attempt to solve the monkeys and coconuts problem. The story goes
that five sailors were stranded on an island and had decided to gather some
coconuts for their provisions. They put all the coconuts in one large pile and
went to sleep. One sailor got up and fearing that there could be problems when the
time to came to divide the pile, he divided the pile five ways and noticing that
he has an extra coconut, he gave it to a monkey, and then hid his stash. The other
four sailor repeated the same procedure. When they woke up they noticed that
they had a smaller pile and proceeded to divide into five equal piles, this time
around there were no extra coconut left for the monkey. So the question is: what was
the size of the original pile?

We will denote by $$x_i$$ as the size of the
pile after the $$i$$th sailor has carried out his procedure. In this system $$x_0$$
is original size of the pile. So following this procedure we then proceed as
follows:

$$x_1=\frac{4(x_0-1)}{5}$$
$$\cdots$$
$$x_i=\frac{4(x_{i-1}-1)}{5}$$
$$\cdots$$
$$x_5=\frac{4(x_4-1)}{5}$$

It is important to note that $$x_i \in \mathbb{N}_0$$ for $$i=0\ldots5$$, also $$\frac{x_5}{5}\in \mathbb{N}_0$$. Alternatively, we think of the reverse procedure and express the above as
$$x_4=\frac{5x_5}{4}+1$$
$$\cdots$$
$$x_i=\frac{5x_{i+1}}{4}+1$$
$$\cdots$$
$$x_0=\frac{5x_1}{4}+1$$

Observing that $$x_5$$ has to be divisible by 4 and 5 (last equation in the first system and first equation in the second), one can brute force the solution(s) by the following Julia code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 x=zeros(Float64,5) maxmultiple=1000 for m=1:maxmultiple x=4*5*m #It has to be divisalbe by 4 and 5 for i=4:–1:1 x[i]=5x[i+1]/4+1 end x0=x*5/4+1 if isinteger(x)&&isinteger(x0) println(int(x)) println("m=$m, x₀=$(int(x0))") end end

view raw

gistfile1.jl

hosted with ❤ by GitHub

Which results in

[2496,1996,1596,1276,1020]
m=51, x₀= 3121
[14996,11996,9596,7676,6140]
m=307, x₀= 18746
[27496,21996,17596,14076,11260]
m=563, x₀= 34371
[39996,31996,25596,20476,16380]
m=819, x₀= 49996


This corresponds nicely to the answers that were obtained by rigorous derivation in the video, however it shows how programming can easily find such solutions by brute force.

If one would like to avoid the negative or blue concocts suggested in the video and also preserve the monkey. Below is an alternative derivation. Working through the first system, one gets:

$latex x_{5}={{4\,\left({{4\,\left({{4\,\left({{4\,\left({{4\,\left(x_{0}- 1\right)}\over{5}}-1\right)}\over{5}}-1\right)}\over{5}}-1\right) }\over{5}}-1\right)}\over{5}}=\frac{4^5x_0}{5^5}-\frac{8404}{5^5}$

Hence,
$$5^5x_5=4^5x_0-8404$$.
Realizing the $$x_5$$ has to be necessarily divisible by 5, we denote the final share that each sailor gets in the last division by $$s$$. So our Diophantine equation becomes
$$5^6s=4^5x_0-8404$$.
It will have solutions at $$x_0=3121, 18746, 34371 \ldots= 3121+n5^6 \text{ for } n \in \mathbb{N}_0$$.