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}.
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:
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.