In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 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
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 submatrix of all zeroes. Each of these forces the determinant of the matrix to be zero. For , let denote the position in row and column . Without loss of generality, we may assume that Player 1's first move is at . Player 0 then plays at : After Player 1's second move, at least one of and remains vacant. Without loss of generality, assume remains vacant; Player 0 then plays there. After Player 1's third move, Player 0 wins by playing at 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 and . Hence for equal to one of 1 or 3, and for equal to one of 2 or 3, the following are both true: (a) The submatrix formed by rows 2 and and by columns 2 and 3 contains two zeroes and two empty positions. (b) Column contains one zero and two empty positions. Player 0 next plays at . To prevent a zero column, Player 1 must play in column , upon which Player 0 completes the submatrix in (a) for the win.