Putnam 2002, Problem A-4

In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty $3 \times 3$ matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the $3 \times 3$ matrix is completed with five 1's and four 0's. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies, who will win and how?

Solution:
(partly due to David Savitt) Player 0 wins with optimal play. In fact, we prove that Player 1 cannot prevent Player 0 from creating a row of all zeroes, a column of all zeroes, or a \( 2 \times 2 \) submatrix of all zeroes. Each of these forces the determinant of the matrix to be zero.  

For \( i, j = 1, 2, 3 \), let \( A_{ij} \) denote the position in row \( i \) and column \( j \). Without loss of generality, we may assume that Player 1’s first move is at \( A_{11} \). Player 0 then plays at \( A_{22} \):  
\[ \begin{pmatrix} 1 & * & * \\ * & 0 & * \\ * & * & * \end{pmatrix} \]  

After Player 1’s second move, at least one of \( A_{23} \) and \( A_{32} \) remains vacant. Without loss of generality, assume \( A_{23} \) remains vacant; Player 0 then plays there.  

After Player 1’s third move, Player 0 wins by playing at \( A_{21} \) if that position is unoccupied. So assume instead that Player 1 has played there. Thus of Player 1’s three moves so far, two are at \( A_{11} \) and \( A_{21} \). Hence for \( i \) equal to one of 1 or 3, and for \( j \) equal to one of 2 or 3, the following are both true:  

(a) The \( 2 \times 2 \) submatrix formed by rows 2 and \( i \) and by columns 2 and 3 contains two zeroes and two empty positions.  

(b) Column \( j \) contains one zero and two empty positions.  

Player 0 next plays at \( A_{ij} \). To prevent a zero column, Player 1 must play in column \( j \), upon which Player 0 completes the \( 2 \times 2 \) submatrix in (a) for the win.  

Note: one can also solve this problem directly by making a tree of possible play sequences. This tree can be considerably collapsed using symmetries: the symmetry between rows and columns, the invariance of the outcome under reordering of rows or columns, and the fact that the scenario after a sequence of moves does not depend on the order of the moves (sometimes called “transposition invariance”).  

Note (due to Paul Cheng): one can reduce Determinant Tic-Tac-Toe to a variant of ordinary tic-tac-toe. Namely, consider a tic-tac-toe grid labeled as follows:  
\[ \begin{array}{c|c|c} A_{11} & A_{22} & A_{33} \\ \hline A_{23} & A_{31} & A_{12} \\ \hline A_{32} & A_{13} & A_{21} \end{array} \]  

Then each term in the expansion of the determinant occurs in a row or column of the grid. Suppose Player 1 first plays in the top left. Player 0 wins by playing first in the top row, and second in the left column. Then there are only one row and column left for Player 1 to threaten, and Player 1 cannot already threaten both on the third move, so Player 0 has time to block both.