525,600 Minutes Of Math

Riddler Express

The song “Seasons of Love” from the musical “Rent” notes that a year has $525{,}600$ minutes, and indeed $365 \times 24 \times 60 = 525{,}600$. This raises an abstract mathematical question: given any three random integers $X$, $Y$, $Z$, what are the chances that their product is divisible by $100$?

The Riddler, FiveThirtyEight, February 8, 2019(original post)

Solution

The puzzle is asking for the natural density of triples $(X, Y, Z) \in \mathbb{Z}^{3}$ with $100 \mid XYZ$, made precise by sampling the residues of $X$, $Y$, $Z$ independently and uniformly. Because $100 = 4 \cdot 25$ and $\gcd(4, 25) = 1$, divisibility by $4$ and divisibility by $25$ are independent events (CRT), so $$\Pr(100 \mid XYZ) \;=\; \Pr(4 \mid XYZ) \cdot \Pr(25 \mid XYZ).$$ Compute the two factors separately by working with the $2$-adic and $5$-adic valuations of $X$, $Y$, $Z$.

Valuations. For a uniformly random integer (in the natural-density sense) and a prime $p$, the $p$-adic valuation $v_{p}$ has the distribution $$\Pr(v_{p} = k) \;=\; \frac{1}{p^{k}} \cdot \frac{p - 1}{p}, \qquad k = 0, 1, 2, \ldots,$$ which is geometric: an integer is divisible by $p^{k}$ with probability $1 / p^{k}$, and “exactly $p^{k}$ but no higher” with the displayed product. Because $v_{p}$ is additive under multiplication, $v_{p}(XYZ) = v_{p}(X) + v_{p}(Y) + v_{p}(Z)$. Divisibility of $XYZ$ by $p^{m}$ is the event $v_{p}(XYZ) \ge m$.

The $4 \mid XYZ$ factor. For $p = 2$, $\Pr(v_{2} = 0) = \tfrac{1}{2}$ and $\Pr(v_{2} = 1) = \tfrac{1}{4}$. Compute by complement: $$\begin{aligned} \Pr(v_{2}(XYZ) \le 1) &\;=\; \Pr(\text{all odd}) \;+\; \Pr(\text{one has } v_{2} = 1) \\ &\;=\; \left(\tfrac{1}{2}\right)^{3} + 3 \cdot \tfrac{1}{4} \cdot \left(\tfrac{1}{2}\right)^{2} \\ &\;=\; \tfrac{1}{8} + \tfrac{3}{16} \;=\; \tfrac{5}{16}. \end{aligned}$$ Hence $\Pr(4 \mid XYZ) = 1 - \tfrac{5}{16} = \tfrac{11}{16}$.

The $25 \mid XYZ$ factor. For $p = 5$, $\Pr(v_{5} = 0) = \tfrac{4}{5}$ and $\Pr(v_{5} = 1) = \tfrac{4}{25}$. By the same complement: $$\begin{aligned} \Pr(v_{5}(XYZ) \le 1) &\;=\; \left(\tfrac{4}{5}\right)^{3} + 3 \cdot \tfrac{4}{25} \cdot \left(\tfrac{4}{5}\right)^{2} \\ &\;=\; \tfrac{64}{125} + \tfrac{192}{625} \;=\; \tfrac{320 + 192}{625} \;=\; \tfrac{512}{625}. \end{aligned}$$ Hence $\Pr(25 \mid XYZ) = 1 - \tfrac{512}{625} = \tfrac{113}{625}$.

Combining. By independence, $$\Pr(100 \mid XYZ) \;=\; \frac{11}{16} \cdot \frac{113}{625} \;=\; \frac{1243}{10000} \;=\; 0.1243.$$

$$\boxed{\Pr(100 \mid XYZ) \;=\; \tfrac{1243}{10000} \;=\; 12.43\%.}$$

The computation

Encode the natural-density problem directly: draw $X$, $Y$, $Z$ uniformly from a large range, compute $XYZ \bmod 100$, and tally the empirical hit rate.

1. Sample many triples uniformly from a large integer range.

2. Check the product modulo $100$.

3. Compare the hit rate to the exact rational $1243 / 10000$.

import random
from fractions import Fraction

