Who Keeps the Money on the Floor?

Five colleagues sit around a table and play for a found $100 bill. Each turn one of three equally likely things happens: the bill moves one seat left, moves one seat right, or the game ends and whoever is holding it wins. The bill starts in front of you. What is your chance of winning?

The Riddler, FiveThirtyEight(original post)

Solution

Track the bill by how far it sits from you, and let the symmetry of the round table do the work. With five seats, the bill is either in front of you, one seat away (left or right, the same by symmetry), or two seats away. Write $P_0$, $P_1$, $P_2$ for your chance of eventually winning when the bill is at each of those distances. Every turn splits three ways with probability $\tfrac13$ each, so one step of the game gives one equation per position.

From your own seat, this turn ends the game in your favour with probability $\tfrac13$, and otherwise the bill moves to a neighbouring seat, distance $1$ either way: $$P_0 = \tfrac13 + \tfrac13 P_1 + \tfrac13 P_1 = \tfrac13 + \tfrac23 P_1 .$$ One seat away, the game might end (you do not win, so no $\tfrac13$ term), or the bill moves to your seat or to distance $2$: $$P_1 = \tfrac13 P_0 + \tfrac13 P_2 .$$ Two seats away, the bill moves to distance $1$ or stays at distance $2$ (the seat two to the other side is also distance $2$ around the five-seat ring): $$P_2 = \tfrac13 P_1 + \tfrac13 P_2 .$$ The last equation gives $P_2 = \tfrac12 P_1$. Substituting into the middle one, $P_1 = \tfrac13 P_0 + \tfrac16 P_1$, so $P_1 = \tfrac25 P_0$. Then the first equation reads $P_0 = \tfrac13 + \tfrac23\cdot\tfrac25 P_0 = \tfrac13 + \tfrac{4}{15}P_0$, which gives $\tfrac{11}{15}P_0 = \tfrac13$, hence $$P_0 = \boxed{\dfrac{5}{11}} \approx 0.4545 ,$$ with $P_1 = \tfrac{2}{11}$ and $P_2 = \tfrac{1}{11}$ for the others. You hold seniority and a little better than a one-in-three share of an even split, but the bill wanders away more often than not.

Extra Credit

What if there were $N$ statisticians?

Solution

Let $f(j)$ be your chance of winning when the bill is $j$ seats away, around a ring of $N$. The same one-step reasoning gives $$f(j) = \tfrac13\,[\,j=0\,] + \tfrac13 f(j-1) + \tfrac13 f(j+1),$$ where the bracket is $1$ when $j=0$ and $0$ otherwise, and seats are counted modulo $N$. Away from your seat the recurrence is $f(j-1) - 3f(j) + f(j+1) = 0$, whose characteristic equation $r^2 - 3r + 1 = 0$ has roots $$r = \frac{3 \pm \sqrt5}{2} = \varphi^{2},\ \varphi^{-2}, \qquad \varphi = \frac{1+\sqrt5}{2}.$$ The golden ratio appearing here is the tell that the answer lives among the Fibonacci numbers $F_N$ and the Lucas numbers $L_N$. Imposing the ring’s symmetry $f(j)=f(N-j)$ and the source condition at your seat and simplifying, the starting player’s chance is $$\boxed{\,P_0(N) = \begin{cases} \dfrac{F_N}{L_N}, & N \text{ odd},\\[2.2ex] \dfrac{L_N}{5\,F_N}, & N \text{ even}.\end{cases}}$$ For $N=5$ this is $F_5/L_5 = 5/11$, as before. Both branches march to the same limit: since $L_N/F_N \to \sqrt5$, the starting player’s edge erodes toward $1/\sqrt5 \approx 0.4472$ as the table grows. With infinitely many colleagues you are barely better off than anyone else, which is the quietly beautiful endpoint of the problem.

The computation

Solve the system exactly for a range of table sizes and check the boxed Fibonacci-Lucas law term by term. Then, for the five-seat table, play the actual game many times to confirm $5/11$.

import numpy as np, random

def win_prob(N):                          # exact: solve the linear system
    A, b = np.zeros((N, N)), np.zeros(N)
    for j in range(N):
        A[j, j] += 1
        A[j, (j - 1) % N] -= 1 / 3
        A[j, (j + 1) % N] -= 1 / 3
        if j == 0:
            b[j] = 1 / 3
    return np.linalg.solve(A, b)[0]

def fib(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a

def luc(n):
    a, b = 2, 1
    for _ in range(n): a, b = b, a + b
    return a

for N in range(1, 9):
    law = fib(N) / luc(N) if N % 2 else luc(N) / (5 * fib(N))
    print(f"N={N}: solve={win_prob(N):.6f}  law={law:.6f}")
print("limit 1/sqrt5 :", round(1 / 5 ** 0.5, 6))

random.seed(0)
wins = 0
for _ in range(400_000):                  # play the five-seat game
    pos = 0
    while True:
        r = random.random()
        if r < 1 / 3:
            wins += (pos == 0); break
        pos = (pos + (1 if r < 2 / 3 else -1)) % 5
print("N=5 simulated :", round(wins / 400_000, 4), " 5/11 =", round(5 / 11, 4))
# N=1: solve=1.000000  law=1.000000
# N=2: solve=0.600000  law=0.600000
# N=3: solve=0.500000  law=0.500000
# N=4: solve=0.466667  law=0.466667
# N=5: solve=0.454545  law=0.454545
# N=6: solve=0.450000  law=0.450000
# N=7: solve=0.448276  law=0.448276
# N=8: solve=0.447619  law=0.447619
# limit 1/sqrt5 : 0.447214
# N=5 simulated : 0.4553  5/11 = 0.4545