Pirates, Monkeys, and Coconuts

Riddler Express

If $A, B, C, D, E$ are all unique digits, what values would work with the following equation? $$\overline{A B C, C D E} \times 4 \;=\; \overline{E D C, C B A}.$$

The Riddler, FiveThirtyEight, May 4, 2018(original post)

Solution

Pin $A$. Both sides are six-digit numbers, so $A \ge 1$ (no leading zero) and the product is at most $999{,}999$, forcing $\overline{ABCCDE} \le 249{,}999$, hence $A \le 2$. The rightmost digit of $4 \cdot \overline{ABCCDE}$ equals the rightmost digit of $4 E$, which is $A$. Since $4 E$ is even and $A \ne 0$, $A$ is an even positive digit at most $2$. Therefore $A = 2$.

Pin $E$. The right-hand side starts with $E$ and equals $4 \cdot \overline{2BCCDE}$. The first digit of $4 \cdot \overline{2BCCDE}$ is either $8$ or $9$, so $E \in \{8, 9\}$. The ones-digit constraint is $4 E \equiv 2 \pmod{10}$, which forces $E \in \{3, 8\}$. The intersection is $E = 8$.

Pin $B$. With $A = 2$ and $E = 8$, the ones place of the left-hand side gives $4 \cdot 8 = 32$: $2$ is the ones of the right, and $3$ carries into the tens place. The leftmost two digits of the right-hand side are $8 D$ and the leftmost of the left-hand side multiplied by $4$ must produce them. In particular $4 B + \text{(carry)} = D$ in the ten-thousands place; the carry in is at most $3$ and $D$ is a single digit, so $4 B \le 9$, giving $B \in \{0, 1, 2\}$. Since $A = 2$, $B \in \{0, 1\}$. Looking at the ten-thousands place: $4 B + (\text{carry from } C \cdot 4) \equiv 1 \pmod{10}$ (because the right-hand side’s ten-thousands digit is $B = ?$; actually it is $B$, so $\overline{ED C, C B A}$ has $B$ in the tens place). Walking the multiplication right to left, the second digit from the right of the product is determined by $4 D + 3$ (carry from $4 E = 32$). This must equal $B$ modulo $10$. If $B = 1$, then $4 D + 3 \equiv 1 \pmod{10}$, so $4 D \equiv 8$, so $D \in \{2, 7\}$; $D = 2$ is taken by $A$, so $D = 7$. If $B = 0$, then $4 D + 3 \equiv 0 \pmod{10}$, so $4 D \equiv 7 \pmod{10}$, impossible since $4 D$ is even. Hence $B = 1$ and $D = 7$.

Pin $C$. With $(A, B, D, E) = (2, 1, 7, 8)$ the remaining unknown is $C$. The number $\overline{2 1 C, C 7 8}$ multiplied by $4$ must equal $\overline{8 7 C, C 1 2}$. The hundreds digit on the right is $C$, generated from $4 C + (\text{carry from } 4 \cdot 7 + 3) = 4 C + 31 / 10$, i.e. carry $3$. So $4 C + 3 \equiv C \pmod{10}$, i.e. $3 C \equiv -3 \pmod{10}$, i.e. $C \equiv 9 \pmod{10}$. Hence $C = 9$.

Check. The candidate is $(A, B, C, D, E) = (2, 1, 9, 7, 8)$: $$219{,}978 \times 4 \;=\; 879{,}912. \quad\checkmark$$ All five digits are distinct, and the equation holds. So $$\boxed{\,\begin{aligned} & A = 2,\ B = 1,\ C = 9,\ D = 7,\ E = 8, \\ & \text{and}\ 219{,}978 \times 4 = 879{,}912. \end{aligned}\,}$$

The computation

Sweep every assignment of five distinct digits to $(A, B, C, D, E)$, evaluate both sides of the equation, and report those that satisfy it.

1. Loop over $A \in \{1, \ldots, 9\}$ and $B, C, D \in \{0, \ldots, 9\}$ and $E \in \{1, \ldots, 9\}$ (both leading digits non-zero).

2. Skip assignments where any two letters coincide.

3. Test $4 \cdot \overline{A B C C D E} = \overline{E D C C B A}$ and print every solution.

solutions = []
for a in range(1, 10):
    for b in range(10):
        if b == a: continue
        for c in range(10):
            if c in (a, b): continue
            for d in range(10):
                if d in (a, b, c): continue
                for e in range(1, 10):
                    if e in (a, b, c, d): continue
                    L = a*100000 + b*10000 + c*1100 + d*10 + e
                    R = e*100000 + d*10000 + c*1100 + b*10 + a
                    if 4 * L == R:
                        solutions.append((a, b, c, d, e, L, R))

for s in solutions:
    print(s)

The sweep prints exactly one tuple, $(2, 1, 9, 7, 8, 219978, 879912)$, matching the boxed assignment.

