Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across this problem while looking at Putnam problems a while ago:

"Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008 x 2008 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?"

I figured out the answer to the question they asked, but it made me wonder about a different question, which might not have an easy answer. For the original question, Barbara has a winning strategy. She can force the first two columns of the matrix to be the same, by copying whatever Alan plays in one column into the other column.

My question is: can Barbara still win if she goes first instead of Alan? She can't use the same strategy as before, because now Alan can force her to play in the first two columns by filling up the rest of the grid.

It might seem likely that Alan would have a winning strategy if Barbara went first, since he gets to control the last entry of the matrix. On the other hand, from sketching out a few games on paper, I concluded that Barbara could win whether she went first or second on both a 2x2 or a 3x3 matrix, so maybe that pattern continues to hold for larger matrices. I also sketched out a few games with a 4x4 matrix, but I wasn't able to come to a conclusion for that one.

Edit: Maybe the 2008 x 2008 array is too large of a problem. I would be equally happy knowing the answer to the 4 x 4 problem: is there a winning strategy if Barbara goes first in a 4 x 4 array?

Edit 2: It looks like my question was asked before: Alice and Bob matrix problem.

share|improve this question

1 Answer 1

If $n>1$ is an odd number then Barbara has the following winning strategy in the game on $n\times n$ matrix. At her first move she put an arbitrary number in $(1,1)$ entry. Now we pair the rest of the entries into the following pairs: $(1,2)-(1,3), (1,4)-(1,5),\dots (1,n-1)-(1,n), (2,1)-(3,1),(2,2)-(3,2),\dots (2,n)-(3,n),(4,1)-(5,1), (4,2)-(5,2),\dots (4,n)-(5,n),\dots (n-1,1)-(n,1), (n-1,2)-(n,2),\dots (n-1,n)(n,n).$ If Alan plays a number in one entry of the pair then Barbara plays the same number in the other. Using this strategy, Barbara makes the second column equal to the third, the fourth – to the fifth and so forth.

share|improve this answer
1  
Agreed. Barbara's winning strategy when she goes first in an odd matrix is similar to the winning strategy she has available when going second in an even matrix. The other two situations are unclear to me. –  Evan Jul 27 '13 at 5:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.