linear algebra - Variation on a matrix game

While I still can't answer in the general case, in the case where n > 2 and Alan moves only with 0 in attempt to fill a row or column with 0s, he cannot win.

This proof is written semi-informally for ease of reading.

--

Call Alan's moves 0s and Barbara's moves Xs.

A "blocked" row or column is a row or column that Barbara has at least one X. A "unblocked" row or column is free of Xs.

For Alan to win on an nxn grid, after his move is complete there needs to be at least one row with n-1 unblocked 0s and at least one row with n-1 unblocked 0s.

Define a set R which contains, for each unblocked row, the number of 0s on that row.

Define a set C which contains, for each unblocked column, the number of 0s on that column.

For our the explanation that follows we will write set R followed by set C. For example, if R={2,1} and C={1,3} the sets will be written as {2,1} {1,3}.

The game begins with both R and C as the empty set.

(1st move) Alan moves and the sets become {1} {1}.

(2nd move) Barbara moves to block a row and the sets become {} {1}.

(3rd move) Alan has three choices, let us consider each:

[Case 1]
Alan moves in the same column as the existing unblocked 0. The sets become {1} {2}

Barbara moves in the same column as the two unblocked 0s. The sets become {1} {}.

[Case 2]
Alan moves in a square that is blocked in both row or column. Barbara blocks the unblocked column and the sets become {} {}.

[Case 3]
Alan moves in a square that contains no 0s or Xs in both the row and column. The sets become {1} {1,1}.

Now the situation is as in the diagram above. Suppose the 0s are in A and D, and B and D are empty. One of the rows must be blocked; suppose it is the same row as A. Then Barbara
moves at C and the sets become {} {1}. If the blocked row is the same row as D, Barbara moves at B and the sets become {} {1}.

The situation if the 0s are at B and C is symmetrical.

Now note that all the cases are either identical to an earlier position of the game or are symmetrical to an earlier position. Therefore Alan can never win the game.