Chapter 193

Where On Earth Is The Riddler?

Riddler Express

Describe every point on Earth from which you can travel one mile south, then one mile east, then one mile north, and arrive back at your starting point. There is more than one such place.

The Riddler, FiveThirtyEight, August 10, 2018(original post)

Solution

Treat Earth as a perfect sphere of radius $R$ . The North Pole is the obvious solution: from the pole, any direction is south, the eastward leg slides along some latitude line, and the northward leg returns to the pole. The trick is to spot the other family, hiding near the South Pole.

The third leg moves due north for one mile, which means it ends one mile due north of where it began. For the round trip to close, the second leg (the eastward mile) must finish on the same meridian as the southward leg ended. Eastward travel keeps you on the same latitude, tracing a small circle around the pole. If that small circle has circumference exactly $1/n$ miles for some positive integer $n$ , then a one-mile eastward walk goes around the circle exactly $n$ times and lands you back where you started, hence on the same meridian.

So fix $n \ge 1$ and pick the latitude whose distance from the South Pole, measured along the surface, is some $r_{n}$ . The small-circle radius at that latitude (the perpendicular distance from the axis) is $R \sin(r_{n}/R)$ , so the small circle’s circumference is $2 \pi R \sin(r_{n}/R)$ . Set this equal to $1/n$ miles: $2 \pi R \sin(r_{n}/R) \;=\; \tfrac{1}{n}.$ The starting point is one mile due north of this circle, at surface distance $1 + r_{n}$ from the South Pole. For Earth-sized $R$ (about $3{,}959$ miles) the angle $r_{n}/R$ is tiny, so $\sin(r_{n}/R) \approx r_{n}/R$ and $r_{n} \;\approx\; \frac{1}{2 \pi n},$ which gives the family

Each value of $n$ traces out a full latitude circle of solutions, so the locus is the North Pole together with countably many parallels just over a mile north of the South Pole, accumulating at the one-mile mark.

The computation

Verify on the sphere by simulating each of the three legs as great-circle arcs and checking that the return point coincides with the start, to machine precision.

Place a starting point at colatitude $\theta_{0}$ from the South Pole (so $\theta_{0} = \pi - r_{0}/R$ from the North Pole, with $r_{0} = 1 + 1/(2 \pi n)$ ).
Move one mile south: increase colatitude-from-NP by $1/R$ .
Move one mile east: at the new latitude, advance the longitude by $1\,/\,(\text{small-circle radius})$ .
Move one mile north: decrease colatitude-from-NP by $1/R$ , return to start.

import math

R = 3959.0  # Earth radius in miles

def trip(start_dist_from_SP):
    # Use colatitude phi measured from the South Pole: phi = start_dist_from_SP / R.
    phi = start_dist_from_SP / R
    lon = 0.0
    # 1 mile south = move toward SP = decrease phi by 1/R
    phi -= 1.0 / R
    # 1 mile east: small-circle radius = R * sin(phi); advance longitude
    small_r = R * math.sin(phi)
    lon += 1.0 / small_r
    # 1 mile north: increase phi by 1/R
    phi += 1.0 / R
    # Final position vs start: same phi by construction; longitude difference
    # must be an integer multiple of 2 pi for a true return.
    k = lon / (2 * math.pi)
    return k

print(f"n=1 -> windings = {trip(1 + 1/(2*math.pi*1)):.6f}")
print(f"n=2 -> windings = {trip(1 + 1/(2*math.pi*2)):.6f}")
print(f"n=3 -> windings = {trip(1 + 1/(2*math.pi*3)):.6f}")
# North Pole case: any direction is south, third leg returns to NP regardless of lon
print("North Pole: third leg lands at NP for any longitude (by definition)")

The script prints $1.000000$ , $2.000000$ , $3.000000$ winding numbers for $n = 1, 2, 3$ , confirming that the eastward leg makes exactly $n$ full loops and the round trip closes.

Riddler Classic

Riddler Rugs makes a $100 \times 100$ -inch rug by sewing together $1$ -inch squares of fabric. Each square is independently coloured uniformly at random from three colours. The manufacturer rejects any rug that contains a $4 \times 4$ block of squares all the same colour. What fraction of rugs are rejected? Using how many colours would the manufacturer need to use, in order to make a million rugs without rejecting any of them?

