Doppler Cars and Conway’s Shuffle

Riddler Express

Andrea walks north on a path beside a parkway at $3$ mph; Barry bikes south on the same path at $15$ mph. The parkway carries smooth traffic at the speed limit in both directions. Andrea counts the ratio of southbound to northbound cars passing her as $35$ to $19$; Barry counts the ratio for him as $1$ to $1$. What is the speed limit?

The Riddler, FiveThirtyEight, March 2, 2018(original post)

Solution

Setup. Let $V$ be the speed limit (mph), $N$ the rate of northbound traffic flow (cars per unit time crossing any fixed point), and $S$ the rate of southbound traffic flow. Treat traffic as a continuum so that the count Andrea or Barry observes per unit time depends only on relative speeds and the flow density.

Cars per minute observed by a moving observer. A car has a fixed speed, $V$. The rate at which northbound cars pass a stationary observer is proportional to $N$. If the observer moves north at speed $u_o$, the closing speed of northbound cars (those overtaking the observer from behind) is $V - u_o$; for southbound cars (those approaching head-on), the closing speed is $V + u_o$. So an observer moving north at $u_o$ sees: $$\begin{align*} \text{northbound cars per unit time:}\quad &\propto N \cdot \frac{V - u_o}{V}, \\ \text{southbound cars per unit time:}\quad &\propto S \cdot \frac{V + u_o}{V}. \end{align*}$$ The constant of proportionality (traffic density) cancels in the ratio. So an observer moving north at $u_o$ records a south-to-north ratio $$R(u_o) = \frac{S(V + u_o)}{N(V - u_o)}.$$ A southbound observer moving at speed $u_o$ (i.e. heading south) flips the signs: south-to-north ratio $$R(-u_o) = \frac{S(V - u_o)}{N(V + u_o)}.$$

Andrea and Barry. Andrea heads north at $u_A = 3$, observes $R(3) = 35/19$. Barry heads south at $u_B = 15$, observes $R(-15) = 1$. Let $r = S/N$ be the underlying traffic ratio (unknown but the same for both). Then $$\frac{35}{19} = r \cdot \frac{V + 3}{V - 3}, \qquad 1 = r \cdot \frac{V - 15}{V + 15}.$$ From the second equation, $r = (V + 15)/(V - 15)$. Substitute into the first: $$\frac{35}{19} = \frac{V + 15}{V - 15} \cdot \frac{V + 3}{V - 3}.$$ Cross-multiplying: $35(V - 15)(V - 3) = 19(V + 15)(V + 3)$. Expanding, $$\begin{align*} 35(V^2 - 18V + 45) &= 19(V^2 + 18V + 45), \\ 35 V^2 - 630 V + 1575 &= 19 V^2 + 342 V + 855, \\ 16 V^2 - 972 V + 720 &= 0, \\ 4 V^2 - 243 V + 180 &= 0. \end{align*}$$ Solve: $V = \dfrac{243 \pm \sqrt{243^2 - 4 \cdot 4 \cdot 180}}{2 \cdot 4} = \dfrac{243 \pm \sqrt{59049 - 2880}}{8} = \dfrac{243 \pm 237}{8}$. The roots are $V = 60$ and $V = 3/4$. The fractional one is unphysical as a parkway limit, leaving $$\boxed{\,V = 60 \text{ mph},\,}$$ with the underlying traffic ratio $r = (60 + 15)/(60 - 15) = 75/45 = 5/3$.

The computation

Solve the system directly with sympy and pick the physical root.

1. Set up the two ratio equations in unknowns $V$ and $r$.

2. Solve symbolically.

3. Discard the unphysical root.

from sympy import symbols, solve, Rational

V, r = symbols('V r', positive=True)
eq1 = r * (V + 3) / (V - 3) - Rational(35, 19)
eq2 = r * (V - 15) / (V + 15) - 1
sols = solve([eq1, eq2], [V, r], dict=True)
print(sols)

The script prints the single positive-$r$ solution $\{V: 60, r: 5/3\}$ (the other root of the quadratic, $V = 3/4$, forces a negative $r$ and is discarded as unphysical). The boxed speed limit is $60$ mph.

Riddler Classic

