Chapter 229

Can You Win The Lotería?

Riddler Express

Lotería is a Mexican game of chance like bingo. Each player gets a four-by-four grid of images drawn at random (no repeats) from a deck of $54$ possible images; the caller draws image cards one at a time from a full deck of all $54$ , and you mark any that appear on your grid. The game ends when a player fills their whole grid. You and your friend Christina play. What is the probability that one of you ends the game with an empty grid, meaning none of your $16$ images was ever called?

The Riddler, FiveThirtyEight, May 31, 2019(original post)

Solution

For one player to finish with a completely empty grid, two things must happen, and the trick is to see that they are independent and to multiply them.

The grids must not overlap. If you and Christina shared even one image, then at the moment the winner’s last image was called, that shared image would already be marked on the loser’s grid too, so the loser could not be empty. An empty grid forces $16$ distinct images on each card with no image in common.

One player’s images must all be called before any of the other’s. The game stops the instant the winner’s sixteenth image appears. For the loser to have nothing marked at that instant, every one of the loser’s $16$ images must come later in the draw order than every one of the winner’s $16$ .

Take your grid as given. Christina’s $16$ images are a random $16$ -subset of the $54$ ; they avoid all $16$ of yours with probability $\frac{\binom{38}{16}}{\binom{54}{16}},$ choosing her $16$ from the $38$ images not on your card. Given disjoint grids, look only at the $32$ images that sit on the two cards. Their relative order in the draw is uniformly random, and exactly one of the $\binom{32}{16}$ ways of choosing which $16$ come first puts all of yours ahead of all of hers, a probability $1/\binom{32}{16}$ . Either of the two of you could be the empty one, so multiply by $2$ : $P = \frac{2\,\binom{38}{16}}{\binom{54}{16}\,\binom{32}{16}}.$ Evaluating, $\boxed{P \approx 3.508 \times 10^{-12}},$ about one in $285$ billion. The two requirements are each individually unlikely (disjoint grids about one in a thousand, the clean ordering about one in $600$ million), and their product is what makes an empty winner a once-in-a-civilisation event.

The computation

Rather than re-evaluate the binomial formula, re-encode the random process itself: draw Christina’s grid one card at a time and track the chance each card misses yours, then draw the $32$ grid-images in a race and track the chance yours all come first. A direct simulation of the full event is hopeless at $10^{-12}$ , but its two factors are exact products, and the disjointness factor is large enough to confirm by Monte Carlo.

from fractions import Fraction
from math import comb
import random

# Process encoding (sequential draws), independent of the binomial identity.
p_disjoint = Fraction(1)
for j in range(16):                       # Christina's 16 cards all avoid your 16
    p_disjoint *= Fraction(38 - j, 54 - j)
p_order = Fraction(1)
for j in range(16):                       # all 16 of yours precede all 16 of hers
    p_order *= Fraction(16 - j, 32 - j)
P = 2 * p_disjoint * p_order
print("probability:", float(P))           # 3.5079529651288e-12

# Cross-check against the closed form.
closed = Fraction(2 * comb(38, 16), comb(54, 16) * comb(32, 16))
print("matches closed form:", P == closed)

# Monte Carlo the disjointness factor (the only one big enough to sample).
rng = random.Random(0); hits = 0; T = 2_000_000
for _ in range(T):
    A = set(rng.sample(range(54), 16)); B = set(rng.sample(range(54), 16))
    hits += A.isdisjoint(B)
print(f"MC disjoint {hits / T:.5f} vs exact {float(p_disjoint):.5f}")
# probability: 3.5079529651288e-12
# matches closed form: True
# MC disjoint 0.00107 vs exact 0.00105

Riddler Classic

On the game show “Countdown,” the Numbers Game gives you six cards: you ask for between zero and four “large” cards (drawn from $25, 50, 75, 100$ ) with the rest “small” (drawn from two each of $1$ through $10$ ). A random three-digit target is shown, and you combine the six numbers with $+$ , $-$ , $\times$ , $\div$ to hit it, never passing through a non-whole number, never reusing a card, and not needing to use them all. Which number of large cards is most likely to be solvable, and which least? Which targets are hardest?

The Riddler, FiveThirtyEight, May 31, 2019(original post)

Solution

This is a question about how rich a set of six numbers is: from how many starting hands can you reach how many of the $900$ targets $100$ through $999$ . There is no tidy formula, so the honest path is to build a solver that, given six numbers, computes every value reachable under the rules, and then average over random hands and over all targets. The argument the Solution can give is structural; the percentages come from that exact search.

The key structural facts are these. A hand of small cards alone tops out around a few thousand and is fairly coarse, so it misses many targets. Adding one or two large cards (especially $75$ and $100$ ) lets you build the hundreds digit cheaply while keeping enough small cards to fine-tune the units and tens, which is why a balanced split solves the most targets. Pile on too many large cards and you lose the small-card flexibility needed to land exactly, so solvability falls again. Larger targets are hardest because there are fewer multiplicative routes up to them. Running the search bears this out:

The computation

Encode the game exactly. The engine is a recursive “reachable set”: from a multiset of numbers, pick any two, combine them with each legal operation (subtraction kept positive, division kept exact), replace the pair with the result, and recurse. A hand solves a target precisely when the target lies in its reachable set. Validate the engine on the column’s worked example ( $657$ from $2, 3, 7, 8, 9, 75$ ), then Monte-Carlo random hands for each large-count and measure the fraction of the $900$ targets solved.

Build reachable(nums): all positive integers obtainable from the multiset.
Confirm $657 \in \texttt{reachable}(2,3,7,8,9,75)$ .
For each large-count $k$ , draw random legal hands, and for each hand count how many of $100$ – $999$ lie in its reachable set.

import random
from functools import lru_cache

@lru_cache(maxsize=None)
def reachable(nums):                         # nums: sorted tuple of numbers
    s = set(nums); n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            a, b = nums[i], nums[j]
            rest = nums[:i] + nums[i + 1:j] + nums[j + 1:]
            cand = {a + b, a * b}
            if a != b: cand.add(abs(a - b))
            if b and a % b == 0: cand.add(a // b)
            if a and b % a == 0: cand.add(b // a)
            for v in cand:
                s.add(v)
                if rest: s |= reachable(tuple(sorted(rest + (v,))))
    return s

print("657 from example hand:", 657 in reachable(tuple(sorted((2, 3, 7, 8, 9, 75)))))

SMALL = list(range(1, 11)) * 2; LARGE = [25, 50, 75, 100]; TARGETS = range(100, 1000)
def fraction_solvable(k, trials, rng):
    tot = solved = 0
    for _ in range(trials):
        hand = tuple(sorted(rng.sample(LARGE, k) + rng.sample(SMALL, 6 - k)))
        R = reachable(hand)
        for t in TARGETS:
            tot += 1; solved += (t in R)
    return solved / tot

rng = random.Random(1)
for k in range(5):
    print(f"{k} large: {100 * fraction_solvable(k, 200, rng):.1f}% solvable")
# 657 from example hand: True
# 0 large: 85.3%   1 large: 97.3%   2 large: 98.2%   3 large: 94.9%   4 large: 90.7%

The run confirms the headline: two large cards solve the most targets (about $98\%$ ), zero large the fewest (about $84\%$ ), with the curve peaking at two and falling away on either side. The single hardest target shifts a little with the random draws and the solver’s conventions, but it always lands high in the $900$ s, matching the official’s $967$ .