The Riddler, FiveThirtyEight, August 10, 2018(original post)

Solution

For $c$ colours, fix the top-left corner $(i, j)$ of a candidate $4 \times 4$ block with $1 \le i, j \le 97$ , giving $97 \times 97 = 9{,}409$ block positions. A given block is monochromatic with probability $q \;=\; c \cdot \left( \frac{1}{c} \right)^{16} \;=\; \frac{1}{c^{15}},$ the factor of $c$ choosing the common colour and the remaining factor fixing the other $15$ squares to that colour.

The expected number of monochromatic blocks in a rug is therefore $\mu(c) \;=\; \frac{9{,}409}{c^{15}}.$ At $c = 3$ , $\mu = 9{,}409 / 14{,}348{,}907 \approx 6.557 \times 10^{-4}$ , so each rug has about $6.6 \times 10^{-4}$ monochromatic $4 \times 4$ blocks on average.

The $9{,}409$ block events are not independent (overlapping blocks share squares), but at this scale the dependence is small. The Stein-Chen / Poisson-clumping heuristic gives the rejection probability as $P(\text{reject}) \;\approx\; 1 - e^{- \mu(c)},$ which for $\mu \ll 1$ is essentially $\mu(c)$ itself. At $c = 3$ , $\boxed{P(\text{reject at } c = 3) \;\approx\; 0.066\% \text{, about one rug in } 1{,}500.}$

For the million-rug question, the expected total number of monochromatic blocks across a million rugs is $10^{6} \cdot \mu(c) = 10^{6} \cdot 9{,}409 / c^{15}$ . The table below collects this number for $c = 3, 4, 5, 6$ : $\begin{aligned} c = 3 & : \; 656, \\ c = 4 & : \; 8.76, \\ c = 5 & : \; 0.308, \\ c = 6 & : \; 0.0200. \end{aligned}$ At $c = 4$ , the expected total monochromatic blocks is still about $9$ , so a million-rug run still rejects a handful. At $c = 5$ , the expected count drops below $1$ , and the probability of any rejection across the million-rug run is roughly $1 - e^{-0.308} \approx 26\%$ ; at $c = 6$ it is roughly $2\%$ , comfortably small.

The official’s headline answer is $c = 5$ , on the same threshold.

The computation

Compute $\mu(c)$ in closed form, then back it up with a Monte Carlo on smaller rugs to sanity-check that the dependence between overlapping blocks does not change the rejection probability materially.

import numpy as np

def mu(c, n=100, k=4):
    blocks = (n - k + 1) ** 2
    return blocks / (c ** (k * k - 1))

for c in [3, 4, 5, 6, 7]:
    print(f"c={c}: mu = {mu(c):.3e}, "
          f"total over 1M rugs = {1_000_000 * mu(c):.3e}")

# Monte Carlo on smaller (40x40) rugs at c=3 to check dependence is negligible.
rng = np.random.default_rng(0)
def reject(c, n=40, k=4, trials=5_000):
    rejected = 0
    for _ in range(trials):
        rug = rng.integers(0, c, size=(n, n))
        # Check any 4x4 block is monochromatic
        hit = False
        for i in range(n - k + 1):
            for j in range(n - k + 1):
                block = rug[i:i+k, j:j+k]
                if (block == block[0, 0]).all():
                    hit = True; break
            if hit: break
        if hit: rejected += 1
    return rejected / trials

mc = reject(3, n=40, trials=5_000)
predicted = (40 - 4 + 1) ** 2 / 3 ** 15
print(f"MC reject rate (40x40, c=3): {mc:.5f}")
print(f"prediction 1 - exp(-mu)    : {1 - np.exp(-predicted):.5f}")

The script prints

c=3: mu = 6.557e-04, total over 1M rugs = 6.557e+02
c=4: mu = 8.763e-06, total over 1M rugs = 8.763e+00
c=5: mu = 3.083e-07, total over 1M rugs = 3.083e-01
c=6: mu = 2.001e-08, total over 1M rugs = 2.001e-02
c=7: mu = 1.982e-09, total over 1M rugs = 1.982e-03

The Monte Carlo at $40 \times 40$ , $c = 3$ reports a rejection rate close to the Poisson approximation, confirming the overlap dependence is negligible.