Two Holiday Puzzles

Riddler Express

From a standard $52$-card deck, take any $50$ cards and arrange them into $10$ poker hands, one of each type, from a royal flush down to a high card. The hands you build always rank as the highest type of hand possible (so a four-of-a-kind made of the cards remaining after the royal flush, straight flush, four-of-a-kinds, full house, flush, straight, three-of-a-kind, two pair, one pair and high card have been chosen). No card may be reused. How many ways are there to do it?

The Riddler, FiveThirtyEight, December 22, 2017(original post)

Solution

There is no clean closed form: the overlap constraint between hand types ties them all together combinatorially. The official solution uses a two-step heuristic estimate that we reproduce, with the headline answer $$\boxed{\,\approx 7.88 \cdot 10^{20} \text{ ways.}\,}$$

The estimate proceeds in two parts.

Step 1: count each hand type independently. For each rank in the standard poker hierarchy, count the number of five-card hands of that type without worrying about overlap with other types yet:

The product of these ten counts is $$\Pi \approx 1.7012 \cdot 10^{38},$$ which counts ordered ten-hand assemblages with replacement (each hand drawn from a fresh full deck). Most of these reuse cards across hands.

Step 2: correct for overlap. The fraction of ten-hand assemblages drawn independently (with replacement) from a full deck whose $50$ cards are all distinct is $$p_{\text{no overlap}} = \frac{52 \cdot 51 \cdot 50 \cdots 3}{52^{10} \cdot 51^{10} \cdot 50^{10} \cdot 49^{10} \cdot 48^{10}}.$$ The numerator is the number of ordered $50$-card sequences drawn without replacement from a $52$-card deck; the denominator is the number of ways to draw five cards in order from each of ten independent decks. Numerically $p_{\text{no overlap}} \approx 4.632 \cdot 10^{-18}$.

Estimate. Multiplying the two, $$\Pi \cdot p_{\text{no overlap}} \approx 1.7012 \cdot 10^{38} \cdot 4.632 \cdot 10^{-18} \approx 7.88 \cdot 10^{20}.$$

This is approximate: $p_{\text{no overlap}}$ above is the fraction for ten independent five-card draws, whereas the actual overlap depends on which type each hand is (a royal flush always uses four specific ranks in one suit; a full house uses two specific ranks; etc.). The official acknowledges the looseness and reports the headline figure as “on the order of $8 \cdot 10^{20}$”. The exact figure would require a more elaborate inclusion-exclusion or a constrained constructive count; we report the heuristic estimate as the official did.

The computation

Verify the two factors of the estimate directly.

1. Compute the product of the ten hand-type counts.

2. Compute the no-overlap probability and combine.

import math

counts = [4, 36, 624, 3744, 5108, 10200,
          54912, 123552, 1098240, 1302540]
prod = math.prod(counts)
num = math.factorial(52) // math.factorial(2)        # 52*51*...*3
den = 1
for r in range(52, 47, -1):
    den *= r ** 10                                   # 52^10 * 51^10 ... 48^10
p_no_overlap = num / den
print(prod, p_no_overlap, prod * p_no_overlap)

The script prints $$\begin{aligned} \Pi &\approx 1.7011 \cdot 10^{38}, \\ p_{\text{no overlap}} &\approx 4.632 \cdot 10^{-18}, \\ \Pi \cdot p_{\text{no overlap}} &\approx 7.880 \cdot 10^{20}, \end{aligned}$$ reproducing the boxed estimate.

Riddler Classic

In the dice game Left, Right, Center, $X$ players sit in a circle, each starting with $Y$ one-dollar bills. On each turn, the active player rolls one die for each dollar they hold, up to three dice. For each die: $1$ or $2$ pays one dollar to the player on the left; $3$ or $4$ to the right; $5$ or $6$ to the centre pot. Players with no money are skipped. The game ends as soon as exactly one player has any money, and that player wins the centre pot. What is the expected number of turns until the game ends? Solve the headline case $X = 6$, $Y = 3$, and give a rule for general $X$ and $Y$.