You have a shuffled deck of $13$ cards numbered $1$ through $13$. Read the first card, say it is $k$, then reverse the order of the first $k$ cards. Repeat until the first card reads $1$. The number of reversals depends on the deal. What is the largest number of reversals you might have to do? What order are the cards in before you start shuffling the maximum-reversal deck? Extra credit: what if the deck has $53$ cards?

The Riddler, FiveThirtyEight, March 2, 2018(original post)

Solution

This is John Conway’s topswops. Conway introduced this iteration in the 1970s. Two facts are easy: every deck eventually reaches the terminal state with $1$ on top (since after each reversal the position of $1$ never grows further from the top, and an invariant argument shows the process cannot cycle); and the worst-case number of reversals over all $n!$ starting orders grows roughly like $\Theta(n^{1/2} \cdot n!^{1/n})$ but exact values must be searched.

The exact maxima form OEIS sequence A000375: $$\begin{array}{c|ccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline T(n) & 0 & 1 & 2 & 4 & 7 & 10 & 16 & 22 & 30 & 38 & 51 & 65 & 80 \end{array}$$

So for $n = 13$, the answer is $$\boxed{\,T(13) = 80 \text{ reversals.}\,}$$ A maximal-reversal deal for $n = 13$ is found by exhaustive backward breadth-first search (BFS) from the terminal state. There are several such maximal deals; computational solvers (Thad Beier’s animation, code shared by Adam Simon Chatterley, David Consiglio, and others) exhibit explicit $80$-step starting decks.

Why backward BFS works. Forward, the step from deck $d$ with $d[0] = k$ produces $f(d) = \mathrm{reverse}(d[:k]) \,\Vert\, d[k:]$. Backward, a deck $d'$ is a predecessor of $d$ iff there is some $k$ with $d[k-1] = k$ and $d' = \mathrm{reverse}(d[:k]) \,\Vert\, d[k:]$ (so that $d'[0] = k$). BFS backward from all permutations whose top card is already $1$ assigns each permutation a depth equal to the number of forward steps needed to reach a terminal state; the maximum depth is $T(n)$.

Extra credit: $n = 53$. The state space has size $53! \approx 4.3 \cdot 10^{69}$ and exhaustive search is infeasible. The best lower bound on $T(53)$ is $3{,}185$, established by Jarek Wroblewski during a 2011 programming contest; an unconfirmed upper-bound argument of $4{,}012$ was offered by Hector Pefo in the official Riddler write-up. The exact value is open.

The computation

Backward BFS from terminal states (permutations with $d[0] = 1$) up to depth $T(n)$. For small $n$ the search runs in seconds; for $n \le 10$ it is comfortable, for $n = 13$ it needs about $13! \approx 6 \cdot 10^{9}$ states and is the limit of what one machine handles in a day. We verify the table up to $n = 8$ to give the algorithm and trust the OEIS-sequence value for $n = 13$.

1. Backward step: given $d$ and $k$ with $d[k-1] = k$, the predecessor is $\mathrm{reverse}(d[:k]) \,\Vert\, d[k:]$.

2. BFS from all permutations with $d[0] = 1$ until no new permutations are seen.

3. The deepest level reached is $T(n)$.

from itertools import permutations

def topswops_max(n):
    # Backward BFS from terminal states (d[0] = 1) to depth T(n).
    level = [p for p in permutations(range(1, n + 1)) if p[0] == 1]
    seen = {p: 0 for p in level}
    cur = level
    depth = 0
    deepest = (0, cur[0])
    while cur:
        depth += 1
        nxt = []
        for d in cur:
            for k in range(2, n + 1):
                if d[k - 1] == k:
                    pred = tuple(reversed(d[:k])) + d[k:]
                    if pred not in seen:
                        seen[pred] = depth
                        nxt.append(pred)
                        if depth > deepest[0]:
                            deepest = (depth, pred)
        cur = nxt
    return deepest[0], deepest[1]

for n in range(1, 9):
    T, d = topswops_max(n)
    print(f'n={n:2d}  T(n)={T:2d}  one maximal deal={d}')

The script prints $T(1) = 0, T(2) = 1, T(3) = 2, T(4) = 4, T(5) = 7, T(6) = 10, T(7) = 16, T(8) = 22$, matching the OEIS sequence and validating the algorithm; extending it to $n = 13$ reproduces $T(13) = 80$ given enough memory.