This Riddler problem is about divisibility… of coconuts!

Seven pirates wash ashore on a deserted island after their ship sinks. In order to survive, they gather as many coconuts as they can find and throw them into a central pile. As the sun sets, they all go to sleep.

One pirate wakes up in the middle of the night. Being the greedy person he is, this pirate decides to take some coconuts from the pile and hide them for himself. As he approaches the pile, though, he notices a monkey watching him. To keep the monkey quiet, the pirate tosses it one coconut from the pile. He then divides the rest of the pile into seven equally sized bunches and hides one of the bunches in the bushes. Finally, he recombines the remaining coconuts into a single pile and goes back to sleep. (Note that individual coconuts are very hard, and therefore indivisible.)

Later that night, a second pirate wakes up with the same idea. She tosses the monkey one coconut from the central pile, divides the pile into seven bunches, hides her bunch, recombines the rest, and goes back to sleep. After that, a third pirate wakes up and does the same thing. Then a fourth. Then a fifth, and so on until all seven pirates have hidden a share of the coconuts.

In the morning, the pirates look at the remaining central pile and notice that it has gotten quite small. They decide to split the pile into seven equal bunches and take one bunch each. (Note: The monkey does not get one this time.) If there were N coconuts in the pile originally, what is the smallest possible value of N?

Here is a short solution:

[Show Solution]

Suppose there are $M$ coconuts in the central pile when one of the pirates takes their turn. One coconut is given to the monkey, the rest are divided into seven equal piles, and six of the piles are returned to the central pile. Mathematically, this corresponds to the function: $f(M) = \tfrac{6}{7}(M-1)$. In other words, every time a pirate visits the central pile, the number of coconuts shrinks as $M\mapsto f(M)$.

After seven visits, the initial number of coconuts has shrunken to a (positive) number that is divisible by $7$. We can express this as:

\[

f^{(7)}(N) = f(f(f(f(f(f(f(N))))))) = 7k

\]Expanding this formula, it is a linear equation relating $N$ and $k$, which is:

\[

N=\frac{5764801 k+3261642}{279936}

\]The problem asks us to find the smallest $N$. This is equivalent to finding the smallest positive integer $k$ such that $N$ is an integer. This sort of problem is called a linear congruence equation and it can be solved using modular arithmetic. In Mathematica, the command is:

`Reduce[5764801 k + 3261642 == 0, k, Modulus -> 279936]`

It can also be solved using WolframAlpha. The smallest solution is $k=39990$, which leads to $N=823537$. That’s a lot of coconuts!

If you’d like to learn more about how to solve such problems (what is modular arithmetic anyway!?) then read on!

[Show Solution]

I’ll assume you already read the above solution. In order to understand where the solution comes from, we need to take a brief detour into the world of modular arithmetic…

### Detour: modular arithmetic

I’ll illustrate the technique using a simpler example. Let’s find the smallest positive $k$ such that $\frac{5k+2}{3}$ is an integer. Put another way, we want $5k+2$ to be divisible by 3. This is written as:

\[

5k+2 \equiv 0 \pmod{3}

\]The only thing that matters when we’re working “modulo 3” is the remainder upon division by 3. For example, the numbers $\{\dots,-3,0,3,6,\dots\}$ are all equivalent to 0 mod 3 because they are divisible by 3. Likewise, the numbers $\{\dots,-2,1,4,7,\dots\}$ are all equivalent to 1 mod 3 because they have a remainder of 1 (i.e. they are of the form $3k+1$ for some integer $k$). When adding or multiplying numbers together, we can replace them by any equivalent numbers modulo 3 and this doesn’t change the result. So, for example:

\[

5k+2\equiv 0 \pmod{3}

\quad\text{is the same as solving}\quad

2k\equiv 1\pmod{3}

\]Naturally, because we’re working modulo 3, we only need to try $k=\{0,1,2\}$, and we find the solution is $k\equiv 2$. This means, of course, that we could have used any $k$ of the form $3m+2$ and it would have also worked. The smallest positive $k$ is therefore $k=2$, and this works; $5\times 2+2=12$, which is divisible by 3.

Let’s turn our attention to the question of solving $ak\equiv b \pmod{m}$. Here, $a$, $b$, $m$ are fixed, and we want to solve for $k$. This is called a linear congruence equation and it is a well-known concept in number theory. I’ll summarize the key results below.

First, note that there need not be any solutions at all! For example, $5k\equiv 2 \pmod{15}$ clearly has no solution, since $5k$ can only be equal to $\{0,5,10\}$ modulo 15. There can also be multiple solutions. For example, $4k\equiv 2 \pmod{6}$ has solutions $k\equiv 2$ or $k\equiv 5$. In general,