def simulate(trials=2_000_000, lo=1, hi=10**6, seed=0):
    rng = random.Random(seed)
    hits = 0
    for _ in range(trials):
        x = rng.randint(lo, hi)
        y = rng.randint(lo, hi)
        z = rng.randint(lo, hi)
        if (x * y * z) % 100 == 0:
            hits += 1
    return hits / trials

exact = Fraction(11, 16) * Fraction(113, 625)
print(f"exact     = {exact} = {float(exact):.4f}")
print(f"simulated = {simulate():.4f}")

The script prints $\mathrm{exact} = 1243/10000 = 0.1243$ and a simulated value within $\pm 0.001$ at $2{,}000{,}000$ trials, matching the boxed answer.

Riddler Classic

Spread on a table between you are nine index cards numbered $1$ through $9$. You take turns picking up cards and putting them in your hand; there is no discarding. The game ends either when no cards remain (a draw) or when one player has any three cards summing to exactly $15$ (that player wins). You go first. With perfect play, who wins?

The Riddler, FiveThirtyEight, February 8, 2019(original post)

Solution

The game is tic-tac-toe in disguise on a $3 \times 3$ magic square; with perfect play it is a draw.

The bijection. Arrange the digits $1, \ldots, 9$ as the $3 \times 3$ magic square $$M \;=\; \begin{pmatrix} 2 & 7 & 6 \\ 9 & 5 & 1 \\ 4 & 3 & 8 \end{pmatrix}.$$ Every row, column, and diagonal of $M$ sums to $15$. Moreover, every three-element subset of $\{1, \ldots, 9\}$ that sums to $15$ is a row, column, or diagonal of $M$. The eight subsets are $$\begin{aligned} &\{1, 5, 9\}, \quad \{1, 6, 8\}, \quad \{2, 4, 9\}, \quad \{2, 5, 8\}, \\ &\{2, 6, 7\}, \quad \{3, 4, 8\}, \quad \{3, 5, 7\}, \quad \{4, 5, 6\}, \end{aligned}$$ exactly the eight lines of the $3 \times 3$ board (three rows, three columns, two diagonals).

The consequence. Picking a card is, by this bijection, placing an $\mathrm{X}$ or an $\mathrm{O}$ on the corresponding cell of the tic-tac-toe board. Holding three cards that sum to $15$ is the same as occupying a line. The card game is therefore tic-tac-toe played on $M$.

Game value. Tic-tac-toe with perfect play is a draw (standard, known to children; provable by full backward induction on the $\le 5{,}478$ reachable positions). The same value transfers to the card game by the bijection above. Hence:

$$\boxed{\text{With perfect play, the game is a draw.}}$$

The computation

Encode the card game directly (no use of the tic-tac-toe equivalence): play minimax over the full game tree, terminal-test on “some three cards in the current player’s hand sum to $15$”, and propagate the game value back to the root. The root value $0$ confirms the draw.

1. State $=$ (sorted tuple of available cards, sorted tuple of player-$1$’s hand, sorted tuple of player-$2$’s hand, whose turn).

2. Terminal: the current mover may pick any available card $c$; after picking, if any three cards in the mover’s hand sum to $15$, the mover wins. If all cards are gone with no winner, it is a draw.

3. Game value is $+1$ for player-$1$ win, $-1$ for player-$2$ win, $0$ for a draw. Player $1$ maximises, player $2$ minimises.

from functools import lru_cache
from itertools import combinations

def has_15(hand):
    return any(a + b + c == 15
               for a, b, c in combinations(hand, 3))

@lru_cache(maxsize=None)
def value(avail, h1, h2, turn):
    if not avail:
        return 0
    if turn == 0:
        best = -2
        for c in avail:
            na = tuple(x for x in avail if x != c)
            nh = tuple(sorted(h1 + (c,)))
            v = 1 if has_15(nh) else value(na, nh, h2, 1)
            if v > best:
                best = v
            if best == 1:
                break
        return best
    else:
        best = 2
        for c in avail:
            na = tuple(x for x in avail if x != c)
            nh = tuple(sorted(h2 + (c,)))
            v = -1 if has_15(nh) else value(na, h1, nh, 0)
            if v < best:
                best = v
            if best == -1:
                break
        return best

print("game value (perfect play):",
      value(tuple(range(1, 10)), (), (), 0))

The script prints $0$, confirming a draw with perfect play.