Determinant Tic Tac Toe Part 2

Question

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

If a method for player 0 to always win exists, will it work for an (n × n) grid, where n > 3? I would like a detailed proof of whether this method (shown in the below link) would work, as described in the bounty on this question.

Note: A solution for a 3 x 3 can be found at Q4 solutions at http://math.ucr.edu/~muralee/p4sols.pdf but I'm not quite sure how the proof provided extends to an n x n grid.

Perhaps the above could be used as a starting point? Edit: The answer to the first part of the question can be found at Two players put fill $1$ and $0$ in a $3\times 3$ matrix and compute its determinant when it is full. Can Player $0$ win if $1$ starts at the center?

Edit: The determinant of a 3 x 3 matrix is calculated by

\begin{bmatrix}a&b & c\\d&e&f\\g&h&i\end{bmatrix}

The determinant is $$ a (ei-hf) - b (di -gf) + c (dh - ge)$$

Answer 1

Here’s an easier way to represent a winning strategy for Player 0 on the 4x4 matrix:

Whenever player 1 plays in a letter, claim the other of the same letter. The determinant of the resulting matrix must be zero; an easy way to demonstrate that is by direct computation.

Or, we can note that the sum of the first two columns is (1,1,1,1) and the second two columns is (1,1,1,1) so the four columns cannot be linearly independent.

This reasoning carries over to any other size of matrix; in fact, we only need to care about how we play in four of the columns! On a 5x5 we can extend the strategy, this is one of several ways:

Columns 2 and 3 add to (1,1,1,1,1) and columns 4 and 5 add to (1,1,1,1,1) so the determinant must be zero. So it doesn’t matter what goes in the first column.

Answer 2

Let $n \geq 5$, and let the first entry picked by player one be in the last row (without loss of generality).

Player $0$ can ensure that: (a) row 1 + row 2 equals the all $1$s vector, as well as (b) row 3 + row 4 equals the all-$1$ vector, thus ensuring a linear relation among the rows, and making the determinant zero.

To ensure that row 1 + row 2 (and row 3 + row 4) is the all $1$s vector, player $0$ avoids these rows until player 1 makes an entry there; if player $1$ enters a one in $(1,i)$, then player $0$ enters a zero in $(2,i)$ (and vice-versa and likewise for rows 3, 4). This means that player $0$ must be able to play in the other rows as long as player 1 plays in the other rows.

This is possible if $n$ is even, as the number of remaining entries, that is $n^2-4n$, is even. Even if $n$ is odd, this strategy works. The key point is that even if player $0$ has to move first on the first two rows, it can be ensured that their sum is all 1s; player 0 makes an arbitrary entry, say in $(1,1)$ and subsequently if player 1 makes an entry anywhere except $(2,1)$, follows the earlier strategy. Whenever player 1 makes an entry in $(2,1)$, it reduces to the game on two equal-sized rows (of shorter length) with player 0 to move, so we're done by induction.

Answer 3

Claim:$\;$If $n\ge 4$, player $0$ has a winning strategy.

The idea is simple, and in essence just a variation of Aravind's beautiful solution for the even case.

Of the first $4$ rows, call rows $1$ and $2$ a complementary pair, and similarly, call rows $3$ and $4$ a complementary pair.

In a complementary pair of rows, call two cells in the same column a complementary pair of cells.

Let $u$ be the $n$-vector with all entries equal to $1$.

As Aravind explained, if the completed matrix is such that each of the two complementary pairs of rows has sum equal to $u$ (i.e., $R_1+R_2=u=R_3+R_4$), then those $4$ rows are linearly dependent, hence the determinant is zero.

A two-phase winning strategy for player $0$ is as follows . . .

Phase $1$ strategy:

Whenever player $1$ places $1$ in a blank cell in one of the first $4$ rows for which the complementary cell is blank, player $0$ responds by placing $0$ in the complementary cell.

If player $1$ plays outside the first $4$ rows, player $0$ does the same, unless all cells outside the first $4$ rows are already filled, in which case, the strategy for player $0$ switches to the phase $2$ strategy.

Note that for even $n$, the number of cells outside the first $4$ rows is even, hence, assuming player $0$ has followed the phase $1$ strategy, there will never be a scenario where player $1$ fills the last blank cell outside the first $4$ rows. It follows that for even $n$, the game will run to completion with no need for player $0$ to switch to the phase $2$ strategy, and at completion, all pairs of complementary cells sum to $1$, so player $0$ wins.

So now assume:

• $n$ is odd.$\\[2pt]$
• It's player $0$'s turn.$\\[2pt]$
• Player $1$ has just filled the last remaining blank cell outside the first $4$ rows.

Player $0$'s strategy now switches to phase $2$ . . .

Phase $2$ strategy:

Given that player $0$ faithfully followed the phase $1$ strategy, it follows that for every pair of complementary cells, either both cells are filled (and sum to 1) or both cells are blank.

If there are no blank cells, then the game is over and player $0$ has won.

Otherwise, player $0$ chooses some pair of complementary blank cells and places $0$ in one of those cells.

From that point on, player $0$'s basic strategy is to place $0$ is some cell to ensure that whenever it's player $1$'s turn to play, there is exactly one pair of complementary cells for which one of the two cells contains $0$ and the other one is blank.

To accomplish the phase $2$ basic strategy, player $0$'s choice of move depends on the nature of player $1$'s previous move. There are two cases . .

If player $1$ places $1$ in a cell for which the complementary cell is blank, player $0$ responds by placing $0$ in that complementary cell.

If player $1$ instead places $1$ in a cell for which the complementary cell contains $0$, and if the game is not over, there must be at least one pair of complementary blank cells, so player $0$ responds by placing $0$ in one of the cells of such a complementary pair.

In either case, after player $0$'s response, there is exactly one pair of complementary cells for which one of the two cells contains $0$ and the other one is blank.

Assuming player $0$ faithfully follows the phase $2$ basic strategy, player $1$'s last move will be in a blank cell (the only remaining blank cell) for which the complementary cell contains $0$, and at that point, all pairs of complementary cells sum to $1$, hence player $0$ has won.

This completes the proof.