Putnam A2, revised

[Buttons]

Okay, so this year's Putnam had a sort-of interesting A2:

Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008x2008 array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

Except it's not that interesting, because

Spoiler:

Barbara has an easy winning strategy. If she just mirrors Alan's moves (reflecting over a vertical axis, say) then the first and last columns will be equal (as will the ith and 2009-ith), so the determinant is zero.

So, a more interesting variation: suppose Alan is trying to make the determinant zero, and Barbara is trying to make it nonzero. Now who wins?

[mike-l]

My inclination is that Barbara still wins, since she can guarantee the last play in each column, but the naive strategies I've come up with so far are slightly flawed.

Incidentally, what happens in the two different games in 2009? Alan can easily make the determinant zero by arbitrarily playing in the middle column first and using Barbara's strategy from your game, playing arbitrarily in the middle column again if Barbara plays there. Since there are an odd number of rows in the middle column, this essentially makes him 2nd player in the 2008 game. The game where Barbara is shooting for determinant zero seems more interesting than the 2008 case though.

[Token]

My inclination is that Barbara still wins, since she can guarantee the last play in each column, but the naive strategies I've come up with so far are slightly flawed.

Barbara can guarantee the last play in each column in the 2x2 game, yet Alan still wins.

[heyitsguay]

In a 2009x2009 game, Alan has a winning strategy. He can ensure that no two columns/rows end up being identical, because after the first 2009 rounds of play in different columns, the game essentially reduces to the 2008x2008 case with Barbara going first. Whatever she places in any column then, Alan can put a different entry in the same row of the corresponding column, and none will end up identical.

In the 2008x2008 case with Alan seeking a determinant of 0, Barbara still has a winning strategy, basically by doing what Alan did after round 2009 in the last example, I think.

[jestingrabbit]

Having non zero determinant requires more than not having identical rows. No linear combination of rows can be zero.

I think the idea should be to start by resolving what happens when the matrices are small, and then trying to move that up. Even the three by three seems pretty convoluted.

[ConMan]

It looks like Alan has a winning strategy for the 3x3 case:

Alan plays the last number and so he can guarantee that the row it appears in is l.i. from the other two rows. Thus, for him to have a winning strategy he has to be able to ensure that the first two rows to be completed are also l.i., i.e. are not multiples of each other.

WLOG, let Alan's first play be in the top-left corner. If Barbara makes her first play in the same row, then Alan can complete the row. This forces Barbara to start a new row, in which Alan can then play to make sure it's l.i. from the first row. If Barbara finishes the second row next play, then they just fill out the third row and as stated above Alan wins. If Barbara tries to start the third row instead, Alan just puts a second entry in that row guaranteeing pairs of rows are l.i., and again by having the last play he takes the win.

If, on the other hand, Barbara follows Alan's opening play by starting a row of her own, then Alan can put his second play in the third row. Barbara's next play must then be the second entry in a given row, to which Alan responds in a similar fashion to above to ensure that two of the rows cannot be l.d. If Barbara doesn't try to make one of the rows a multiple of another at this point, then Alan can play whatever he likes until endgame. But if she does make the play, then Alan plays in the third row, so Barbara has to complete one of her two rows and Alan can respond appropriately.

I'll try to draw some diagrams to help explain, and I suspect the strategy can be extended to any odd-dimensional matrix.

Edit: I've just noticed, in trying to make the diagrams, that Alan needs to keep an eye on the columns at the same time, but only really to prevent the possibility of, say, an all-zero column. I'm pretty sure the strategy otherwise holds.

[skeptical scientist]

Alan plays the last number and so he can guarantee that the row it appears in is l.i. from the other two rows. Thus, for him to have a winning strategy he has to be able to ensure that the first two rows to be completed are also l.i., i.e. are not multiples of each other.

Not true. For example:

\begin{bmatrix}
0 &1 &1\\
0 &0 &1\\
0 &1 &x
\end{bmatrix}

