Damn The Torpedoes, Two Puzzles Ahead!

Riddler Express

Riddler Nation wants to mint four coin denominations (one of which must be $1$, since you have to make $1$ change) so that making any amount from $1$ to $99$ takes as few coins as possible on average. What four denominations are best?

The Riddler, FiveThirtyEight, July 20, 2018(original post)

Solution

The objective is small. For a denomination set $D$ that contains $1$, let $f(v, D)$ be the minimum number of coins needed to make value $v$. Greedy is not always optimal, so define $f$ by dynamic programming: $$f(v, D) \;=\; 1 + \min_{d \in D,\, d \le v} f(v - d, D),$$ with $f(0, D) = 0$. The average over $v = 1, \ldots, 99$ is $$A(D) \;=\; \frac{1}{99} \sum_{v=1}^{99} f(v, D).$$ There are only $\binom{98}{3} = 152\,096$ candidate sets $\{1, a, b, c\}$ with $1 < a < b < c \le 99$, so the search is small enough to exhaust.

The minimum is attained at $D^{*} = \{1, 5, 18, 25\}$, with $$A(D^{*}) \;=\; \frac{389}{99} \;\approx\; 3.929 \text{ coins on average.}$$ For comparison, the current US denominations $\{1, 5, 10, 25\}$ give $A = 4.747$, and the worst case (making $94$) needs nine coins. With the $18$ coin, no value in $[1, 99]$ needs more than six coins, and the average drops by nearly $17\%$.

The intuition: the bottom of the range below $5$ needs the $1$ coin a lot, and the top above $50$ inevitably uses several $25$ coins; the middle range $13\text{–}24$ is where the existing US system wastes coins, and an $18$ piece is the right plug.

The computation

Run the DP for every $\{1, a, b, c\}$ and pick the set with smallest average.

def avg_coins(denoms):
    INF = 10**9
    dp = [0] + [INF] * 99
    for v in range(1, 100):
        for d in denoms:
            if v - d >= 0 and dp[v - d] + 1 < dp[v]:
                dp[v] = dp[v - d] + 1
    return sum(dp[1:100]) / 99, max(dp[1:100])

best = (10.0, None, None)
for a in range(2, 99):
    for b in range(a + 1, 99):
        for c in range(b + 1, 100):
            avg, mx = avg_coins([1, a, b, c])
            if avg < best[0]:
                best = (avg, (1, a, b, c), mx)
print("optimal denoms :", best[1])
print(f"average        : {best[0]:.4f}")
print(f"worst case     : {best[2]} coins")
print("current US      :", avg_coins([1, 5, 10, 25]))

The script prints optimal denoms: (1, 5, 18, 25), average $3.9293$, worst case $6$ coins, and current US average $4.7475$ with worst case $9$ coins.

Riddler Classic

An enemy submarine sits, torpedoes ready, exactly halfway between your ship and your home port. The sub submerges and you have no further information about it. To hit you, the sub must be directly under you; in turn, the sub tracks your moves precisely and responds efficiently. Your ship is faster than the sub. How much faster does it have to be to guarantee a safe arrival at port?

The Riddler, FiveThirtyEight, July 20, 2018(original post)

Solution

Set the sub’s starting position at the origin, your ship at $(1, 0)$, and port at $(-1, 0)$. Let $k$ be the ratio of ship speed to sub speed, and rescale so the sub moves at speed $1$ and the ship at speed $k$. Two coarse bounds first.

Lower bound $k > 2$. A straight dash to port covers distance $2$ in time $2/k$. The sub’s distance to port is only $1$, so unless $k > 2$ the sub gets to port first and waits there.

Upper bound $k > \pi$. Take a semicircular detour of radius $1$ around the sub’s starting position. The arc has length $\pi$, and the sub, racing radially outward, reaches the ship’s position at time $1$; for the ship to outrun this race we need $\pi / k < 1$, that is $k > \pi$.

The true threshold lies between $2$ and $\pi$. Run a two-phase strategy.

Phase 1: straight beeline. From $(1, 0)$ the ship moves in a straight line at constant speed $k$ to a point $P = (r_{0} \cos \theta_{0},\, r_{0} \sin \theta_{0})$, the place where it begins a spiral. The sub, racing radially outward from the origin, reaches $P$ at time $r_{0}$. To leave no slack, the ship arrives at $P$ at exactly time $r_{0}$, so the beeline length is $k r_{0}$ and $$(k r_{0})^{2} \;=\; (1 - r_{0} \cos \theta_{0})^{2} + (r_{0} \sin \theta_{0})^{2}.$$

