Sailors, monkey and coconuts

According to MathWorld, the smallest positive solution is $15621$ coconuts. The smallest positive solution if the coconuts divide evenly at the end, with none left over for the monkey, is $3121$. The link gives an outline of the solution to this classic Diophantine problem. A detailed solution can be found in this PDF, alone with the slick shortcut solution:

By inspection $-4$ is a solution: when it’s divided into $5$ piles of $-1$ with $1$ left over for the monkey, and one of the piles is removed, $-4$ coconuts remain for the next division. It’s also not too hard to see that $5^6=15625$ can be added to any solution to obtain another, since the pile is divided into $5$ piles $6$ times; thus, $15621$ is a solution.

Let $x_k$ be the number of coconuts left after the $k$-th sailor has divided them into $5$ piles, hidden his pile, and given the remaining coconut to the monkey. Hence,

$$x_{k+1} = \frac 45 (x_k - 1) = \frac 45 x_k - \frac 45$$

and, thus,

$$x_k = \left(\frac 45\right)^k x_0 - \sum_{\ell=1}^k \left(\frac 45\right)^{\ell} = \cdots = (x_0 + 4) \left(\frac 45\right)^k - 4$$

After the $5$ sailors' interventions, one coconut is given to the monkey and the remaining ones are divided evenly in $5$ piles. Thus, $x_5 - 1$ is not merely a nonnegative integer, but also a multiple of $5$, i.e., there exists $m \in \mathbb N$ such that $x_5 - 1 = 5 m$. Thus, the initial number of coconuts is given by

$$x_0 = - 4 + \frac{5^6}{4^5} (m+1)$$

The first natural $m$ that makes $x_0$ integral is $m = 4^5 - 1$. The first admissible $x_0$ is thus $$x_0 = 5^6 - 4 = \color{blue}{15621}$$

Computing $x_0, x_1, \dots, x_5$ in Haskell,

λ> take 6 $ iterate (\x->(div (4*(x-1)) 5)) 15621
[15621,12496,9996,7996,6396,5116]

Note that $x_5 = 5116 = 1 + 5 \cdot 1023$.

Derivation: how does a mathematician change a lightbulb? Level the house thereby reducing it to a previously solved problem.

Solve it without feed the monkey(s) first, just n men no monkeys. It's clear that $n^{n+1}$ can be divided by each of the $n$ man and again in the morning. So $n^{n+1}$ works here. In fact once you have a solution to the original problem, any solution, you can add $n^{n+1}$ to it and get another solution to the original problem.

Find a number $x$ you can subtract $c$ from, $c$ is the number of monkeys, then divide what remains by $n$ and then multiply by $n-1$ but the final answer is what you started with $x$.

$\dfrac{(n+1)(x-c)}{n} = x$, so $x$ is $-c(n-1)$ and $-c(n-1)$ is a solution, though an abstract solution, it is negative. Once you add any multiple of $n^{n+1}$ you get all the solutions, for there are an infinite numbers of solutions.

$$ M \cdot [n^{n+1}] - c(n-1) $$ To show that all solution s look like this, assume you have any two solutions and show that their difference is divisible by $n$, namely $n+1$ times.

Retired Professor Lynn Garner (former chairman of the BYU Mathematics Faculty), has found a general analytical solution to an extension of this problem, in m men.

His solution (which I have published by his permission from our private correspondence) may be found here (my article also includes a few solutions to the standard problem in 5 men): https://aaabit.com/Coconuts

In outline—

Let $n = n_0$ be the initial number of coconuts gathered.

$$n_1={m−1\over m}(n−1)$$

$$…$$

$$n_m=\left({m−1\over m}\right)^{mn}− \left\{\left({m−1\over m}\right)^{m−1}+…+\left({m−1\over m}\right)^2+{m−1\over m} \right\}$$

Rewriting this expression, summing over the geometric progression using $1+r+r^2+…+r^{m−1}={1-r^m\over 1−r}$, we get the number of coconuts left in the morning which is a multiple of m. Then let q be a positive integer, and set:

$$n_m= \left({m−1\over m} \right)^{m}n − (m−1)\left( {m^m−(m-1)^m\over m^m} \right)=qm$$

Solving for n, we get:

$$n=1−m+m^m\left(m−1+qm\over (m−1)^m\right)$$

In order for n to be an integer, we only need the quotient to be an integer. So let r be an integer and set:

$${m−1+qm\over (m−1)^m}=r$$

Isolating the qm term, and noting that $m$ and $m−1$ are relatively prime; we deduce that for some s:

$$(m−1)^{m−1}r−1=sm$$

$$(m−1)^{m−1}r=sm+1$$

That is, some multiple of $(m−1)^{m−1}$ is also one more than a multiple of m. That such integers r and s exist follows from the fact that $m$ and $m−1$ are relatively prime. For example,

m=3 r=1 s=1
m=4 r=3 s=20
m=5 r=1 s=51
m=6 r=5 s=2604
m=7 r=1 s=6665
m=8 r=7 s=720600

etc. We can easily prove that $r=1$ when m is odd, whereas $r=m−1$ when m is even; since $m−1$ is congruent to $-1$, so to an even power (m odd) is congruent to $1$, and to an odd power (m even) is still $-1$, so needs another factor of $m-1$ to square it. Therefore:

$$n=rm^m−m+1$$ $$r=\begin{cases}m\ odd:1\\m\ even:m−1\end{cases}$$

Examples of minimum possible solutions, where other solutions may be given by adding some multiple of $m^{m+1}$:

m=1    n=1
m=2    n=3
m=3    n=25
m=4    n=765
m=5    n=3121
m=6    n=233275
m=7    n=823537
m=8    n=117440505
m=9    n=387420481