Alan's last move is the x. The first two rows are linearly independent, and Alan plays the last number in the third row, but Alan can't ensure that it is linearly independent from rows one and two.

Edit: you seem to have realized this problem yourself. However, handwaving is not going to cut it.

[ConMan]

Alan plays the last number and so he can guarantee that the row it appears in is l.i. from the other two rows. Thus, for him to have a winning strategy he has to be able to ensure that the first two rows to be completed are also l.i., i.e. are not multiples of each other.

Not true. For example:

\begin{bmatrix}
0 &1 &1\\
0 &0 &1\\
0 &1 &x
\end{bmatrix}

Alan's last move is the x. The first two rows are linearly independent, and Alan plays the last number in the third row, but Alan can't ensure that it is linearly independent from rows one and two.

Edit: you seem to have realized this problem yourself. However, handwaving is not going to cut it.

I still suspect Alan can force the win, but I haven't worked through all the cases yet.

[Cleverbeans]

I think Alan has a forced win in the 3X3 case. The overall plan is to create an identical row or column. Their are three column and rows, so A's first move will claim one row and one column. B now moves, and no matter where she plays it will either have a distinct row or column (or both) from A's first play. WLOG assume that a second column is claimed, leaving one column completely blank. A's plan is to now ensure that the second column claimed by B's first move is identical to the unclaimed column by mirroring moves in that column. If B makes a move on the initial column where then A puts an arbitrary entry into the last spot on that column and B is in zugswang being forced to make a move that A can again mirror. This should work in higher order cases for odd by odd matrices by choosing an arbitrary row/column to start as the "move wasting" row then mirror with B's first play column and using the same move wasting strategy.

[Torn Apart By Dingos]

Alan has a winning strategy for the 3x3 case by only placing zeroes. I'm not going to write it out, but there aren't that many cases to consider. It seems like this doesn't work for the 4x4 case though. One thing I tried was for Alan to place three zeroes in a row so he will only need to worry about a 3x3 minor (in which Barbara has already placed one or two numbers). Unfortunately, I haven't been able to force a win from there.

[Token]

Alan has a winning strategy for the 3x3 case by only placing zeroes.

In the NxN case, for N odd, Alan can easily make the determinant zero by mirroring Barbara, so we're interested in how Alan can make it NON-zero. Placing only zeroes is going to make that task somewhat difficult.

[ConMan]

Yeah, I've been playing "Alan wants a non-zero determinant". I think his best strategy will tend to avoid placing zeros (because of the risk of a zero row or column), and I think I've managed to prove that in the situation where Barbara starts by playing a zero in the same row or column as his starting move that he can force a win in the 3x3 case.

Edit: Actually, it *looks* like Barbara has a winning first move. I'm going to have to make sure I didn't make any mistakes, though (which is likely). I think that if Barbara plays a zero in a position that shares neither row nor column to Alan's first move then she wins. I need to work out what her winning strategy is, though.

Edit 2: Yep, Barbara wins with that move. Alan has a response that forces it to the second-last move, but he's got no chance unless Barbara slips up. Full strategy to come.

[ConMan]

Ok, hopefully the necro justifies the double post, because I'm about to post Barbara's winning strategy for the 3x3 case.

First, let's simplify things by naming the matrix and its entries:

M=\begin{bmatrix}
m_{11} & m_{12} & m_{13} \\
m_{21} & m_{22} & m_{23} \\
m_{31} & m_{32} & m_{33}
\end{bmatrix}

WLOG, Alan's first move will be either m₁₁ = 0 or m₁₁ = 1.