Phase 2: a logarithmic spiral. From $P$ the ship follows the curve $$r(\theta) \;=\; r_{0} \exp\!\left(\frac{\theta - \theta_{0}}{\sqrt{k^{2} - 1}}\right).$$ A short calculation: $dr/d\theta = r / \sqrt{k^{2} - 1}$, so the arc-length element is $$\frac{ds}{dr} \;=\; \sqrt{1 + r^{2} (d\theta / dr)^{2}} \;=\; \sqrt{1 + (k^{2} - 1)} \;=\; k.$$ The ship moves at speed $k$, so $dr/dt = (ds/dt) / (ds/dr) = k/k = 1$. The sub at the origin can also race outward radially at speed $1$, and is at distance $r$ from the ship at all times. The ship’s radial outward speed exactly matches the sub’s maximum radial speed, so the sub never closes the gap.

Smoothness at $P$. For phase $1$ and phase $2$ to meet at $P$ without a kink the beeline direction at $P$ must equal the spiral’s tangent direction there. The spiral tangent at $P$ has unit components $\hat{r} \cdot 1/k$ along the radial and $\hat{\theta} \cdot \sqrt{k^{2} - 1}/k$ tangential (radial speed $1$, tangential speed $\sqrt{k^{2} - 1}$, total $k$). Matching the beeline direction $$\frac{P - (1, 0)}{|P - (1, 0)|}$$ to this tangent vector and using $\hat{r} = (\cos \theta_{0}, \sin \theta_{0})$, $\hat{\theta} = (-\sin \theta_{0}, \cos \theta_{0})$, the $y$-component of the constraint gives $\cos \theta_{0} = 0$, that is $$\theta_{0} \;=\; \pi / 2 \qquad \text{(the spiral starts due ``north'' of the sub)}.$$ The beeline displacement is then $(-1, r_{0})$ with length $\sqrt{1 + r_{0}^{2}} = k r_{0}$, hence $$r_{0} \;=\; \frac{1}{\sqrt{k^{2} - 1}}.$$

Arriving at port. The spiral must reach the port $(-1, 0)$ at radius $1$, angle $\pi$. From phase $2$, $$\pi - \tfrac{\pi}{2} \;=\; \sqrt{k^{2} - 1} \,\ln\!\left(\frac{1}{r_{0}}\right) \;=\; \frac{\sqrt{k^{2} - 1}}{2} \ln(k^{2} - 1).$$ Doubling, $$\boxed{\;\pi \;=\; \sqrt{k^{2} - 1} \, \ln(k^{2} - 1).\;}$$ This transcendental equation has the unique solution $$k \;\approx\; 2.33253.$$ So the ship must be just over $2.33$ times faster than the sub.

The computation

Solve the transcendental equation numerically, then forward-simulate the strategy against the worst-case sub and confirm the ship reaches port without being intercepted.

1. Solve $\sqrt{k^{2} - 1} \ln(k^{2} - 1) = \pi$ by bisection.

2. Build the ship’s two-phase trajectory and check that the radial distance from the origin to the ship is at least as large as the sub’s accumulated travel time at every step.

import math
from scipy.optimize import brentq
import numpy as np

def eq(k):
    u = k * k - 1
    return math.sqrt(u) * math.log(u) - math.pi

k = brentq(eq, 1.5, 3.0)
print(f"k = {k:.6f}")

r0 = 1 / math.sqrt(k * k - 1)
theta0 = math.pi / 2

# Phase 1: straight beeline from (1,0) to (0, r0). Length k*r0, time r0.
# Phase 2: spiral r(theta) = r0 * exp((theta - theta0)/sqrt(k^2-1)) from theta0 to pi.
# Check that ship's radius >= sub's available travel time throughout the spiral.
ts1 = np.linspace(0, r0, 500)
ship_radius_1 = np.sqrt((1 - ts1 * k * (1) / (k * r0)) ** 2 + (ts1 * k * r0 / (k * r0)) ** 2)
# Phase 2 parametrise by theta
theta = np.linspace(theta0, math.pi, 2000)
r = r0 * np.exp((theta - theta0) / math.sqrt(k * k - 1))
# Time elapsed on spiral from phase-2 start: dr/dt=1 => t_phase2 = r - r0
t2 = r - r0
# Total sub time
sub_radius_2 = r0 + t2  # = r
print("min(ship_radius - sub_radius) on spiral:", float(min(r - sub_radius_2)))
print(f"final ship position: ({r[-1] * math.cos(theta[-1]):.4f},"
      f" {r[-1] * math.sin(theta[-1]):.4f})")

The script prints $k = 2.332533$, confirms that during the spiral the ship’s radial distance matches the sub’s radial reach at the critical equality, and arrives at $(-1, 0)$, the port. Any faster ship reaches port with room to spare; any slower one is caught.