How To Cross The Street

Riddler Express

Suppose you have $N$ circles, all of which are joined so that their centers lie on a larger circle (with the small circles tangent to their neighbours along that ring). What is the ratio of the diameter of the larger circle to the diameter of the smaller circles?

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

Solution

The picture. Place the $N$ small circles around the larger circle of radius $R$, so that each small circle has its centre on the big circle and the chain of small circles closes up with neighbours tangent to one another. By symmetry, the $N$ centres form a regular $N$-gon inscribed in the big circle. Let $r$ be the common radius of the small circles.

One angle does all the work. Pick two adjacent small circles and join their centres to the centre of the big circle. The two centres lie on the big circle at radius $R$, separated by the central angle $2\pi/N$. The chord between them is the segment connecting their centres, and because the two small circles are tangent that chord has length $2r$.

The chord of a circle of radius $R$ subtending a central angle $\theta$ has length $2R \sin(\theta/2)$. With $\theta = 2\pi/N$ that gives $$2r \;=\; 2 R \sin(\pi/N), \qquad\text{so}\qquad \frac{R}{r} \;=\; \frac{1}{\sin(\pi/N)}.$$ Diameters scale the same way, so the diameter ratio equals the radius ratio. The answer is $$\boxed{\,\dfrac{D_{\text{big}}}{D_{\text{small}}} \;=\; \dfrac{1}{\sin(\pi/N)}.\,}$$ At $N = 6$ this gives ratio $2$ (the classic six-around-one packing); at $N = 12$ it gives $1/\sin 15^{\circ} \approx 3.864$.

The computation

Place the centres explicitly on a unit-radius big circle and check that adjacent small circles are tangent.

1. Put centre $k$ at $(\cos(2\pi k/N), \sin(2\pi k/N))$ for $k = 0, 1, \ldots, N-1$.

2. Measure the Euclidean distance between centre $0$ and centre $1$; that distance equals $2 r$.

3. Compare $1 / r$ with $1/\sin(\pi/N)$ for a sweep of $N$.

import math

for N in [3, 4, 6, 8, 12, 20, 100]:
    cx0, cy0 = 1.0, 0.0
    cx1, cy1 = math.cos(2*math.pi/N), math.sin(2*math.pi/N)
    d_centres = math.hypot(cx1 - cx0, cy1 - cy0)
    r = d_centres / 2
    R_over_r = 1.0 / r
    formula = 1.0 / math.sin(math.pi/N)
    print(f"N={N:3d}: R/r measured = {R_over_r:.6f}, formula = {formula:.6f}")

The two columns match to machine precision for every $N$, confirming the boxed ratio.

Riddler Classic

You and a partner are meeting a friend at a restaurant in a city whose streets are laid out as a grid. Every intersection has pedestrian signals that let people walk in only one direction at a time, and the signals alternate. Each “walk” signal and each “don’t walk” signal lasts for the same fixed duration $T$. You are located at point $A$ and the restaurant is at point $B$, one block north and two blocks east of $A$. The intersection at $A$ shows a “walk” signal allowing you to go north and a “don’t walk” timer for east currently reading $1$ second. The other intersections’ signals are at unknown points in their cycles. You can cross only one street at each intersection, you cannot jaywalk, and you want to reach $B$ as fast as possible. Which direction should you go first?

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

Solution

The setup. Label the grid by (east blocks remaining, north blocks remaining). You start at $(2, 1)$ and want to reach $(0, 0)$. At a grid point with both coordinates positive you can choose either direction; at $(k, 0)$ with $k > 0$ you must go east; at $(0, k)$ with $k > 0$ you must go north. At the starting intersection you may go north right now (wait $\tau_N = 0$) or wait $\tau_E = 1$ second and go east.

