2
$\begingroup$

So we have a 3x3 matrix and two players, a player that only puts in ones and a player that only puts in zeros. A coin flip is used to decide which player goes first. The first move is always to fill the upper left entry with the player's number, whoever won the coin flip. Then the players take turns filling in ones and zeros. Once the matrix is full, the winner is decided by the determinant of the matrix. If the determinant of the matrix is non-zero (an invertible matrix), the player who filled in ones wins. If the determinant of the matrix is zero (non-invertible matrix), the player who filled in zeros wins.

The question is: Is one of the players always going to win if both players employ optimal strategies? Who wins if 1-player goes first? Who wins if 0-player goes first? Does it even depend on who goes first?

$\endgroup$
2
  • $\begingroup$ In this case it's probably a slight overkill, but the answer to your first question is yes for general reasons. If every egal run of a game is finite, then exactly one of the players (the one that starts or the second one) has a winning strategy. $\endgroup$
    – user57888
    Commented Oct 4, 2018 at 15:07
  • 1
    $\begingroup$ No harm in the first player starting in the corner but it doesn't really matter. Shuffling rows and/or columns (and taking the transpose) does not change if a matrix is singular or not. $\endgroup$ Commented Oct 5, 2018 at 5:58

1 Answer 1

6
$\begingroup$

0 always wins (regardless of 1's strategy). This is because any configuration with (a) 0s all in one row or (b) 0s all in one column or (c) 0s all in a 2x2 minor will win.

For the case 1 goes first, let 0 play in the center square. After which up to symmetry there are only four cases that need to be considered after 4 moves

11.      1.1     1..    1..
.00      .0.     .01    .00
...      .0.     .0.    ..1

(this being 0's strategy). It is easy to see that either 1 allows 0 to make a line in the 6th move, or 1 allows a block of the form

.0
00.

to form after the 6th move which guarantees win for 0.

When 0 goes first she wins faster.

$\endgroup$
0

You must log in to answer this question.

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