Maths Olympiad Prep

Library / /34 of 64

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3×33 \times 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3×33 \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?

A number or a short expression. Spacing and $ signs are ignored.

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 2×22 \times 2 submatrix of all zeroes. Each of these forces the determinant of the matrix to be zero. For i,j=1,2,3i,j=1, 2,3, let AijA_{ij} denote the position in row ii and column jj. Without loss of generality, we may assume that Player 1's first move is at A11A_{11}. Player 0 then plays at A22A_{22}: (10)\begin{pmatrix} 1 & * & * \\ * & 0 & * \\ * & * & * \end{pmatrix} After Player 1's second move, at least one of A23A_{23} and A32A_{32} remains vacant. Without loss of generality, assume A23A_{23} remains vacant; Player 0 then plays there. After Player 1's third move, Player 0 wins by playing at A21A_{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 A11A_{11} and A21A_{21}. Hence for ii equal to one of 1 or 3, and for jj equal to one of 2 or 3, the following are both true: (a) The 2×22 \times 2 submatrix formed by rows 2 and ii and by columns 2 and 3 contains two zeroes and two empty positions. (b) Column jj contains one zero and two empty positions. Player 0 next plays at AijA_{ij}. To prevent a zero column, Player 1 must play in column jj, upon which Player 0 completes the 2×22 \times 2 submatrix in (a) for the win.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.