Can You Decode The Riddler Lottery?

Riddler Express

In a best-of-seven World Series, one team hosts games $1, 2, 6, 7$ and the other hosts games $3, 4, 5$ (the series stops once a team wins four). If the home team wins each game with probability $54\%$, what is the probability the home team loses at least six games in a row? Extra credit: at least five in a row, and at least four in a row.

The Riddler, FiveThirtyEight, November 22, 2019(original post)

Solution

Each game the home team loses with probability $0.46$, independently, so a naive count of seven-game loss-streaks would just multiply $0.46$s and $0.54$s. The twist is that the series ends the moment a team reaches four wins, so some streaks are cut off before they can happen.

Write $H$ for a home win and $R$ for a home loss (a road win). For six consecutive home losses you might list $HRRRRRR$, $RRRRRRH$, $RRRRRRR$. But $HRRRRRR$ never occurs: after games $1$–$2$ ($HR$) the series is $1$-$1$, and after the road team takes games $3, 4, 5$ ($RRR$) one team is up $4$-$1$, so the series is over before games $6$ and $7$. Only $RRRRRRH$ and $RRRRRRR$ reach seven games, with probabilities $0.54 \cdot 0.46^6 = 0.512\%$ and $0.46^7 = 0.436\%$: $$\boxed{0.947\%},$$ a roughly once-a-century event. The extra credit, accounting for early stoppage the same way, gives about $\boxed{2.06\%}$ for five in a row and $\boxed{8.1\%}$ for four in a row.

The computation

Encode the series with its stopping rule: play games in the fixed host order, each host winning with probability $0.54$, stop at four wins for either team, and record the longest run of home losses among the games actually played. Sum the probabilities of all series whose longest run reaches the threshold.

hosts = ['A', 'A', 'B', 'B', 'B', 'A', 'A']
def prob_run_at_least(thresh):
    total = [0.0]
    def rec(i, aw, bw, run_max, run, prob):
        if aw == 4 or bw == 4:
            if run_max >= thresh: total[0] += prob
            return
        for host_wins, p in ((True, 0.54), (False, 0.46)):
            host = hosts[i]
            winner = host if host_wins else ('B' if host == 'A' else 'A')
            na, nb = (aw + (winner == 'A'), bw + (winner == 'B'))
            r = 0 if host_wins else run + 1       # home loss extends the run
            rec(i + 1, na, nb, max(run_max, r), r, prob * p)
    rec(0, 0, 0, 0, 0, 1.0)
    return total[0]
for t in (6, 5, 4):
    print(f">= {t} in a row: {100 * prob_run_at_least(t):.3f}%")
# >= 6 in a row: 0.947%   >= 5 in a row: 2.060%   >= 4 in a row: 8.096%

Riddler Classic

Five friends each pick five numbers from $1$ to $70$. All $25$ are distinct; all are composite; each has at least two distinct prime factors; and the product of the five numbers on every ticket is the same. What is that common product? Extra credit: in how many ways could they have chosen their numbers (as five unordered tickets)?

The Riddler, FiveThirtyEight, November 22, 2019(original post)

Solution

The numbers from $1$ to $70$ with at least two distinct prime factors (which forces composite) are $41$ in all. The five products are equal, so the product of all $25$ chosen numbers is the common product to the fifth power: every prime’s total exponent across the $25$ must be a multiple of $5$.

That requirement does the work. Take the prime $13$: only $26, 39, 52, 65$ carry a factor of $13$ (and each only one), so the total exponent of $13$ among any chosen numbers is at most $4$, never a positive multiple of $5$. Hence none of those four can be used, and the same logic rules out multiples of every prime $\ge 13$. What remains are exactly $25$ usable numbers built from the primes $2, 3, 5, 7, 11$, and their product is $2^{35} 3^{20} 5^{10} 7^5 11^5$, a perfect fifth power. Each ticket therefore has product $$\boxed{2^{7} \cdot 3^{4} \cdot 5^{2} \cdot 7 \cdot 11 = 19{,}958{,}400}.$$ For the extra credit, the number of ways to split those $25$ numbers into five unordered tickets each of product $19{,}958{,}400$ is $$\boxed{12{,}781},$$ found by search (multiplied by $5! = 120$ ways to hand the tickets to named friends, that is $1{,}533{,}720$ labelled outcomes).

The computation

Encode the constraints and search. Confirm the $25$ numbers each have at least two distinct primes and a common product of $19{,}958{,}400$, then count partitions into five product-equal groups by depth-first search, canonically placing the smallest unused number into the next group to avoid recounting group orderings.

from math import prod
from sympy import factorint
nums = [6,10,12,14,15,18,20,21,22,24,28,30,33,36,40,
        42,44,45,48,50,54,55,56,60,66]
T = 19_958_400
assert all(len(factorint(n)) >= 2 for n in nums)
assert round(prod(nums) ** 0.2) == T == 2**7 * 3**4 * 5**2 * 7 * 11

used = [False] * 25
def dfs(groups_done):
    if groups_done == 5: return 1
    first = next(i for i in range(25) if not used[i]); used[first] = True
    rest = [i for i in range(25) if not used[i]]
    count = 0
    def pick(pos, cnt, p):
        nonlocal count
        if cnt == 4:
            if p * nums[first] == T: count += dfs(groups_done + 1)
            return
        for j in range(pos, len(rest)):
            i = rest[j]
            if not used[i] and (T // nums[first]) % (p * nums[i]) == 0:
                used[i] = True; pick(j + 1, cnt + 1, p * nums[i]); used[i] = False
    pick(0, 0, 1); used[first] = False
    return count
print("common product:", T)
print("partitions:", dfs(0))
# common product: 19958400
# partitions: 12781

The search confirms the common product $19{,}958{,}400$ and the $12{,}781$ distinct ways to form the five tickets.