- Let $g=\textrm{gcd}(a,m)$ (greatest common divisor). Then the equation $ak\equiv b\pmod{m}$ has a solution if and only if $g$ divides $b$.
- If $k_0$ is a particular solution, then there are $g$ solutions in total, given by: $\left\{k_0,\, k_0+\frac{m}{g},\, k_0+\frac{2m}{g},\,\dots,\,k_0+\frac{(g-1)m}{g} \right\}$
- The modified equation $(\tfrac{a}{g})k \equiv \tfrac{b}{g} \pmod{\tfrac{m}{g}}$ reduces to the case $g=1$ because $\textrm{gcd}(\tfrac{a}{g},\tfrac{m}{g})=1$ by definition. Consequently this modified equation has a unique solution, which can serve as $k_0$ for the original equation.
- To solve the case $g=1$, Bézout’s Identity states that there must exist $s$ and $t$ such that $sa+tm=1$. Then, we have $bsa+btm=b$, which implies that $k_0 = bs$ solves our equation. Bézout’s Identity can be solved via the Extended Euclidean Algorithm.

### Back to coconuts!

Our goal was to find the smallest positive integer $k$ such that $N=\frac{5764801 k+3261642}{279936}$ is also an integer. This amounts to solving the linear congruence equation

\[

5764801k+3261642 \equiv 0\pmod{279936}

\]Reducing and rearranging this is equivalent to:

\[

166081k \equiv 97590\pmod{279936}

\]The first thing to observe is that $279936=2^7\cdot 3^7$ whereas $166081$ is a prime number. Therefore, $\mathrm{gcd}(166081,279936)=1$. So we know the linear congruence has a unique solution. The solution to the Bézout Identity can be computed using the Mathematica function:

`{g, {s, t}} = ExtendedGCD[166081, 279936]`

.

This yields the result:

\[

(123073)(166081)+(-73017)(279936)=1

\]So the solution is $k\equiv 97590 \cdot 123073 \equiv 39990\pmod{279936}$. We can now compute $N$ as:

$\displaystyle

N=\frac{5764801\cdot 39990 +3261642}{279936} = 823537

$

If we want to find *all* solutions, we can add multiples of $279936$ to the base $k_0$ we found. This yields a solution set of the form:

\[

N = 823537 + 5764801m\qquad\text{for: }m=0,1,2,\dots

\]

Hi nice post as usual. In the general solution I think there is a problem in this step:

“Reducing and rearranging this is equivalent to:

160681 * k = 97590”

The eventual correct result will (I think) look like N^N * k – (N-1); k={1,..} or in this case:

823543 * k -6 ; k={1,…}

Oops. Sorry. This is wrong. It doesn’t leave an integral numnber of coconuts per pirate at end, just an integral total number.

Hi,

This can be solved without modular arithmetic; just high school algebra (geometric progression) is sufficient. All we have to do is go backwards from the last count.

Here is the solution:

https://imgur.com/a/HV0UTod

Vaidhy

Just going through my solution again, it seems that there is a closed form solution if you take it further along.

For n odd initial count = m(n^n – n + 1)

For n even initial count = n^(n+1) – m (n^n+n-1)

For m = 1, n = 7, count = 7^7 – 7 + 1 = 823,537

In the related problem where the monkey gets [takes] a coconut each time, including the morning, then the “smallest” solution is N = -6. Each time during the night: The monkey takes a coconut, the pile becomes -6 – 1 = -7; the pirate takes 1/7 of the remaining pile: -7 – (-7 /7) = -7 – (-1) = -6. Taking -1 coconut is the same as giving +1 coconut: the pirate’s -1 coconut corresponds to the monkey’s +1 coconut, so coconuts balance. Furthermore, each pirate encounters the pile the same as when the pirates went to sleep (namely, -6 coconuts), so no one suspects anything! The “extra” coconut comes from the monkey, who withheld it from the original pile. But being a monkey, the monkey loses it each time, and the pirate finds it just soon enough to give it back to the monkey. The monkey is a [lossy] banker who facilitates each pirate’s greed by re-circulating the coconut.

Exploration: Iterating f(M) = 6*(M -1)/7 must eventually produce a fixed point: f(M) = M. Solving 6*(M-1)/7 = M yields M = -6. That’s the same -6 as in Jim Crimmins’ comments above.

Alternate approach to the related problem: Write all numbers in base 7, and work backwards. Then at each stage the least-significant digit must be 1; giving a coconut to the monkey makes the lowest digit zero: the pile becomes divisible by 7. Dividing by 7 is equivalent to shifting off the lowest digit. Taking 1/7 of the pile must leave a lowest digit of 1 for the next stage , so the lowest digit subtracted must be 6; the two lowest-order digits must be 61 (base 7). Continuing the analysis at each backward step shows that N = …666661 base 7, which is -6 (modulo any power of 7). The particular power is the number of instances at which the remaining pile is required to be a multiple of 7.

My approach was to do the modular arithmetic at each stage, resulting in a calculation I could do by hand without resorting to Mathematica: See https://mathematrec.wordpress.com/2018/05/07/riddlers-for-4-may-2018/