Can You Light Up the Pinball Machine?

A pinball game has four lanes, all initially unlit. Every flip sends the ball through exactly one of the four lanes, chosen at random, and toggles that lane: an unlit lane becomes lit, and a lit lane becomes unlit. On average, how many flips does it take until all four lanes are lit?

The Fiddler, Zach Wissner-Gross, September 29, 2023(original post)

The official solution appeared in the post of October 6, 2023 and gives $64/3$ flips for the main puzzle and $N = 6$ for the Extra Credit. Both agree with the answers below.

Solution

Which lanes are lit does not matter, only how many. With $k$ of the four lit, the next ball goes through an unlit lane with probability $(4 - k)/4$, lighting it, and through a lit lane with probability $k/4$, putting it out. So the number lit moves one step up or down along $0, 1, 2, 3, 4$.

To get from $0$ lit to $4$ lit, the count must pass through each step $k \to k + 1$ for the first time, in order. So the expected total is the sum of the expected waits $t_k$ for each of those first crossings. Each $t_k$ follows from the one before it:

• From $0$ lit, any lane lights, so $t_0 = 1$.

• From $k$ lit, one flip either lights a new lane (probability $(4 - k)/4$), and the wait is over, or puts one out (probability $k/4$). In the second case it takes $t_{k-1}$ flips on average to get back to $k$, and then a fresh wait $t_k$. So $$t_k \;=\; 1 + \frac{k}{4}\bigl(t_{k-1} + t_k\bigr), \qquad\text{that is,}\qquad t_k \;=\; \frac{4 + k\,t_{k-1}}{4 - k} .$$

Working up the steps: $$t_0 = 1, \qquad t_1 = \frac{4 + 1}{3} = \frac53,$$ $$t_2 = \frac{4 + 2 \cdot \frac53}{2} = \frac{11}{3}, \qquad t_3 = \frac{4 + 3 \cdot \frac{11}{3}}{1} = 15 .$$ The last step is by far the slowest: with three lanes lit, the ball finds the dark one only a quarter of the time, and three times as often it undoes earlier progress. Adding the four waits, $$\boxed{\ 1 + \frac53 + \frac{11}{3} + 15 \;=\; \frac{64}{3} \;\approx\; 21.33 \text{ flips}. \ }$$

The computation

The program writes down the defining equations for the expected number of flips still needed, $f(k)$, with $k$ lanes lit: $f(N) = 0$, and otherwise one flip followed by $f(k - 1)$ or $f(k + 1)$ with the chances above. It solves them exactly, with fractions, by elimination. It does not use the step-by-step waits of the solution.

from fractions import Fraction

def expected_flips(n):
    """Expected flips to light all n lanes, starting dark.
    f[k] = expected flips still needed with k lanes lit:
      f[n] = 0,
      f[k] = 1 + (k/n) f[k-1] + ((n-k)/n) f[k+1].
    Solved exactly by eliminating down the chain: write
    f[k] = A[k] + B[k] f[k+1], then substitute back up."""
    A, B = [], []
    for k in range(n):
        down, up = Fraction(k, n), Fraction(n - k, n)
        a_prev, b_prev = (A[-1], B[-1]) if k else (0, 0)
        scale = 1 - down * b_prev
        A.append((1 + down * a_prev) / scale)
        B.append(up / scale)
    f = Fraction(0)                  # f[n]
    for k in reversed(range(n)):
        f = A[k] + B[k] * f
    return f

print("main:", expected_flips(4))

It prints

main: 64/3

Extra Credit

With $N$ lanes, let $E(N)$ be the average number of flips until all are lit. Each extra lane roughly doubles $E$, but not exactly. For which $N$ is the ratio $E(N + 1)/E(N)$ smallest?

Solution

With $N$ lanes the same reasoning gives $t_0 = 1$ and $$t_k \;=\; \frac{N + k\,t_{k-1}}{N - k}, \qquad E(N) \;=\; t_0 + t_1 + \dots + t_{N-1} .$$ This recursion has a tidy solution. Scale each wait by a binomial coefficient, $s_k = \binom{N-1}{k} t_k$. Since $\binom{N-1}{k} \frac{1}{N - k} = \frac1N\binom{N}{k}$ and $\frac{k}{N}\binom{N}{k} = \binom{N-1}{k-1}$, the recursion becomes $$s_k \;=\; \binom{N}{k} + \binom{N-1}{k-1} t_{k-1} \;=\; \binom{N}{k} + s_{k-1} .$$ So $s_k$ is a running total of binomial coefficients, and $$t_k \;=\; \frac{\binom{N}{0} + \binom{N}{1} + \dots + \binom{N}{k}}{\binom{N-1}{k}}, \qquad E(N) \;=\; \sum_{k=0}^{N-1} t_k .$$ For $N = 4$ this gives $1, \frac53, \frac{11}{3}, 15$ again.

Why is $E$ close to doubling? The last wait dominates: its numerator is every binomial coefficient except the last, $2^N - 1$, over $\binom{N-1}{N-1} = 1$. The next wait is about $2^N/(N - 1)$, and the rest are much smaller. So $E(N)$ is a little more than $2^N$, and the ratio $E(N+1)/E(N)$ is a little less than $2$ for large $N$, creeping back up towards $2$. For small $N$ the ratio starts well above $2$ ($E(1) = 1$, $E(2) = 4$). So it falls, bottoms out, and rises. Exact values show where:

The minimum among these is at $N = 6$. To rule out a smaller ratio for some large $N$, bound $E$ from both sides. From below, the last wait alone gives $E(N + 1) \ge 2^{N+1} - 1$. From above, for $N \ge 5$: the waits $t_0 = 1$ and $t_1 = (N + 1)/(N - 1)$ add to at most $3$; the last wait is below $2^N$; the next is below $2^N/(N - 1)$; and each of the other $N - 4$ waits has a numerator below $2^N$ and a denominator at least $\binom{N-1}{2}$, so together they are below $2^N \cdot 2/(N - 1)$. Hence $$E(N) \;<\; 2^N\left(1 + \frac{3}{N - 1}\right) + 3 ,$$ and so $$\frac{E(N + 1)}{E(N)} \;>\; \frac{2^{N+1} - 1}{2^N\bigl(1 + \frac{3}{N-1}\bigr) + 3} .$$ Apart from the negligible $-1$ and $+3$, the right side is $2(N - 1)/(N + 2)$, which exceeds $151/78$ once $N \ge 92$, and the $-1$ and $+3$ cannot change that. The exact computation covers every $N$ up to $100$, so $$\boxed{\ N = 6, \qquad \frac{E(7)}{E(6)} = \frac{151}{78} \approx 1.936 . \ }$$

The computation

The equation solver from The computation above, run for every $N$ up to $101$, gives the exact ratios up to $N = 100$; the program also confirms that they rise steadily after the minimum.

E = {n: expected_flips(n) for n in range(1, 102)}
ratio = {n: E[n + 1] / E[n] for n in range(1, 101)}
best = min(ratio, key=ratio.get)
print("extra credit: N =", best, " ratio =", ratio[best])
print("ratio rises after it:",
      all(ratio[n] < ratio[n + 1] for n in range(best, 100)))

It prints

extra credit: N = 6  ratio = 151/78
ratio rises after it: True