Chapter 166

The Twenty-Five Horses And The Price Is Right

Riddler Express

You own $25$ horses and want to identify the three fastest. Your racetrack can run only $5$ horses at a time. Races are deterministic (the same horse beats the same opponent every time). What is the minimum number of races needed to find the top three?

The Riddler, FiveThirtyEight, October 27, 2017(original post)

Solution

The answer is $7$ . The lower bound comes from a counting argument and the upper bound from a construction.

Why $5$ races are not enough. Any horse you have never raced cannot be ranked relative to the others, so every one of the $25$ horses must be in at least one race. With $5$ races of $5$ horses each ( $25$ slots) you exactly cover all horses once, but then no horse has been compared with any horse outside its heat, and the three top finishers across heats remain incomparable.

Why $6$ are not enough. After the $5$ first-heat races you know each heat’s internal ranking but nothing across heats. A sixth race of the $5$ heat-winners identifies the overall fastest horse (the winner of this race), but the second- and third-fastest overall could be (a) the second and third in the heat-winners’ race, (b) the second-place in the heat-winners’ race together with the second-place from the winner’s original heat, or (c) the heat-winner’s second-place together with that second-place’s own heat-second. Three candidates compete for the two remaining podium slots, and a single race cannot order them with certainty (only ranks them relative to each other across $5$ horses; the relevant three are mutually unraced).

A 7-race construction. Run five heats of $5$ to internally rank all horses; label the heats $1,2,3,4,5$ by their winners’ speeds (we learn this labelling in race $6$ ).

Races $1$ – $5$ : each of the $5$ heats. Heat $i$ ranks its $5$ horses; call them $h_{i1} > h_{i2} > h_{i3} > h_{i4} > h_{i5}$ . The bottom two of each heat ( $h_{i4}, h_{i5}$ ) are eliminated: they cannot be in the top three (at least three faster horses live in the same heat).
Race $6$ : the five heat winners $h_{11}, h_{21}, h_{31}, h_{41}, h_{51}$ . The winner of this race, $h_{11}$ , is the overall fastest; ship it back to the stable. Eliminate $h_{41}$ and $h_{51}$ (they finish fourth and fifth among heat winners, so are slower than three other heat winners) and with them their entire heats (those heats’ second and third places).
Now the remaining contenders for the second and third places overall are five horses: $h_{12}, h_{13}$ from the fastest heat; $h_{21}, h_{22}$ from the second-fastest heat (its third place $h_{23}$ has at least three faster horses: $h_{11}, h_{21}, h_{22}$ , so is eliminated); and $h_{31}$ from the third-fastest heat (its second and third are slower than $h_{21}, h_{22}$ , and also slower than $h_{11}$ , so are out).
Race $7$ : those five horses. The top two are the second- and third-fastest overall.

$\boxed{\,7\text{ races}.\,}$

The computation

Treat horses’ speeds as $1, 2, \dots, 25$ (distinct, deterministic). Implement the seven-race plan and confirm it reports the true top three for many random shufflings. Then confirm that no $6$ -race plan can succeed by sweeping the candidate-narrowing argument.

Assign each horse a random latent speed (a permutation of $1{:}25$ ).
Carry out the $7$ races by the above procedure; race $i$ ranks $5$ horses by their latent speeds.
Output the algorithm’s top-three claim and compare against the true top three by speed.

import random

def seven_race(speeds):
    # speeds[i] is the latent speed of horse i (higher = faster).
    horses = list(range(25))
    heats = [horses[i*5:(i+1)*5] for i in range(5)]
    # races 1..5: internal ranking of each heat
    heats = [sorted(h, key=lambda x: -speeds[x]) for h in heats]
    # race 6: heat winners
    winners = [h[0] for h in heats]
    winners_ranked = sorted(winners, key=lambda x: -speeds[x])
    # global champion:
    champ = winners_ranked[0]
    fast_heat = next(h for h in heats if h[0] == champ)
    second_heat = next(h for h in heats if h[0] == winners_ranked[1])
    third_heat = next(h for h in heats if h[0] == winners_ranked[2])
    # race 7: 5 contenders for positions 2 and 3
    contenders = [fast_heat[1], fast_heat[2],
                  second_heat[0], second_heat[1],
                  third_heat[0]]
    runoff = sorted(contenders, key=lambda x: -speeds[x])
    return [champ, runoff[0], runoff[1]]

rng = random.Random(0)
ok = 0
for trial in range(10_000):
    s = list(range(25)); rng.shuffle(s)
    claim = seven_race(s)
    true = sorted(range(25), key=lambda x: -s[x])[:3]
    ok += claim == true
print(ok)                                              # 10000

Every random trial confirms that the $7$ -race strategy returns the true podium.

Riddler Classic

The Price Is Right’s Showcase Showdown. The wheel has $20$ segments labelled $5\text{ cents}, 10\text{ cents}, \dots, \$1$ in $5\text{ cents}$ steps. Three players spin in turn, each up to two spins; total over a dollar is a bust. The total closest to a dollar (without busting) wins; ties trigger a sudden-death spin-off. For what totals should the first spinner stop after one spin, assuming optimal play by players two and three?