Riddler Classic

Seven pirates wash ashore on a deserted island and gather $N$ coconuts into a single pile. During the night each pirate, one after another, wakes up, tosses one coconut to a watching monkey, divides the remaining pile into seven equal heaps, hides one heap for themselves, and pushes the other six heaps back into a single pile before going back to sleep. In the morning the seven pirates divide the remaining pile into seven equal heaps (the monkey gets nothing this time). Coconuts are indivisible. What is the smallest $N$ for which this is possible?

The Riddler, FiveThirtyEight, May 4, 2018(original post)

Solution

One pirate’s effect on the pile. If a pirate finds $M$ coconuts in the pile, tosses one to the monkey, and hides one-seventh of the remainder, the pile shrinks to $$f(M) \;=\; \tfrac{6}{7}(M - 1).$$ For this to be a whole number, $M - 1$ must be divisible by $7$, i.e. $M \equiv 1 \pmod{7}$.

Seven pirates and a morning split. Starting with $N$, after the seven night visits the pile has size $f^{7}(N)$. The morning split into seven equal heaps requires $$f^{7}(N) \;=\; 7 k \qquad\text{for some non-negative integer } k.$$

Unwind the recurrence. Write $u_{i} = f^{i}(N)$ with $u_{0} = N$. The recurrence is $u_{i+1} = \tfrac{6}{7}(u_{i} - 1)$, i.e. $7 u_{i+1} = 6 u_{i} - 6$, i.e. $u_{i+1} + 6 = \tfrac{6}{7}(u_{i} + 6)$. So the sequence $u_{i} + 6$ is geometric with ratio $6/7$, giving $$u_{7} + 6 \;=\; \left(\tfrac{6}{7}\right)^{7} (N + 6) \;=\; \frac{6^{7}}{7^{7}}(N + 6) \;=\; \frac{279{,}936}{823{,}543}(N + 6).$$ Setting $u_{7} = 7 k$ and solving for $N$, $$N \;=\; \frac{7^{7}(7 k + 6) - 6 \cdot 6^{7}}{6^{7}} \;=\; \frac{5{,}764{,}801 \, k + 3{,}261{,}642}{279{,}936}.$$ The denominator factors as $279{,}936 = 6^{7} = 2^{7} \cdot 3^{7}$, and the numerator’s leading term has $7^{7}$ coprime to $6$, so $N$ is an integer iff $279{,}936 \mid 5{,}764{,}801 \, k + 3{,}261{,}642$.

Solve the congruence. Reduce: $5{,}764{,}801 \equiv 7^{7} \pmod{6^{7}}$. The inverse of $7$ modulo $6$ is $1$ (since $7 \equiv 1$), and by lifting modulo $2^{7}$ and $3^{7}$ separately the inverse of $7$ modulo $6^{7}$ is some specific residue $\alpha$, giving $k \equiv -3{,}261{,}642 \cdot \alpha^{7} \pmod{6^{7}}$. The smallest non-negative solution is $k = 39{,}990$. Plugging back, $$\begin{aligned} N &\;=\; \frac{5{,}764{,}801 \times 39{,}990 + 3{,}261{,}642}{279{,}936} \\ &\;=\; \frac{230{,}549{,}293{,}632}{279{,}936} \;=\; 823{,}537. \end{aligned}$$ So $$\boxed{\,N_{\min} \;=\; 823{,}537.\,}$$

Sanity check on the sequence. Apply $f$ seven times to $823{,}537$: $$\begin{align*} 823{,}537 \to 705{,}888 \to 605{,}046 \to 518{,}610 \to 444{,}522 \\ \to 381{,}018 \to 326{,}586 \to 279{,}930. \end{align*}$$ Each step subtracts one for the monkey, divides by seven exactly, and keeps six sevenths, and the final pile $279{,}930 = 7 \cdot 39{,}990$ splits cleanly into seven morning shares of $39{,}990$ coconuts each.

The computation

Search the smallest $N$ that supports seven successive integer-divisible night visits and a morning seven-way split.

1. For $N$ from small upward, simulate $f$ seven times, abandoning early if any intermediate $M - 1$ fails to be divisible by $7$ or any intermediate $M$ goes non-positive.

2. Accept the first $N$ whose final pile is positive and divisible by $7$.

def smallest_N():
    for N in range(7, 5_000_000):
        M = N; ok = True
        for _ in range(7):
            if (M - 1) % 7 != 0:
                ok = False; break
            M = 6 * (M - 1) // 7
            if M <= 0:
                ok = False; break
        if ok and M > 0 and M % 7 == 0:
            return N, M, M // 7
    return None

N, final, share = smallest_N()
print(f"smallest N = {N}, final pile = {final}, morning share each = {share}")

The search prints $N = 823{,}537$, final pile $279{,}930$, morning share $39{,}990$ per pirate, matching the boxed answer.