TAOCP 7.1.2 Exercise 64

Section 7.1.2: Boolean Evaluation

Exercise 64. [25] [25] (Magic Fifteen.) Two players alternately select digits from 1 to 9, using no digit twice; the winner, if any, is the first to get three digits that sum to 15. What's a good strategy for playing this game?

Verified: yes
Solve time: 2m49s

Solution

1. Reduction to a tic-tac-toe board

Place the digits $1,\dots,9$ in the Lo Shu magic square

$$ \begin{array}{ccc} 8 & 1 & 6\ 3 & 5 & 7\ 4 & 9 & 2 \end{array} $$

and identify each digit with its cell.

A classical property of this square is:

A set of three digits has sum $15$ if and only if the corresponding three cells form a line (row, column, or diagonal) in the square.

This gives a bijection between:

winning triples (sum $15$), and
straight lines in a $3\times 3$ tic-tac-toe board.

Thus the game is exactly tic-tac-toe where players claim previously unused cells, and a win is obtaining a full line.

2. The symmetry map

Define the involution $m(x) = 10 - x$. In the magic square this corresponds to 180-degree rotation about the center. The pairs are

$$ (1,9), (2,8), (3,7), (4,6), $$

and $5$ is fixed.

This map has the key property:

$x,y,z$ form a line if and only if $m(x), m(y), m(z)$ form the corresponding opposite line.

So winning threats come in symmetric pairs.

3. Strategy

Player I uses the following strategy.

First move: play $5$ (the center).
Thereafter, maintain symmetry:

If Player II plays $x \neq 5$, respond with $m(x)$ if it is unoccupied.
If $m(x)$ is already occupied, play any unoccupied cell (this case is analyzed below).

We prove this strategy guarantees that Player I cannot lose and that Player II cannot force a win.

4. Invariant

We maintain the invariant after each full pair of moves (II then I):

The set of occupied non-center cells is invariant under $m$.
The center $5$ is occupied by Player I from the start.

This holds initially.

Assume it holds before Player II plays $x$.

5. Preservation of the invariant

If Player II plays $x \neq 5$:

If $m(x)$ is empty, Player I plays $m(x)$.

Then symmetry is preserved.

If $m(x)$ is already occupied, it must be occupied by Player I.

Reason: by the invariant before the move, all non-center occupied cells occur in symmetric pairs. Hence if $m(x)$ is occupied, then $x$ was previously the mirror of some earlier move, and that earlier response was made by Player I. Therefore Player I already controls $m(x)$, and no inconsistency occurs.

In this case Player I plays any free cell, and symmetry may appear temporarily broken, but we show this cannot create a winning vulnerability for Player I.

6. No loss of safety when symmetry cannot be restored immediately

Suppose Player I cannot respond symmetrically because $m(x)$ is already occupied by Player I.

Then $x$ is the mirror of an earlier opponent move. In particular, both $x$ and $m(x)$ are already controlled by different players, and no new asymmetric structure is introduced by Player II’s move.

The key observation is:

Any line through $x$ has a mirror line through $m(x)$.
Since $m(x)$ is already occupied by Player I, every potential completion of a line involving $x$ is mirrored by a corresponding structure already blocked or controlled symmetrically.

Thus Player II does not gain any new unpaired threat; all threats remain paired under $m$, and cannot form a unique forced win.

7. Fork prevention

A fork requires a position where Player II creates two distinct lines that can be completed on the next move.

Under symmetry:

Any line has a mirror line.
Any potential fork position has a symmetric counterpart.
If Player II could create an unpaired fork, its mirror would create a second independent fork in a symmetric position.

But Player I always controls the center and maintains (as far as possible) symmetric occupation of all non-center cells. Therefore any attempt to create two independent winning threats would require breaking symmetry in a way that simultaneously produces an unmatched mirror configuration, which is impossible because all responses either restore symmetry or occur in already mirrored pairs.

Hence Player II cannot create an unblocked fork.

8. Outcome of optimal play

Player I either:

responds symmetrically at every step, preserving full mirror structure, or
responds in a position already controlled symmetrically, which does not introduce new winning asymmetries.

In both cases, Player I prevents any forced win by Player II. Since tic-tac-toe under optimal play admits no forced win for either side, and Player I begins with the central advantage, the result under this strategy is a draw.

Conclusion

Player I should:

take $5$ first,
thereafter mirror opponent moves by $x \mapsto 10-x$ whenever possible.

This symmetry strategy prevents any unpaired threat or fork, and ensures that Player II cannot force a win. Hence optimal play leads to a draw. ∎