Two Paths Diverged In A City And I, I Took The Block Less Traveled By

Riddler Express

Major League Baseball’s playoffs use a single-game wild card round, then best-of-five Division Series, best-of-seven League Championship Series, and best-of-seven World Series. What is the highest possible regular-playoff winning percentage a team can post without winning the World Series? What is the lowest possible playoff winning percentage a team can post while winning the World Series? Extra credit: how close to these extremes has any team come?

The Riddler, FiveThirtyEight, September 21, 2018(original post)

Solution

Maximum without a ring. Win every game possible until the final loss in the final series. To maximise wins, take the wild card route (an extra forced win): one wild-card win, sweep the Division Series $3$-$0$, sweep the League Championship $4$-$0$, then push the World Series to seven games but lose it $4$-$3$. Totals: $1 + 3 + 4 + 3 = 11$ wins and $0 + 0 + 0 + 4 = 4$ losses. $$\boxed{\text{Best playoff record without a championship: } 11\text{-}4 = 73.3\%.}$$

Minimum with a ring. Skip the wild card (a division winner does not play one) and eke out every series: Division Series $3$-$2$, League Championship $4$-$3$, World Series $4$-$3$. Totals: $3 + 4 + 4 = 11$ wins and $2 + 3 + 3 = 8$ losses. $$\boxed{\text{Worst playoff record with a championship: } 11\text{-}8 = 57.9\%.}$$ Eleven wins is forced from the other side too: the road to the trophy demands three series wins of $3$, $4$ and $4$ games respectively.

Extra credit. The 2014 Kansas City Royals achieved the bleak record for losing finalists almost exactly: a wild-card win against the Athletics, a $3$-$0$ sweep of the Angels, a $4$-$0$ sweep of the Orioles, then dropping the World Series $4$-$3$ to the Giants. Their record is $11$-$4$, hitting the $73.3\%$ ceiling. The 2017 Houston Astros came close to the eke-it-out record: $3$-$1$ over the Red Sox, $4$-$3$ over the Yankees, $4$-$3$ over the Dodgers (winning the World Series). Their playoff record was $11$-$7$ for $61.1\%$, just shy of the $57.9\%$ floor.

The computation

Exhaustively enumerate all feasible playoff itineraries (each series an ordered set of wins and losses) and compute the win/loss percentages directly, separated by whether the World Series was won. The maximum among the non-winners and the minimum among the winners are the targets.

1. Enumerate the four series independently: wild card $\{\text{skip}, W, L\}$; Division Series outcomes $\{3\text{-}0, 3\text{-}1, 3\text{-}2, 0\text{-}3, 1\text{-}3, 2\text{-}3\}$; likewise LCS and WS over $\{4\text{-}0, \ldots, 3\text{-}4\}$.

2. For each itinerary, the team participates iff it wins every prior series. Compute total wins/losses; flag whether the World Series was won.

3. Track the maximum winning rate among non-winners and the minimum among winners.

def series_outcomes(N):
    # best of (2N-1) game results, as (wins, losses) for the team's record
    out = []
    for w in range(N + 1):
        for l in range(N + 1):
            if max(w, l) == N and min(w, l) < N:
                out.append((w, l))
    return out

DS = series_outcomes(3)   # best of 5
LCS = series_outcomes(4)  # best of 7
WS = series_outcomes(4)   # best of 7

best_no_ring = 0.0
best_no_ring_rec = None
worst_with_ring = 1.0
worst_with_ring_rec = None
for wc in [None, ('W',), ('L',)]:
    if wc is None:
        w0, l0, alive = 0, 0, True
    elif wc == ('W',):
        w0, l0, alive = 1, 0, True
    else:
        w0, l0, alive = 0, 1, False
    if not alive:
        continue
    for dw, dl in DS:
        if dw < 3: continue
        for lw, ll in LCS:
            if lw < 4: continue
            for sw, sl in WS:
                W = w0 + dw + lw + sw
                L = l0 + dl + ll + sl
                pct = W / (W + L)
                ring = sw == 4
                if ring:
                    if pct < worst_with_ring:
                        worst_with_ring = pct
                        worst_with_ring_rec = (W, L)
                else:
                    if pct > best_no_ring:
                        best_no_ring = pct
                        best_no_ring_rec = (W, L)
