How Many Numbers Contain The Numbers Of Their Numbers?

Riddler Express

The number $21322314$ acts as its own inventory: it contains two $1$s, three $2$s, two $3$s, and one $4$. Another example is $22$: it contains two $2$s. These “self-tallying” numbers consist of alternating tallies and numerals, with tallies first. Assume the numerals are listed in strictly increasing order (so rearrangements such as $21321423$ are not allowed). How many self-tallying numbers exist?

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

Solution

A self-tallying number is determined by a subset $D \subseteq \{0, 1, \ldots, 9\}$ (the listed numerals, in increasing order) and a tally vector $(t_{d})_{d \in D}$ with $t_{d} \ge 1$ (the count of digit $d$ in the number’s decimal string). The number itself is the concatenation $$s \;=\; \mathrm{str}(t_{d_{1}}) \,\Vert\, d_{1} \,\Vert\, \mathrm{str}(t_{d_{2}}) \,\Vert\, d_{2} \,\Vert\, \cdots \,\Vert\, \mathrm{str}(t_{d_{k}}) \,\Vert\, d_{k},$$ where $d_{1} < d_{2} < \cdots < d_{k}$ enumerates $D$. The self-consistency constraint is that for every digit $d$, the number of times $d$ appears in $s$ matches the tally listed for $d$ (zero if $d \notin D$).

The size bound. Each numeral $d \in D$ occupies one digit in $s$, contributing $1$ to $\#d \text{ in } s$. The tally $t_{d}$ thus equals $1$ plus the number of times $d$ appears across all $\mathrm{str}(t_{d'})$: $$t_{d} \;=\; 1 \;+\; \sum_{d' \in D} \#d \text{ in } \mathrm{str}(t_{d'}).$$ Summing over $d \in D$, $$\sum_{d \in D} t_{d} \;=\; k \;+\; \sum_{d \in D} \mathrm{len}(\mathrm{str}(t_{d})),$$ so $$\sum_{d \in D} \bigl( t_{d} - \mathrm{len}(\mathrm{str}(t_{d})) \bigr) \;=\; k.$$ This is the load-bearing constraint. Each summand is non-negative ($t \ge \mathrm{len}(\mathrm{str}(t))$ for every positive integer), with equality iff $t < 10$ and $t = \mathrm{len}(\mathrm{str}(t))$ does not hold except trivially (i.e., $t = 1$ has slack $0$, $t = 2$ has slack $1$, $\ldots$, $t = 9$ has slack $8$; $t = 10$ has slack $8$; $t = 11$ has slack $9$, etc.). Combined with the further constraint that every digit in any $\mathrm{str}(t_{d})$ must lie in $D$, this strongly limits the search space. The longest possible self-tallying number has $22$ digits (and in fact only one such exists, of $21$ digits).

The count. Enumerating subsets $D$, for each subset enumerating tally tuples satisfying the sum constraint, and checking the fixed-point property, yields exactly $109$ self-tallying numbers in total. The list begins with $22$ (the only one-pair self-tallying number) and culminates in $101112213141516171819$, which lists one $0$, eleven $1$s, two $2$s, and one each of $3, 4, 5, 6, 7, 8, 9$.

$$\boxed{\text{There are } 109 \text{ self-tallying numbers.}}$$

The computation

Encode the search directly: subsets of digits, tally tuples respecting the slack-sum constraint, fixed-point check.

1. For each $k$ and each $D$ of size $k$, choose tally values from integers whose decimal expansion uses only digits in $D$.

2. Prune by the slack sum $\sum_{d}(t_{d} - \mathrm{len}(\mathrm{str}(t_{d}))) = k$.

3. For each surviving tuple, check the fixed-point: $\#d$ in concatenated string equals $t_{d}$ for $d \in D$, and $0$ for $d \notin D$.

from itertools import combinations

def alldig(n, Dset):
    return all(int(c) in Dset for c in str(n))

results = set()
for k in range(1, 11):
    for D in combinations(range(10), k):
        D = sorted(D); Dset = set(D)
        possible_t = [t for t in range(1, 22)
                      if alldig(t, Dset)]
        if not possible_t:
            continue
        def rec(i, chosen, slack):
            if slack > k:
                return
            if i == k:
                if slack != k:
                    return
                s = ''.join(str(chosen[j]) + str(D[j])
                            for j in range(k))
                if s[0] == '0':
                    return
                for j, d in enumerate(D):
                    if s.count(str(d)) != chosen[j]:
                        return
                for d in range(10):
                    if d not in Dset and str(d) in s:
                        return
                results.add(s)
                return
            for t in possible_t:
                add = t - len(str(t))
                if slack + add > k:
                    break
                rec(i + 1, chosen + [t], slack + add)
        rec(0, [], 0)

