Problem A2

Alan and Barbara play a game in which in which they take turns filling entries of an initially empty 2008×2008 array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant cell. The game ends when all the cells 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?

Solution

For those who is aware of some simple properties of the determinant, the solution is almost immediate. First note that the specific value of the number 2008 that appears in the formulation of the problem is most certainly irrelevant to the solution. After all, the problem has been posed in the 2009 competition. So why the organizers preferred 2008 to 2009. Why did the have to pose a backward looking problem? If, for some reason, picking 2009 would not work, why could not they use 2010? There is something to that question.

As is often the case in problem solving, looking at a smaller problem is quite helpful. Let's start with very small arrays.

For an 1×1 array, the games ends with Alan's single move. Obviously, he'll enter a nonzero number and, by doing so, win the game. Next, try a 2×2 array, with four positions to fill and each player having to make two moves. A 2×2 determinant is zero if and only if its rows (or columns) are proportional. Let's think of columns. Barbara can choose a coefficient of proportionality even, say 1, prior to starting the game and counter every Alan's move with the number that would make two columns proportional, or even equal, if she selected 1 as the coefficient of proportionality. Barbara's strategy is just to place a number equal to that entered by Alan on the previous move in the same row at the last Alan's entry. This would lead to two equal columns and a zero determinant.

But then this strategy works for any N×N array with N even, 2008 in particular. Whenever Alan puts an entry in one of the first two columns, Barbara counters with an equal number in the same row but the other of the two columns. Their moves elsewhere are irrelevant. At the end of the game, the matrix will have two first columns equal and the determinant zero, assuring Barbara's win.