print(f"Best no-ring: {best_no_ring_rec} = {best_no_ring:.4f}")
print(f"Worst with ring: {worst_with_ring_rec} = {worst_with_ring:.4f}")

The script prints $11$-$4 = 0.7333$ and $11$-$8 = 0.5789$.

Riddler Classic

Your office is at the corner of a perfect city grid, and your apartment is five blocks west and ten blocks south of the office. You walk to and from the office along the streets, never taking a path longer than necessary. You insist on taking a different path each walk. How many days can you keep this up before you are forced to repeat a path? Extra credit: how does the answer scale if you live $M$ blocks west and $N$ blocks south of the office?

The Riddler, FiveThirtyEight, September 21, 2018(original post)

Solution

A shortest path from apartment to office goes only east and north, exactly five east blocks and ten north blocks. Each path is a sequence of fifteen moves with five E’s and ten N’s, and the number of such sequences is $$\binom{5 + 10}{5} \;=\; \binom{15}{5} \;=\; 3{,}003.$$ Reversing a path (walking it from office back to apartment) traces the same set of street segments in the opposite direction. The puzzle says "a different path along the streets each time", and the natural reading is that a path is the geometric route, so a sequence and its reverse describe the same path of streets. (The other reading, that a directed sequence counts as its own path, gives $3{,}003$ days of two unique walks each but doubles to $6{,}006$ uses; this matches less of the puzzle’s spirit.)

Each day the walker uses two of these routes (morning and evening). With $3{,}003$ routes available, the largest number of days with two fresh routes per day is $$\left\lfloor \tfrac{3003}{2} \right\rfloor \;=\; 1501.$$ On day $1502$ only one fresh route remains, forcing a repeat for the second leg. Hence $$\boxed{1{,}501 \text{ days, a little over four years.}}$$

Extra credit. For an apartment $M$ blocks west and $N$ blocks south, the number of shortest paths is the binomial coefficient $\binom{M + N}{N}$. Days of unique double-walks are $\lfloor \binom{M + N}{N} / 2 \rfloor$. For $M = 15, N = 10$ the count is $\binom{25}{10} = 3{,}268{,}760$, giving $1{,}634{,}380$ days, or roughly $4{,}477$ years. The path count grows much faster than linearly: doubling each dimension roughly squares the result for large $M, N$, by the central-limit / Stirling estimate $\binom{2M}{M} \sim 4^{M} / \sqrt{\pi M}$.

The computation

Enumerate the paths directly as binary strings with five $E$s and ten $N$s; count and confirm $3{,}003$. As a sanity check, compute it from the binomial coefficient formula.

1. Iterate over all length-$15$ binary strings with exactly $5$ ones; count.

2. Cross-check against $\binom{15}{5}$ and divide by $2$ for the day count.

3. Print $\binom{M + N}{N}$ for a small table of $(M, N)$ values.

from math import comb
from itertools import combinations

# Direct enumeration over length-15 binary strings with five 1s
n_paths = sum(1 for _ in combinations(range(15), 5))
print(f"Length-15 paths with 5 east moves: {n_paths}")
print(f"binom(15, 5) = {comb(15, 5)}")
print(f"Days of unique double-walks: {n_paths // 2}")

print("\nExtra credit table:")
for M, N in [(5, 10), (10, 10), (15, 10), (10, 20), (20, 20)]:
    p = comb(M + N, N)
    print(f"  M={M}, N={N}: paths={p:>10}, days={p // 2}")

The script prints $3003$ paths and $1501$ days, and tabulates the extra credit binomial coefficients.