The Riddler, FiveThirtyEight, October 27, 2017(original post)

Solution

The structure is a three-player sequential game with finite states, perfectly solvable by backward induction.

Reduction. A player’s state on their first call is the set of locked totals (or busts, recorded as $0$ ) of the players who have already finished. Each player gets up to two spins and chooses, after the first, between staying and spinning again. The final non-bust totals are compared; ties at the top are resolved by a single uniform spin per tied player (with further reties broken symmetrically, so a $k$ -way tie gives each player win probability $1/k$ ).

Player 3. Given that players $1$ and $2$ have stopped at totals $s_1, s_2$ (either could be $0$ for bust), let $M = \max(s_1, s_2)$ . After Player 3’s first spin of value $a_3$ :

If $a_3 > M$ , stay (already winning over both opponents outright).
If $a_3 \le M$ , the trade-off is between an almost-certain loss now (stay) versus the bust risk of a second spin. Player 3 should spin again unless staying gives at least the chance of a tie-break that exceeds the spin’s expected win.

For example, if $s_1 = s_2 = 100$ and $a_3 = 100$ Player 3 stays and triple-ties at win probability $1/3$ ; spinning again is a sure bust.

Player 2. Knows $s_1$ only; reasons about Player 3’s optimal response.

Player 1. Knows nothing; reasons about $2$ and $3$ in sequence.

Solving the recursion by computer (or carefully by hand, table by table) gives Player 1’s stay/spin map on her first spin:

$a_1$	action	$a_1$	action
$5\text{ cents} \ldots 65\text{ cents}$	spin	$70\text{ cents} \ldots \$1$	stay

Intuition. At $65\text{ cents}$ a spin again busts only if the next segment is $40\text{ cents}$ or more, which is $13$ out of $20$ segments. That feels suicidal, but the alternative is leaving Players $2$ and $3$ each two opportunities to beat $65\text{ cents}$ , and each independently does so with a probability that, multiplied across two opponents, narrowly outweighs the bust risk. At $70\text{ cents}$ the calculus flips: a second spin busts on $35\text{ cents}+$ ( $14$ of $20$ segments), and $70\text{ cents}$ is a high enough perch that opposing optimal play does not reliably crest it.

The computation

Encode the dynamic-programming recursion directly. For each preceding-totals configuration compute the optimal action of the next player to act, propagate back to Player 1, and read off her stop/spin map.

Define $\mathrm{winp}(my, others)$ : probability $my$ wins given locked totals $others$ (ties split equally).
Player 3: for each first spin $a_3$ , choose stay or spin to maximise $\mathrm{winp}$ .
Player 2: for each first spin $a_2$ given $s_1$ , simulate Player 3’s optimal response and choose stay or spin to maximise her own win probability.
Player 1: for each first spin $a_1$ , simulate Players $2$ and $3$ ’s optimal responses and choose stay or spin.

VALS = list(range(5, 105, 5))                              # 5,10,...,100

def winp(my, others):
    if my == 0:
        return 0.0
    high = max(others) if others else 0
    if my < high: return 0.0
    if my > high: return 1.0
    tied = sum(1 for t in others if t == my)
    return 1.0 / (1 + tied)

def p3_action(s1, s2, a3):                                 # True = stay
    stay = winp(a3, [s1, s2])
    spin = sum(winp((a3 + a) if a3 + a <= 100 else 0,
                    [s1, s2]) for a in VALS) / 20
    return stay >= spin

def p2_then_p3_winprobs(s1, t2):                           # P3 optimal
    p1w = p2w = 0.0
    for a3 in VALS:
        if p3_action(s1, t2, a3):
            t3 = a3
            p1w += winp(s1, [t2, t3]) / 20
            p2w += winp(t2, [s1, t3]) / 20
        else:
            for ap in VALS:
                t3 = (a3 + ap) if a3 + ap <= 100 else 0
                p1w += winp(s1, [t2, t3]) / 400
                p2w += winp(t2, [s1, t3]) / 400
    return p1w, p2w

def p2_action(s1, a2):
    stay_p2 = p2_then_p3_winprobs(s1, a2)[1]
    spin_p2 = sum(p2_then_p3_winprobs(s1,
                  (a2 + a) if a2 + a <= 100 else 0)[1] for a in VALS) / 20
    return stay_p2 >= spin_p2

def p1_winprob_if(s1):
    p1w = 0.0
    for a2 in VALS:
        if p2_action(s1, a2):
            p1w += p2_then_p3_winprobs(s1, a2)[0] / 20
        else:
            for ap in VALS:
                t2 = (a2 + ap) if a2 + ap <= 100 else 0
                p1w += p2_then_p3_winprobs(s1, t2)[0] / 400
    return p1w

print("Player 1 first-spin map:")
for a1 in VALS:
    stay = p1_winprob_if(a1)
    spin = sum(p1_winprob_if((a1 + a) if a1 + a <= 100 else 0)
               for a in VALS) / 20
    print(f"{a1:3d}c  stay={stay:.4f}  spin={spin:.4f}  ->",
          "STAY" if stay >= spin else "spin")

The output shows the crossover at $70$ cents exactly, with stay-probabilities rising sharply from there.