The Monkey and Coconut Problem

The Monkey and Coconut Problem

Three sailors, who live together with a monkey as shipwrecked on an abandoned island, collected one day a heap of coconuts, which is to be divided in the early of the next day among the sailors. Sometime in the night one of the sailors gets up and divides the pile into 3 equal parts. A coconut remains, which he gives to the monkey. Afterwards he hides his share and puts the remaining coconuts together again to a heap. Later that night, the other two sailors also get up and repeat the work of the first sailor. The following morning the three sailors get up, divide the remaining pile into three parts. Again a coconut remains, which they give to the monkey. How many coconuts were originally in the heap?

Also, a general solution is to be found for n coconuts, k sailors and m monkeys.

Derivation

So, let us start writing down the given information in a more mathmatical form, but without too much strict math. To summarize, we have a number of \begin{align} k \in \mathbb{N_+} \backslash { 1} \end{align} sailors (only one sailor is not interesting, so we remove this case from our discussions), the number of coconuts which were collected by the sailors before the night \begin{align} n \in \mathbb{N_+}, \end{align} and the number of monkeys \begin{align} m \in \mathbb{N_+}, \ m < k. \end{align}

The first sailor who wakes up first divides the number of coconuts by the number of sailors. He gives the remaining coconuts to the monkeys. This results in k shares, which have the size (n-1)/k. The first sailor buries his (stolen) share, leaving behind the following number of coconuts: \begin{align} n_1 = \frac{n-m}{k}(k-1)=(n-m)\frac{k-1}{k} \label{eq:n1} \end{align} The second sailor, who wakes up, repeats the procedure of the first one: Then, the third sailor wakes up and does the same again: So, for the i-th sailor, with , we find the general recursive rule: For every sailor, we subtract off one from the previous number and then multiply by . This relationship can also be expressed as (for ): For our convenience, we define the initial number of coconuts as . Hence, we can write for all as:

In order to find an initial amount of coconuts , we have to ensure that all are dividable by with a remainder of one (which is given to the monkey). Hence, it has to be ensured that: Remember that in the morning, after all sailors have woken up, the remaining coconuts are divided among all sailors. So, as stated above, also has to have a remainder of one when divided by . For it is sufficient to ensure that is a multiple of plus . For larger , everything gets slightly more difficult. We have to find an for Eq. \eqref{eq:iterativeForm} such that Eq. \eqref{eq:forallI} is satisfied. To do so, let us first simplify the complicated expression (for now assuming ) in Eq. \eqref{eq:iterativeForm} using the geometric series specified in the Appendix:

Now we can try to find an that suffices Eq. \eqref{eq:forallI}:

Note that we cannot get rid of the term , since the power of the fraction is smaller than one and not a natural number. The left-hand side of Eq. \eqref{eq:modulo} should hence be a multiple of . This can be expressed as:

where for now we choose and then solve for :

Although we can now compute different values for according to \eqref{eq:firstN} which will suffice Eq. \eqref{eq:modulo}, we can observe a problem: For example, with and we receive a value of , which – although it suffices Eq. \eqref{eq:modulo} – is not a natural number. This is due to the fraction in Eq. \eqref{eq:firstN}. However, we show in the Appendix that numerator and denominator are relatively prime to each other, hence, the fraction cannot be reduced. So, in order to obtain a natural number for , we can drag the denominator to and assume that is a multiple of it by replacing with :

Note that in Eq. \eqref{eq:finalSolution} we have an expression which is independent of and hence fulfills Eq. \eqref{eq:forallI} for all .

You might have noticed that we actually only solved the problem for , since the sum in Eq. \eqref{eq:probWithSum} is only evaluated for . However, Eq. \eqref{eq:forallI} demands for all – so also for and – that . We can directly see that Eq. \eqref{eq:finalSolution} is also a valid solution for the case and we can furthermore show that also the case specified in Eq. \eqref{eq:n1} is only a special case of Eq. \eqref{eq:firstN}, with:

and:

