5
$\begingroup$

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.

(a) If Player 1 goes first and enters a 1 in the middle square, is there a strategy that can give player 2 a guaranteed win?

Note: I have seen a similar question at https://mathoverflow.net/questions/312034/matrix-tic-tac-toe, however this is based on the first number entered in the top left.

Note: I have seen a similar question and solution at http://math.ucr.edu/~muralee/p4sols.pdf but I'm not quite sure how the proof provided extends to Player 1 starting in the middle.

Perhaps the above could be used as a starting point?

A website I have been using to visualise this is http://textbooks.math.gatech.edu/ila/demos/tictactoe/tictactoe.html (default set to 2 x 2 and Player 0 first but this can be changed).

Thanks!

$\endgroup$
2
  • 2
    $\begingroup$ I'm curious if Player 0 can always win on an $n\times n$ board. $\endgroup$ May 24, 2020 at 5:33
  • $\begingroup$ @DEATH_CUBE_K Yes, if $n\ge 4$. $\endgroup$ Nov 5, 2020 at 18:37

1 Answer 1

4
$\begingroup$

In the first place, it doesn't matter where ONE starts; the nine squares are all equivalent. (Permuting rows and columns can only change the sign of the determinant, not whether its zero or nonzero.) Personally, for neatness, I'd start with a $1$ in a corner, but it's your question so I'll do it your way.

Anyway, the game is a win for player ZERO; he can force not only the determinant but even the permanent of the $3\times3$ matrix to be zero.

Notation. Let me write $a_{i,j}=1$ to mean that player ONE write a $1$ in the $(i,j)$-square of the matix, $a_{i,j}=0$ to mean that player ZERO writes a $0$ in that square.

The game starts with the move $a_{2,2}=1$. I claim that ZERO can win by replying with $a_{1,1}=0$. Now, because of symmetry, there are only four choices for ONE's next move: $a_{2,1}=1,a_{3,1}=1,\ a_{3,2}=1,\ a_{3,3}=1$.

First variation. $a_{2,2}=1,\ a_{1,1}=0,\ a_{2,1}=1,\ a_{1,3}=0,\ a_{1,2}=1,\ a_{3,3}=0$
with a double threat of $a_{2,3}=0$ and $a_{3,1}=0$.

Second variation. $a_{2,2}=1,\ a_{1,1}=0,\ a_{3,1}=1,\ a_{1,3}=0,\ a_{1,2}=1,\ a_{2,3}=0$
threatening $a_{2,1}=0$ and $a_{3,3}=0$.

Third variation. $a_{2,2}=1,\ a_{1,1}=0,\ a_{3,2}=1,\ a_{1,3}=0,\ a_{1,2}=1,\ a_{2,1}=0$
threatening $a_{2,3}=0$ and $a_{3,1}=0$.

Fourth variation. $a_{2,2}=1,\ a_{1,1}=0,\ a_{3,3}=1,\ a_{1,2}=0,\ a_{1,3}=1,\ a_{3,1}=0$
threatening $a_{2,1}=0$ and $a_{3,2}=0$.

$\endgroup$
13
  • 1
    $\begingroup$ would you mind using this website to take screenshots of each step to help me visualise this? textbooks.math.gatech.edu/ila/demos/tictactoe/tictactoe.html (default set to 2 x 2 and Player 0 first but this can be changed). $\endgroup$
    – global05
    May 24, 2020 at 5:39
  • 1
    $\begingroup$ @global05 Anytime there is a row or column of zeroes, or if there are two rows and columns that are equal, the determinant will be zero. $\endgroup$ May 24, 2020 at 5:49
  • 1
    $\begingroup$ @DEATH_CUBE_K could you please prove that statement? $\endgroup$
    – global05
    May 24, 2020 at 6:01
  • 2
    $\begingroup$ I believe I've done enough here. This discussion is not interesting and I have other things to do. You don't have to accept my answer, you don't have to upvote it, you can downvote it. $\endgroup$
    – bof
    May 24, 2020 at 6:14
  • 2
    $\begingroup$ @global05: The main point is that the problem is invariant under permutations of the rows and columns. Thus you can use the visualization in Willie Wong's answer to the MO question you linked to. $\endgroup$
    – joriki
    May 24, 2020 at 6:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .