56
$\begingroup$

Alice and Bob play the following game with an $n \times n$ matrix, where $n$ is odd. Alice fills in one of the entries of the matrix with a real number, then Bob, then Alice and so forth until the entire matrix is filled. At the end, the determinant of the matrix is taken. If it is nonzero, Alice wins; if it is zero, Bob wins. Determine who wins playing perfect strategy each time.

When $n$ is even it's easy to see why Bob wins every time. and for $n$ equal to $3$ I have brute-forced it. Bob wins. But for $n = 5$ and above I can't see who will win on perfect strategy each time. Any clever approaches to solving this problem?

  • 0
    What are the strategies you found optimal for $n=3$?2012-10-18
  • 2
    For reference, the case $n = 2008$ is a Putnam problem (guess the year). I think this generalization was discussed on MO but I can't find it.2012-10-18
  • 0
    i assumed that the game could be played with just 1s and 0s. by playing zeros in the corners Bob keeps forcing Alice to play specific moves, and i checked every possible permutation. each time two rows wound up the same. I saw it in a putnam training course for n = 100, again even. i've never been able to find a generalisation to odd n.2012-10-18
  • 3
    Note that for odd $n$, Alice has the last move. If it happens to be the lower right corner, Bob will - among others - need to win the "subgame" of the $(n-1)\times(n-1)$ top left matrix.2012-10-18
  • 0
    I don't see why you'd want to assume only 1s and 0s. It is certainly to Alice's advantage to allow arbitrary reals. In fact, she may as well make each of her numbers be outside the field generated by all previous moves.2012-10-18
  • 0
    for the n= 3 case i didn't think it mattered what reals would be used, because bob would play so many zeros that one could just divide across by some real. so i used 1s and 0s for convenience. i have spent a number of weeks trying to show alice wins on all other n odd. and working only with 1s and 0s still. working with the assumption that if she can do that, she can do it for all reals.2012-10-18
  • 0
    For the n=3 case, Bob uses only 0, and can create either a row of three zeros, or a column of three zeros, or zeros at the four corners of a rectangle (by forcing Alice to block rows and columns). This last configuration also gives a zero determinant by creating two rows/columns one of which is a simple multiple of the other (there is only one non-zero element). Bob's first move is not in the same row or column as Alice's first move.2012-10-18
  • 0
    The $n=5$ case should be solvable by brute force, at least if you assume Bob is playing zeroes only and trying to get one of the following winning configurations: five zeroes in a single row, or four zeroes in the same columns in a pair of rows, or three zeroes in the same columns in each of three rows, or four zeroes in the same rows in a pair of columns, or five zeroes in a single column.2012-10-18
  • 0
    @Qiaochu: There was an MO discussion [here](http://mathoverflow.net/questions/2193/variation-on-a-matrix-game), but a brief glance suggests that it probably isn’t very helpful.2012-10-19
  • 1
    @mjqxxxx: I followed your suggestion. [Here's the code](https://gist.github.com/3956836). The result, up to coding errors, is that Bob can't force one of those zero patterns in the $5\times5$ game. However, he also can't force a corresponding zero pattern in the $4\times4$ game, which he can win, so this leaves open who wins the $5\times5$.2012-10-26
  • 0
    @joriki: Well, it shows that Bob can't win the 5x5 just by playing zeroes, so it eliminates a class of strategies. And the row-mirroring strategy is already eliminated just by parity. I don't know what else he can try... though that's not a proof :).2012-10-26
  • 0
    Recently posted related question: [Winning strategy in $(2n+1) \times (2n+1)$ matrix game.](https://math.stackexchange.com/questions/2239982/winning-strategy-in-2n1-times-2n1-matrix-game)2017-04-20

3 Answers 3