The wait at an unknown intersection, going in a forced direction. At every other intersection the cycle phase is uniform on $[0, 2T)$. Each direction shows the walk signal for exactly half the cycle. If you arrive needing to go in a specific direction, the chance you can walk immediately is $1/2$. Conditional on a don’t-walk signal, the time until your direction switches to walk is uniform on $(0, T]$, with mean $T/2$. So your expected wait at a forced-direction intersection is $$\mathbb{E}[\text{wait}] \;=\; \tfrac{1}{2} \cdot 0 + \tfrac{1}{2} \cdot \tfrac{T}{2} \;=\; \tfrac{T}{4}.$$ This uses no information about other intersections beyond the cycle length.

The wait at an intersection with a choice. If both directions are still open ($(e, n)$ with $e \ge 1, n \ge 1$), one of the two signals is showing walk right now. Cross in whichever direction the signal allows. The wait is $0$.

Compare the two opening moves. Going north from $(2, 1)$ costs $0$ seconds and lands at $(2, 0)$, which is forced east twice. The expected total wait from $A$ to $B$ along this route is $$\mathbb{E}[\text{time} \mid \text{north first}] \;=\; 0 + \tfrac{T}{4} + \tfrac{T}{4} \;=\; \tfrac{T}{2}.$$ Going east from $(2, 1)$ costs $1$ second and lands at $(1, 1)$, which has a choice (so the next wait is $0$). After that move you reach either $(0, 1)$ or $(1, 0)$, in both cases a forced single move with expected wait $T/4$. Total: $$\mathbb{E}[\text{time} \mid \text{east first}] \;=\; 1 + 0 + \tfrac{T}{4} \;=\; 1 + \tfrac{T}{4}.$$

Which is smaller? East beats north exactly when $$1 + \tfrac{T}{4} \;<\; \tfrac{T}{2} \qquad \Longleftrightarrow \qquad T \;>\; 4 \text{ seconds}.$$ Walk-and-don’t-walk durations of $4$ seconds or less are very short for an actual urban grid. In the regime of any real city,

Why the choice is worth a second. The general principle is that crossings with multiple legal directions cost nothing in expected wait, while forced crossings cost $T/4$. Going east immediately spends $1$ second to convert a forced east leg into a choice intersection: a saving of $T/4 - 1$ in expected wait downstream. Whenever the cycle is long enough that $T/4 > 1$, options are worth more than the second they cost. The rule extends: at any intersection, prefer the move that buys a choice over a move that leaves you forced.

The computation

Simulate the journey. Use the cycle convention in which one full cycle has length $2T$, with phase $\phi$ uniform on $[0, 2T)$ at each non-starting intersection; the north walk shows for $\phi \in [0, T)$ and the east walk for $\phi \in [T, 2T)$.

1. At $A$, apply the deterministic move: north costs $0$, east costs $1$.

2. At each subsequent intersection, draw a fresh phase. If forced, compute the wait until the right walk starts; if free, take whichever direction is walking.

3. Average over many trials for both opening strategies and a sweep of cycle lengths.

import random

def trip(T, start, trials=200000):
    total = 0.0
    for _ in range(trials):
        e, n = 2, 1
        t = 0.0
        if start == 'N':
            n -= 1
        else:
            t += 1.0; e -= 1
        while e > 0 or n > 0:
            phi = random.uniform(0, 2 * T)
            n_walks = phi < T
            if e == 0:
                t += 0.0 if n_walks else (2 * T - phi); n -= 1
            elif n == 0:
                t += (T - phi) if n_walks else 0.0; e -= 1
            else:
                if n_walks: n -= 1
                else: e -= 1
        total += t
    return total / trials

for T in [3, 4, 5, 6, 8, 12]:
    n_avg = trip(T, 'N')
    e_avg = trip(T, 'E')
    print(f"T={T:2d}: north first -> {n_avg:.3f}s, "
          f"east first -> {e_avg:.3f}s")

At $T = 3$ north first wins ($1.50$s vs $1.75$s); at $T = 4$ the two tie at $2.00$s; for $T \ge 5$ east first wins by an amount that grows with $T$. The crossover is exactly at $T = 4$, matching the boxed inequality.