Hence, if we insert into Eq. \eqref{eq:casen1} we obtain Eq. \eqref{eq:firstN} which then leads to the general solution in Eq. \eqref{eq:finalSolution}.

Verification

To make sure that we have obtained a correct solution, let us run some simulations where we try many values for and check if these values correspond to Eq. \eqref{eq:finalSolution}.

# Number of Sailors
k <- 3

# Number of Monkeys on the island
m <- 2

# Range of coconuts to try (1 2 3 ... n_max):
n_max <- 1e6

# There should be less monkeys than sailors
stopifnot(m < k)

# Recursive function simulating the sailors behaviour
divideCocos <- function (n, sailor) {
  if(sailor < 0) return (TRUE)
  if((n %% k) == m) return (divideCocos((n-m) / k * (k - 1), sailor - 1))
  FALSE
}

tryN <- sapply(1:n_max, function(i) divideCocos(i, k))
realN <- which(tryN)

# Compare with formula
formulaNCocos <- function(q, k, m) {
  q*k^(k+1) - m*(k-1)
}
formulaN <- sapply(1:length(realN), formulaNCocos, k, m)

# Check if the simulated results fit to the formula we obtained
anyError <- which(formulaN != realN)
stopifnot(length(anyError) == 0)

cat("Formula appears to be correct!!!\n")
cat("\nSome numbers n that work:", realN[1:min(25, length(realN))])

We can run this R-script for different settings of sailors and monkeys and check if there are any differences between the simulated results and the formula. In such a case, the formula would be wrong. But after trying several combinations we can be quite confident that the formula is correct (although the computer simulation is certainly not a real proof). For our initial setup with sailors and monkeys we get the following result with the R-script:

Formula appears to be correct!!!
Some numbers n that work: 79 160 241 322 403 484 565 646 727 808 889 970 1051 1132 1213 1294 1375 1456 1537 1618 1699 1780 1861 1942 2023

Summary

As we found, it is possible to find a general algebraic solution to the coconut and monkey problem described in the beginning. The number of coconuts that were initially collected, for sailors and monkeys, is given by:

where is a natural number larger than 0, since there are infinitely many solutions.

Appendix

Geometric Series

In this appendix we briefly mention several properties of the geometric series which are required for the derivations in other dependencies. For and the geometric series can be derived as:

More generally, the geometric series can be written as:

Special cases

If the series starts with we retrieve:

For we obtain: \begin{equation} \begin{split} a_0 \sum_{i=j}^{N-1} {1^i} = a_0 (N-j) \end{split} \label{eq:geometricSeries3} \end{equation} For an infinite series with , convergence is achieved for values : \begin{equation} \begin{split} a_0 \sum_{i=j}^{\infty} {q^i} = a_0 \frac{q^j}{1-q} \end{split} \label{eq:geometricSeries4} \end{equation}

Powers of neighbored natural numbers are relatively prime

In this appendix we briefly show that two neighbored natural numbers and are relatively prime, as well as their powers. This can be done with a proof by contradiction: Let us assume that there exists a divisor for which: \begin{align} k &= q \cdot t
k+1 &= r \cdot t \end{align} This also implies: \begin{align} r > q
r - q \geq 1 \end{align} We can also write:

Since we required , we have a contradiction, which means that the two neighbored numbers and are relatively prime and a fraction containing these two numbers in the numerator and denominator cannot be reduced. Furthermore, since the prime factorization of and returns two disjoint sets of primes and (), it can also be trivially shown that the powers and , with are also relatively prime.

Markus Thill

Markus Thill
I studied computer engineering (B.Sc.) and Automation & IT (M.Eng.). Generally, I am interested in machine learning (ML) approaches (in the broadest sense), but particularly in the fields of time series analysis, anomaly detection, Reinforcement Learning (e.g. for board games), Deep Learning (DL) and incremental (on-line) learning procedures.

Deriving a Closed-Form Solution of the Fibonacci Sequence using the Z-Transform

The Fibonacci sequence might be one of the most famous sequences in the field of mathmatics and computer science. Already high school stu...… Continue reading