En Garde! Can You Win The Fencing Relay?

Riddler Express

A single elevator serves four stories: the garage $G$, then floors $1$, $2$, $3$. It is malfunctioning and stops at every floor, forever cycling $G, 1, 2, 3, 2, 1, G, 1, 2, \dots$ I head for it on a uniformly random floor and hear the doors close, with no idea where the car is. On average, how many stops until it opens on my floor (counting that stop)? Extra credit: with $N$ stories instead of four?

Solution

The car’s route is a cycle of $L = 2(N-1)$ stops: up through $G, 1, \dots, N-1$ and back down to $1$, then $G$ again. The garage and the top floor are each visited once per cycle; every floor in between is visited twice. Hearing the doors close tells me only that the car sits at one of the $L$ stops, each equally likely, and I count forward to the next stop at my floor.

For a floor visited once per cycle, the forward distances from the $L$ possible just-closed positions are $1, 2, \dots, L$ in some order, so the wait averages $\tfrac{L+1}{2}$. A floor visited twice splits the cycle into two arcs of lengths $a$ and $b = L-a$; the forward wait averages $$\frac{1}{L}\!\left(\frac{a(a+1)}{2} + \frac{b(b+1)}{2}\right).$$ Floor $j$ (for $1 \le j \le N-2$) is reached going up at stop $j$ and coming down at stop $L-j$, so its arcs are $a = 2j$ and $b = L-2j$. Averaging the two single-visit floors and the $N-2$ double-visit floors over all $N$ starting floors collapses to a strikingly simple result: $$\mathbb{E}[\text{stops}] = \boxed{\dfrac{4N+1}{6}}, \qquad N = 4 \Rightarrow \frac{17}{6} \approx \boxed{2.83}.$$

The computation

Run the cycle exactly: for every starting floor and every just-closed position, count stops to the next opening on that floor, and average.

from fractions import Fraction as F
def avg(n):
    cyc = list(range(n)) + list(range(n - 2, 0, -1))   # floor at each stop
    L, total, count = len(cyc), F(0), 0
    for my in range(n):                                 # my floor, uniform
        for start in range(L):                          # doors just closed here
            k = 1
            while cyc[(start + k) % L] != my: k += 1
            total += k; count += 1
    return total / count
print(avg(4), float(avg(4)))                            # 17/6, 2.833
print([avg(n) for n in (5, 6, 10)])                     # match (4n+1)/6

Riddler Classic

You coach three fencers: the strongest wins each point with probability $0.75$, the middle one $0.5$, the weakest $0.25$. In a relay your first fencer duels until someone reaches $15$, then a second takes over (from the running score) until someone reaches $30$, then the third until someone reaches $45$. You choose the order. Which order, and what is your chance of winning?

Solution

Each leg adds points from the spot the last leg left off, so the order matters even though all three fencers eventually take a turn. The instinct to lead with your best fencer is wrong. Put the weakest first: an early leg can do least harm there, with the whole relay still ahead to recover, while the strongest fencer is most valuable last, fencing the decisive points to $45$. Computing the win probability exactly for all six orders confirms it, with the strongest-last orders far ahead: $$\boxed{\text{weakest},\ \text{middle},\ \text{strongest}}, \qquad \Pr(\text{win}) \approx \boxed{0.932}.$$ Swapping the front two to middle-weakest-strongest costs about a point ($0.925$); leading with the strongest and ending on the weakest collapses to $0.068$.

The computation

Track the exact score distribution leg by leg: each leg races the running score to its threshold, point by point, and the three legs compose into the final win probability for every ordering.

from fractions import Fraction as F
from itertools import permutations
def leg(p, target, dist):                # advance score dist to a threshold
    out = {}
    for (a, b), pr in dist.items():
        cur = {(a, b): pr}
        while cur:
            nxt = {}
            for (x, y), q in cur.items():
                if x >= target or y >= target:
                    out[(x, y)] = out.get((x, y), F(0)) + q
                else:
                    nxt[(x + 1, y)] = nxt.get((x + 1, y), F(0)) + q*p
                    nxt[(x, y + 1)] = nxt.get((x, y + 1), F(0)) + q*(1 - p)
            cur = nxt
    return out
P = {'w': F(1, 4), 'm': F(1, 2), 's': F(3, 4)}
res = []
for order in permutations('wms'):
    d = {(0, 0): F(1)}
    for who, tgt in zip(order, (15, 30, 45)):
        d = leg(P[who], tgt, d)
    win = sum(pr for (a, b), pr in d.items() if a >= 45)
    res.append((order, float(win)))
for o, w in sorted(res, key=lambda r: -r[1]): print(o, round(w, 3))