Carpool Tickets

The Riddler for May 19, 2017. The Express is a beautiful application of linearity of expectation: four drivers with per-drive ticket rates $0.10$, $0.15$, $0.20$, $0.25$ each accumulate $3$ tickets before losing their licenses, and the total number of trips until the carpool dies is the simple sum $30 + 20 + 15 + 12 = 77$ trips, or $38.5$ days. The Classic, Battle for Riddler Nation Round $2$, is a Colonel Blotto castle royale whose “answer” is the empirical tournament winner of reader-submitted plans; we defer it for the same reason we deferred its February predecessor.

Riddler Express

Four co-workers carpool to work each day. Each morning, one is selected uniformly at random to drive to work; each evening, one is selected uniformly at random to drive home. Each driver has a chance of being ticketed for speeding on a given trip. Driver $A$’s chance is $10\%$, Driver $B$’s is $15\%$, Driver $C$’s is $20\%$, Driver $D$’s is $25\%$. The state revokes a driver’s license immediately upon her third ticket, and that driver stops driving in the carpool. At most one ticket is issued per morning and at most one per evening (the lone officer on the route). Starting from no tickets, how many days do we expect the carpool to last until every driver has lost her license?

The Riddler, FiveThirtyEight, May 19, 2017(original post)

Solution

The neat trick is to count driver trips, not days. The randomisation rule says which active driver gets each trip, but the eventual loss of every license is fated to take a specific (random) number of trips per driver. By linearity of expectation, the total number of trips is the sum across drivers.

Trips per driver. A driver with ticket probability $p$ per trip needs $3$ tickets to lose her license. Counted in trips behind the wheel, this is the sum of three independent geometric random variables, one per ticket: trips between tickets are Geometric($p$) with mean $1/p$. So the expected number of trips a driver takes from her first drive to her license being revoked is $$\mathbb{E}[\text{trips for driver } i] \;=\; \frac{3}{p_i}.$$ Why linearity bypasses the scheduling. The total trips of the carpool is the sum, over drivers, of trips each one personally takes. Whether a driver’s trips are clumped early or scattered with idle weeks in between is determined by the random scheduling, but the count of her own trips until her third ticket is independent of how trips are allocated to others. Sum the individual expectations: $$\begin{aligned} \mathbb{E}[\text{total trips}] &= \frac{3}{0.10} + \frac{3}{0.15} + \frac{3}{0.20} + \frac{3}{0.25}\\ &= 30 + 20 + 15 + 12 \;=\; 77. \end{aligned}$$ Each day comprises two trips (morning and evening), so $$\mathbb{E}[\text{days}] \;=\; \frac{77}{2} \;=\; 38.5.$$ $$\boxed{\,\mathbb{E}[\text{days until all four lose their licenses}] \;=\; 38.5.\,}$$

A subtle point: the expectation per driver $3 / p_i$ does not require independence from the scheduling, only the geometric distribution of trips-between-tickets for a given driver. The scheduling rule (uniform over active drivers, two trips per day) affects when each trip happens, but each driver’s own trip-count to license revocation is a fixed-mean variable, and totals add.

The computation

Encode the rule itself: simulate days of randomly assigned trips, accumulate tickets, retire drivers at $3$, and stop when the active list is empty. Confirm the empirical expected days matches $38.5$.

import random

P = [0.10, 0.15, 0.20, 0.25]                              # A, B, C, D

def run_carpool(rng):
    tickets = [0] * 4
    trips = 0
    while True:
        active = [i for i, t in enumerate(tickets) if t < 3]
        if not active: return trips
        i = rng.choice(active)
        if rng.random() < P[i]:
            tickets[i] += 1
        trips += 1

rng = random.Random(0)
TRIALS = 500_000
total_trips = sum(run_carpool(rng) for _ in range(TRIALS))
avg_trips = total_trips / TRIALS
print(f"empirical trips = {avg_trips:.3f}, days = {avg_trips/2:.3f}")
# empirical trips = 77.051, days = 38.525

The simulation converges to $77$ trips on average, equivalently $38.5$ days, agreeing with the linearity calculation to three significant figures.

Riddler Classic

Battle for Riddler Nation, Round 2. In a distant war-torn land, there are $10$ castles worth $1, 2, \ldots, 10$ victory points. You and your archenemy each have $100$ soldiers to distribute among the $10$ castles. Whoever sends more soldiers to a castle conquers it and wins its points; ties split. Submit a distribution of $100$ soldiers across $10$ castles. The tournament awards the crown to whichever submission wins the most one-on-one matchups against all other reader submissions.

The Riddler, FiveThirtyEight, May 19, 2017(original post)

Deferred (participatory contest)

The Classic is a Colonel Blotto castle royale whose “answer” has no closed form: the winner is the strategy that, in the actual tournament of reader-submitted plans, wins the most one-on-one matchups. There is no Nash equilibrium for a player to box; the game is multiplayer in spirit, and the question explicitly invites empirical adaptation to the publicly released earlier-round submissions on GitHub.

We defer this puzzle for the same reason as the February $3, 2017$ Round $1$: it is a participatory empirical contest, not a problem with a derivable answer. Boxing an arbitrary distribution (e.g., the centroid of the previous round’s submissions, or an iterated best-response under some assumed prior) would dress one heuristic as the answer. The official write-up reports the actual tournament winner; this is not a quantity that can be rederived from the puzzle statement alone.

This is the fourth deferral in the build, after the $2016$-$10$-$28$ gerrymander Express+Classic, the $2016$-$11$-$11$ map-colouring game, and the $2017$-$02$-$03$ Round $1$ Riddler Nation. All four sit in the same category: questions whose “answer” is empirical/participatory rather than derivable.