19
$\begingroup$

The original problem appeared on last year's Putnam exam:

"Alan and Barbara play a game 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 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?"

It's not hard to see that Barbara can win this game by reflecting Alan's moves over a vertical line. (In fact, you might say she "wins with multiplicity 1004".) My question is, what if the goals were reversed? That is, suppose Alan (the first player) wants the determinant to be zero, and Barbara wants it to be nonzero. Now who has the winning strategy?

If you expect the result to rely solely on parity, then you should note that Alan wins in the 2×2 case, because he can force a row or column to have only zeroes. Unfortunately, it's not at all clear (to me, anyway) that he can do anything similar to a 4×4 matrix, let alone a 2008×2008 one.

Improve this question
$\endgroup$
5
  • $\begingroup$ I can't edit your post -- it's your turn. As for the text, I would emphasize the text that is the question you're asking, not the one you're quoting. But that's me. $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 23, 2009 at 21:32
  • $\begingroup$ The problem is discussed here: echochamber.me/viewtopic.php?f=17&t=31566&start=0 . I'm not sure if it's solved, though. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 23, 2009 at 21:34
  • $\begingroup$ Thanks, ilya. Qiaochu, yeah, I thought I'd give it a second shot among this crowd, since the xkcd discussion didn't really get anywhere. Also, hi! $\endgroup$
    – Jonah Ostroff
    Commented Oct 23, 2009 at 21:45
  • $\begingroup$ Yeah, people over there have only taken fairly ad-hoc approaches. I don't know much about computers, but would it be hard to set up a program to analyze this game? $\endgroup$
    – Aaron Mazel-Gee
    Commented Oct 28, 2009 at 7:59
  • $\begingroup$ Serious question: should we move this to a blog somewhere while we work this out? It looks like this is doable but needs a good amount more discussion. $\endgroup$
    – Jason Dyer
    Commented Oct 30, 2009 at 12:58

4 Answers 4

Reset to default
7
$\begingroup$

I also can't do the entire problem, but I can handle a more general case than the other answer: Barbara wins if Alan plays only 0s on a board of the form (4n)x(4n). (This is more general because it considers all possible ways of having 0s force a determinant to be zero, not just rows and columns. Admittedly, it's less general because it requires more of the size of the matrix.)

First, consider the 4x4 case. Label the matrix as follows:

aacd
bbcd
efgg
efhh

This pairs up the entries of the matrix. Then, Barbara's strategy is fairly easy: play in the matching pair of wherever Alan plays. One can check that no matter how Alan plays, there will be four entries of Barbara's whose product contributes to the overall determinant. If Barbara plays algebraically independent entries, then this implies the entire determinant is nonzero.