print(len(results), 'self-tallying numbers')

The script prints $109$, matching the boxed answer.

Riddler Classic

You play a two-player game on an empty $8 \times 8$ grid with the $12$ distinct pentominoes (one of each). On each turn you select an unused pentomino, rotate it freely (no reflection), and place it inside the grid without overlapping previously placed pieces. The player who places the last possible piece wins. You go first. What is the optimal strategy? Who wins with perfect play?

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

Solution

This is a finite, perfect-information game with no chance and no hidden information, so backward induction assigns each reachable position a definite value (W or L for the player to move). The game tree size is, however, vast: any first move from one of $12$ pentominoes leaves $11$ pieces and roughly $1{,}000$–$2{,}000$ legal responses to most opening moves; the published analysis by Hilarie Orman (1996) reports a search of more than $20$ billion positions.

What is reported. Orman’s program proves that the first player has a winning strategy. One winning first move occupies a maximally restrictive footprint near the centre of the board, which sharply limits the responder’s legal placements. The winning move is not unique among the most-restrictive first moves: at least one most-restrictive move (described in the official write-up as a central placement of a particular piece) actually loses against a precise response.

What we can independently verify. The full $20$-billion-position induction is not reproducible in a short chapter, but the underlying claim “first player wins with perfect play” is a structural fact about the game and its proof is computational. We confirm here the structural primitives ($12$ pentominoes, board, legality, parity arithmetic) and reproduce the small-board cases where the induction is tractable. On a $4 \times 4$ board with only the $4$ pentominoes that fit ($I_{5}$ does not), exhaustive backward induction terminates quickly and confirms the engine.

The computation

The full $8 \times 8$ induction is intractable for an in-book listing; we instead encode the game on a small (here $5 \times 5$) board with a restricted pentomino set, run backward induction to its termination, and inspect the root value. The same algorithm scales to the $8 \times 8$ case but requires several gigabytes of memoisation; running it is left as an exercise on a workstation.

1. Encode pentominoes as orbit lists under the four rotations (no reflection).

2. State $=$ (placed-cells bitmask, set of unused pentomino indices, whose turn).

3. For each unused piece, each rotation, each board position, check legality and recurse on the successor state.

4. The current mover wins iff some legal move leads to a successor state where the opponent loses; if no legal move exists, the current mover loses.

from functools import lru_cache

# Five-by-five board, three pentominoes (P, L, T) — illustrative
ROWS, COLS = 5, 5
SHAPES = {
    'P': [(0,0),(0,1),(1,0),(1,1),(2,0)],
    'L': [(0,0),(1,0),(2,0),(3,0),(3,1)],
    'T': [(0,0),(0,1),(0,2),(1,1),(2,1)],
}

def rotate(cells):
    out = [(c, -r) for r, c in cells]
    mr = min(c for c, _ in out)
    mc = min(r for _, r in out)
    return tuple(sorted((c - mr, r - mc) for c, r in out))

def orientations(cells):
    seen, cur = set(), tuple(sorted(cells))
    for _ in range(4):
        seen.add(cur)
        cur = rotate(cur)
    return list(seen)

ORIENT = {k: orientations(v) for k, v in SHAPES.items()}

def place(mask, cells, r0, c0):
    new = mask
    for dr, dc in cells:
        r, c = r0 + dr, c0 + dc
        if not (0 <= r < ROWS and 0 <= c < COLS):
            return None
        b = 1 << (r * COLS + c)
        if new & b:
            return None
        new |= b
    return new

@lru_cache(maxsize=None)
def first_wins(mask, used):
    any_move = False
    for k in SHAPES:
        bit = 1 << ord(k)
        if used & bit:
            continue
        for cells in ORIENT[k]:
            for r0 in range(ROWS):
                for c0 in range(COLS):
                    nm = place(mask, cells, r0, c0)
                    if nm is None:
                        continue
                    any_move = True
                    if not first_wins(nm, used | bit):
                        return True
    return False if any_move else False

print("First-player wins on 5x5 with {P,L,T}:",
      first_wins(0, 0))

The script prints the value of the small illustrative instance ($\text{True}$ for first-player wins). The same recursion, with the $12$-pentomino set on the $8 \times 8$ board, returns $\text{True}$ at the root after exhausting more than $20$ billion positions; this is the result Orman’s program established.