Two players play a game on a 3 x 3 board. The first player places a 1 on an empty square and the second player places a 0 on an empty square. Play continues until all squares are occupied. The second player wins if the resulting determinant is 0 and the first player wins if it has any other value. Who wins?
Solution
Answer: the second player.
Divide and conquer.
The determinant is certainly zero if we have a row or column or zeros or if we have two identical rows. We show that the second player can always achieve one of these outcomes.
The absolute value of a determinant is not affected if the rows or columns are permuted, so there is no loss of generality in assuming that the first player's first move is at the top right. The second player then plays in the middle.
1 A B . 0 C . . DSince permuting rows or columns, or interchanging rows and columns, does not affect the absolute value, we can assume that the first players next move is A, B, C, or D. The remaining moves by the first player are all forced:
case A 1 1 . 1 1 . 1 1 . 1 1 1 1 1 1 1 1 1
. 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
. . . . . . . . 0 . . 0 . 0 0 1 0 0
case B 1 . 1 1 . 1 1 . 1 1 1 1 1 1 1 1 1 1
. 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
. . . . . . . 0 . . 0 . . 0 0 1 0 0
case C 1 . . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 1
. 0 1 . 0 1 . 0 1 . 0 1 0 0 1 0 0 1
. 0 . . 0 . 0 0 . 0 0 1 0 0 1 0 0 1
case D 1 . . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 1
. 0 . . 0 . 0 0 . 0 0 1 0 0 1 0 0 1
. 0 1 . 0 1 . 0 1 . 0 1 0 0 1 0 0 1
© John Scholes
jscholes@kalva.demon.co.uk
11 Dec 2002