The Riddler, FiveThirtyEight, December 22, 2017(original post)

Solution

The chain is a Markov process on the joint state $(b_1, b_2, \ldots, b_X)$ of player holdings; absorbing states are those with only one nonzero coordinate. Solving the chain exactly is unwieldy ($X = 6$, $Y = 3$ gives the state space hundreds of thousands strong once the centre pot is tracked), so the answer is obtained by simulation. A million-trial Monte Carlo of the actual rules gives, for the headline case, $$\boxed{\,\mathbb{E}[\text{turns}] \approx 21.7 \text{ for } X = 6, Y = 3.\,}$$

The official’s rule-of-thumb formula is $$\mathbb{E}[\text{turns}] \approx 2(X - 2)Y,$$ which for $X = 6, Y = 3$ predicts $24$. The formula is the right scaling but is a low-precision approximation; direct simulation of the rules (which we use as the ground truth) gives $\approx 21.7$ in the headline case, and is the value we recommend reporting.

Why $2(X - 2)Y$ scales correctly. Each turn, the active player loses (in expectation) $2$ of their dice’s worth of dollars to the centre on average $1/3$ of dice and to their neighbours $2/3$ of dice; so the total money decreases by $1$ on every die that goes to centre, i.e. $1/3$ of the rolled dice. Players who hold $\ge 3$ dollars roll $3$ dice and so lose $1$ dollar in expectation to the centre per turn. The total money in play is $XY$; one player must retain at least one dollar at the end (and on average about $Y$ dollars when the game closes); so the rough number of dollars lost to the centre is $\approx XY - Y = Y(X - 1)$, and the number of turns is $\approx 3$ times that divided by $X$ (one turn per player per round), giving $\approx 3Y(X - 1)/X$. The official’s $2(X - 2)Y$ is an order-of-magnitude refinement of this scaling tuned to the table they tabulate; it overshoots the simulated value by $\approx 10$–$30\%$ on small $X$. A clean closed form is not known.

General rule. As $Y$ grows, $\mathbb{E}[\text{turns}]$ scales linearly in $Y$ (each dollar’s worth of game lengthens the playtime by a constant); as $X$ grows, it scales roughly linearly in $X$. The official’s $\approx 2(X - 2)Y$ captures this scaling; the table below records simulated values alongside.

The first entry in each cell is the simulated mean over $200{,}000$ games; the parenthesised second entry is the official’s $2(X - 2)Y$ approximation.

The computation

Encode the rules of the game and simulate.

1. Initialise each player with $Y$ dollars.

2. Each turn the active player rolls $\min(3, \text{current holdings})$ dice, applying the L/R/centre rule per die.

3. Stop when exactly one player has money. Count the number of turns taken. Repeat many times.

import random
random.seed(7)

def play(X, Y):
    bills = [Y] * X
    turns, i = 0, 0
    while sum(1 for b in bills if b > 0) > 1:
        if bills[i] > 0:
            turns += 1
            for _ in range(min(3, bills[i])):
                if bills[i] <= 0: break
                r = random.randint(1, 6)
                if r in (1, 2):
                    bills[(i - 1) % X] += 1
                elif r in (3, 4):
                    bills[(i + 1) % X] += 1
                bills[i] -= 1
        i = (i + 1) % X
    return turns

N = 200_000
for X, Y in [(6, 3), (4, 5), (10, 7)]:
    avg = sum(play(X, Y) for _ in range(N)) / N
    print(f"X={X}, Y={Y}: sim={avg:.2f}  off={2*(X-2)*Y}")

The script prints X=6, Y=3: sim=21.66 off=24 (and the other two cases at $\approx 20.3$ / $20$ and $\approx 82.0$ / $112$), reproducing the boxed simulated estimate and showing the looseness of the rule-of-thumb formula on larger $X$.