Case 1: m₁₁ = 0
Barbara plays m₁₂ = 0. If Alan plays any move other than placing a non-zero in m₁₃, Barbara plays m₁₃ = 0 and wins. So, let Alan play WLOG m₁₃ = 1. Notice that now \det M = m_{21}m_{32} - m_{22}m_{31}, so Barbara's next two moves, no matter what Alan plays, will be m₂₁ = 0 followed by either m₂₂ = 0 or m₃₁ = 0.
Case 2: m₁₁ = 1
In this case, Barbara plays m₂₂ = 0. Let's now break Alan's second move down to a few sub-cases written in their most general terms (I put Alan's non-zero moves as 1, but the strategy holds no matter what he chooses).

Case 2.1: m₁₂ = 0, m₂₁ = 0, m₂₃ = 0, m₃₂ = 0
Clearly, in all these cases, Alan moved has lined two zeroes up, so Barbara just has to put the third zero in the row or column.

Case 2.2: m₁₃ = 0 (equivalent to m₃₁ = 0)
Barbara plays m₃₃ = 0, forcing Alan to play m₂₃ = 1 to avoid an all-zero 3rd column. Barbara then plays m₃₂ = 0, and Alan can't block both the 2nd column and the 3rd row from becoming all-zero at Barbara's next turn.

Case 2.3: m₃₃ = 0
Barbara plays m₁₃ = 0, and it continues as for Case 2.2.

Case 2.4: m₁₂ = 1 (equivalent to m₂₁ = 1)
Barbara plays m₂₃ = 0. To keep the 2nd row from being all zeroes, Alan must play m₂₁ = 1. Barbara responds with m₃₃ = 0, forcing Alan to play m₁₃ = 0. At this point, \det M = m_{32}, so Barbara just sets this to zero to win.

Case 2.5: m₁₃ = 1 (equivalent to m₃₁ = 1
Barbara plays m₃₂ = 0, and Alan must avoid the zero 2nd column by playing m₁₂ = 1. Now \det M = m_{23}m_{31} - m_{21}m_{33}, so like in Case 1 Barbara just zeros the two terms out one at a time.

Case 2.6: m₂₃ = 1 (equivalent to m₂₃ = 1)
Barbara plays m₃₂ = 0, and like Case 2.5 Alan must play m₁₂ = 1. This time, \det M = m_{31} - m_{21}m_{33}, so Barbara plays m₃₁ = 0 and then one of m₂₁ = 0 or m₃₃ = 0.

Case 2.7: m₃₃ = 1
Barbara plays m₁₂ = 0 and Alan must respond with m₃₂ = 1, and this turns into a rearrangement of the second half of Case 2.6.

And that's it. If I've missed a case, or given incorrect reasoning, feel free to correct me.

[Token]

There's a slight problem with what you've done - Alan is not restricted to placing ones or zeroes. Wlog the first non-zero move is a one, but after that you can't restrict. I don't think that really affects your argument, just means that your determinant calculations get messier.

There is an argument which ignores the problem and actually simplifies the argument by removing cases.

Proposition
Barbara has a winning strategy which only requires her to place zeroes.

Lemma
Barbara can ensure that either:
(i) three of her four moves are all in the same row/column, or
(ii) her four moves form a 2x2 minor of the matrix.

Proof of Lemma
Since we only care about position of moves, rather than what number is placed, mark Alan's moves as Xs and Barbara's moves as Os.

WLOG, Alan plays X₁₁. Barbara responds with O₂₂. Alan now has four equivalent moves (X₁₂, X₁₃, X₂₃, X₃₃), and it's a simple exercise to check that Barbara can force (i) or (ii) in all four cases (it's like tic-tac-toe would be if one player had an extra winning condition and the other didn't have one at all).

Proof of Proposition
Barbara places only zeroes, and forces either a zero row/column or a zero 2x2 minor. QED.

[jestingrabbit]

That's a clear cut approach Token, but I'm not seeing an easy generalisation to higher dimensions.

The minors are a lot larger there... although all that you need is a zero row or two rows which are zero everywhere except in one particular column (with the particular column shared by both rows) or three rows which are zero everywhere but two columns or etc.

From that I'm guessing that Barbara has the winning strategy but proving it would be an absolute bastard.