Alice and Bob play the determinant game

Alice and Bob play the following game with an n×n matrix, where n is odd. Alice fills in one of the entries of the matrix with a real number, then Bob, then Alice and so forth until the entire matrix is filled. At the end, the determinant of the matrix is taken. If it is nonzero, Alice wins; if it is zero, Bob wins. Determine who wins playing perfect strategy each time.

When n is even it’s easy to see why Bob wins every time. and for n equal to 3 I have brute-forced it. Bob wins. But for n=5 and above I can’t see who will win on perfect strategy each time. Any clever approaches to solving this problem?

Answer

I tried to approach it from Leibniz formula for determinants

det(A)=σSnsgn(σ)ni=1Ai,σi.

There are n! factorial terms in this sum. Alice will have n2+12 moves whereas Bob has n212 moves. There are n2 variables (matrix entries). Each of them taken alone appear in (n1)! terms in this summation. Whenever Bob picks a zero in his first move for any entry in the matrix, (n1)! factorial terms of this go to zero. For instance, consider a 5×5 matrix. So there are 120 terms. In first move, whenever Bob makes any matrix entry zero, he zeros out 24 of this terms. In his second move, he has to pick that matrix entry which has least number of presence in the first zeroed-out 24 terms. There can be multiple such matrix entries. In face, it can be seen that there is surely another matrix entry appearing in 24 non-zero terms in the above sum. Since n is odd in this case, the last chance will always be that of Alice. Because of that, one doesn’t have to bother about this terms summing to zero. What Bob has to do if he has to win is that

  • He has to make sure he touches at least once (in effect zeroes) each of this 120 terms. In the n=5 case, he has 12 chances. In this 12 chances he has to make sure that he zeros out all this 120 terms. In one sense, It means that he has to average at least 10 terms per chance of his. I looked at the n=3 case, bob has 4 chances there and 6 terms, he can zero out all of them in 3 moves.

  • He has to make sure that Alice doesn’t get hold of all the matrix entries in one single term in 120 terms, because then it will be non-zero, and since the last chance is hers, Bob won’t be able to zero it out, so she will win.

As per above explanation, in the 5×5, he has to just average killing 10 terms in each chance which seems quite easy to do. I feel this method is a bit easy to generalize and many really clever people in here can do it.

EDIT—————-

In response to @Ross Milikan, I tried to look at solving 5×5 case, this is the approach. Consider 5×5 matrix with its entries filled in by the english alphabets row-wise, so that the matrix of interest is

[abcdefghijklmnopqrstuvwxy]

Without loss of Generality (WLOG), let Alice pick up a (making any entry zero is advantageous for her). Lets say Bob picks up b (again WLOG, picking up any entry is same). This helps Bob to zero out 24 terms in the total 120. Alice has to pick up one entry in this first row itself otherwise she will be in a disadvantage (since then, Bob gets to pick the 3 terms in total from the first row and gets 72 terms zeroed out). So concerning the first row, Alice picks 3 of them, Bob picks 2 of them (say b and d), and hence he zeros out 48 terms of the total 120. Now note that next move is Bob’s. Let us swap the second column and first column. This doesn’t change the determinant other than its sign. Look at the modified matrix

[00gfhijlkmnoqprstvuwxy]

where 0 is put in entries Bob has modified and has been put in entries modified by Alice. Now in the first column, lets say Bob gets hold of g and q, and alice gets hold of l and v. Again Alice has to do this and any other move will put her in a disadvantage. Bob had made 4 moves already, the next move is his and now the matrix will look like,

[000fhijkmno0prstuwxy]

Now we are left with the lower 4×4 matrix, Bob is left with 8 chances, and the first move is his. Compare this with 4×4 case, it looks intuitively that Bob should win.

Attribution
Source : Link , Question Author : pad , Answer Author : Davide Giraudo

Leave a Comment