6
$\begingroup$

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

This question has been posted before.

I saw a solution recently this way:

When Alan places a number in any spot in the array, Barbara places the same number in the column, but one row up or down. That was she forces the rows to be linearly dependent, and the resulting determinate is zero.

This method works fine and I tried with arbitrary values in matrices of smaller rank.

But I need help in proving that this indeed forms linearly dependent rows which leads the determinant of the matrix to be zero?

$\endgroup$
5
  • $\begingroup$ I'm a little confused what exactly you're trying to prove. It seem as though all you need to prove is that if a square matrix has two identical rows, then its determinant is zero. Is that all you're asking about? $\endgroup$ – Ben Grossmann Apr 14 '17 at 14:11
  • 1
    $\begingroup$ The solution you quote is incomplete: there need to be specific rules of when B places the entry above or below A's entry - see Clayton's answer. Think of this scenario: A(1,1), B(2,1), A(5,1), B(4,1), A(3,1). What is B supposed to do next? $\endgroup$ – Catalin Zara Apr 14 '17 at 14:42
  • $\begingroup$ @Omnomnomnom I interpreted the solution as Barbara filling numbers in any row above or below in the same column,like,if Alan fills $a$ in $5^{th}$ row $6^{th}$ column,Barbara fills $a$ in $7^{th}$ row $6^{th}$ column. $\endgroup$ – user362405 Apr 14 '17 at 14:45
  • $\begingroup$ Is my above assumption correct? $\endgroup$ – user362405 Apr 14 '17 at 14:57
  • 1
    $\begingroup$ A generalization for arbitrary $n$: Alice and Bob matrix problem. $\endgroup$ – Martin Sleziak Apr 20 '17 at 2:10
4
$\begingroup$

Group the rows into pairs as $\{1,2\},\ldots \{2007,2008\}$. In this way, if Alan places a number, Barbara will place the same number into the other paired row. This means that one row is identical to another row (in fact, by construction, every row is a duplicate of another row). Since you end up with two equal rows, the rows are linearly dependent (hence determinant zero).

$\endgroup$
8
  • $\begingroup$ Now I'm curious -- what happens when the matrix has odd dimensions? $\endgroup$ – Mees de Vries Apr 14 '17 at 14:25
  • $\begingroup$ In fact, you can just concentrate on the first and second rows. If Alan plays outside the first two rows, Barbara can play at random. This will still ensure zero determinant. $\endgroup$ – Ross Millikan Apr 14 '17 at 15:07
  • $\begingroup$ @Ross: I had a similar idea, but if Alan plays in everything except the first two rows, Barbara is forced to be the first one to put an entry there. I couldn't fully justify linear dependence between rows is guaranteed. $\endgroup$ – Clayton Apr 14 '17 at 15:22
  • $\begingroup$ The "at random" should not include the first two rows. I should have been clearer. Then she can force him to make the first play as there are an even number of cells not in the first two. $\endgroup$ – Ross Millikan Apr 14 '17 at 15:26
  • $\begingroup$ @Ross: there are an odd number of cells total; ignoring the first two rows still leaves an odd number, meaning that Barbara would have to be the first one to place an entry in the first two rows. $\endgroup$ – Clayton Apr 14 '17 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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