Extending this to (4n)x(4n) is fairly easy. Make n 4x4 blocks along the diagonal of the big matrix. If Alan plays in one of them, Barbara plays by the above strategy locally. If he plays in an off-diagonal block, Barbara simply helps Alan by playing 0 in that block. The end result will be a block diagonal matrix with nonzero determinant.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ Interesting how this thread is almost turning into a Polymath project. $\endgroup$
    – Jason Dyer
    Commented Oct 29, 2009 at 14:50
  • $\begingroup$ @Jason Dyer: Yup! I was secretly hoping someone would finish off the argument for me. Unfortunately, I can prove that no pairing strategy works for Barbara in the 4x4 case. ("A pairing strategy" is one in which Barbara always plays in the matching pair to Alan, for some predetermined perfect matching on the entries. I don't care what entries Barbara actually plays.) $\endgroup$
    – aorq
    Commented Oct 29, 2009 at 15:18
3
$\begingroup$

Let me expand upon my comment. Let us say we are dealing with a 4x4 matrix Alan is restricted to integers, Barbara can use any rational numbers. Alan moves first and wants to force the matrix to have an integral determinant. Alan moves first Barbara moves second and her entry is 1/2 in the same row as Alan the look at the matrix with the row Alan moved first in and the column Barbara moved first in deleted. Suppose Alan moves next in that matrix then Barbara moves in the same row and then the row Alan moved in and the column Barbara moved in is deleted or Alan doesn't move in the matrix still Barbara moves in the derived matrix and again her entry is 1/2 in the same row as Alan. In either case the row Alan moved in and the column Barbara moved in are deleted and we get a new derived matrix in which the process is repeated until there are 4 elements in the matrix with entry 1/2 whose product is in the determinant adding or subtracting 1/16. Barbara makes sure that the rest of her entries are integral as a result the 1/16 cannot be canceled out since the all other contributions to the determinant can be expressed as fractions with denominator 8 or less and the determinant is not integral. This idea can be extended in various ways depending on the restiction on Alan's moves.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

     alt text (source)

  • (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}.

     alt text (source)

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ How about this? For the first n-3 moves: if Alan moves into a new row, Barbara moves into that same row, in a column she hasn't played before. If Alan moves into a repeated row, Barbara plays into a new row, again in a column she hasn't played before. After this, there will be a 3 rows and 3 columns that Barbara hasn't played in yet. She plays basic tic-tac-toe strategy to block Alan there. (Alan can play outside of this 3-by-3 block, but that doesn't help him because Barbara can just pretend he played somewhere within the 3-by-3 block.) $\endgroup$
    – aorq
    Commented Oct 28, 2009 at 20:59
  • 1
    $\begingroup$ An alternative argument (which I learned from Joszef Beck): Imagine the matrix as representing the complete bipartite graph K_n,n. Since n is even, this graph has an Eulerian cycle. By directing that cycle, we create a directed graph where each vertex has in and out degree n/2. Now Barbara always makes sure to pick an edge sharing the same out-vertex as Alan, which immediately guarantees she gets at least n/4 edges at every vertex (i.e. n/4 entries in every row and column of the matrix). $\endgroup$
    – Kevin P. Costello
    Commented Oct 28, 2009 at 21:58
  • $\begingroup$ I think this argument could be extended from Alan could only enter zeros to he could only enter integers, rational numbers or algebraic numbers. Alan would still lose due to a similar argument. $\endgroup$
    – Kristal Cantwell
    Commented Oct 30, 2009 at 1:14
  • $\begingroup$ You mean Barbara enters transcendental numbers and Alan loses? $\endgroup$
    – Jason Dyer
    Commented Oct 30, 2009 at 1:38
  • 1
    $\begingroup$ If Alan is limited to algebraic numbers then Barbara would be able to win using transcendental numbers. The idea is that Alan is under a restriction that Barbara is not and Barbara uses this to her advantage she forces the value of the determinant of the matrix to be transcendental. $\endgroup$
    – Kristal Cantwell
    Commented Oct 30, 2009 at 3:49
1
$\begingroup$

Here's an almost-proof of parity which I believe makes the situation clearer.

Consider the last move. Call it x.

Starting with the equation where the determinant is set to zero,

$a_1 + ... + a_{(n-1)\Gamma(n)}+ xb_1 + ... + xb_{(n-1)!}= 0$

$a_1 + ... + a_{(n-1)\Gamma(n)}= - xb_1 - ... - xb_{(n-1)!}$

$a_1 + ... + a_{(n-1)\Gamma(n)}= -x (b_1 + ... + b_{(n-1)!})$

$-\frac{a_1 + ... + a_{(n-1)\Gamma(n)}}{b_1 + ... + b_{(n-1)!}}= x$

Therefore to win the person with the last move simply needs to play

$-\frac{a_1 + ... + a_{(n-1)\Gamma(n)}}{b_1 + ... + b_{(n-1)!}}$

If n is even, the last move is Barbara's so she wins, if n is odd, it is Alan's so he wins.

The only thing foiling this strategy in general is that ${b_1 + ... + b_{(n-1)!}}$ might be zero.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .