Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Putnam Math Question Redux (Game Theory)?
On the 2008 Putnam, there was a question posted about a Matrix game:
--
Consider a 2008 x 2008 matrix, initially empty. Alex and Barbara, the players in the game, take turns placing a real number of their choosing at any empty spot in the grid. Alex goes first, Barbara second.
--
In the original problem, Barbara wins at the end of the game if and only if the determinant of the completed matrix was 0. Alex wins if the determinant is non-zero. Obviously, Barbara has the winning strategy here, because she can just mirror Alex's moves in a different row, forcing two rows in the matrix to be equal, and making the determinant 0.
However, I propose the following twist - what if Alex went second? Could Alex then have a winning strategy? Would aforementioned strategy apply to any n x n matrix?
Incomplete answers welcome.
stephen, your argument is almost valid. The problem is, unlike in the Alex-first case, Barbara no longer has "last licks" on any pair of rows or columns, because of Ben's parity argument.
However, I can't say I agree with Ben either. No one here has really touched the zero strategy I was hoping for - which is how I think Barbara can force her win. If you take a brief look at the cases n = 2 and n = 3, you should be able to see intuitively that Barbara can easily force a zero-valued determinant by placing zeros in key locations in the matrix.
I have yet to figure out a way to formalize this. I think induction is the way to go, but not quite sure...
@Ben: I know Barbara can't force an entire row or column her way, but she doesn't have to. I have tested the n = 4 case, and even the n = 5, and she can't lost. Barbara needs only to adopt the following strategy:
Remember that the Determinant of an n x n matrix can be written as a sum of n! terms, each term written as a product of n distinct cells A(i, j). Let u = the product of which Alex has accumulated the most non-zero numbers towards completing and that Barbara has not yet forced to be 0. Simply have Barbara place a 0 in one of the as-yet empty cells in this product, forcing that term in the summation to be 0.
Try the strategy out yourself. It doesn't matter what Alex does - Barbara will always be able to stop him from getting a non-zero product in the determinant summation in time.
However, I am not having much luck formalizing this proof. If either of you have an idea, please come forward. I'm extending the deadline.
2 réponses
- BenLv 6il y a 1 décennieRéponse favorite
I think he does, actually.
He can pair up the rows as Barbara did before, and always place his number in the same column, corresponding row. He can force a nonzero determinant so long as no row is a linear combination of the others. It seems that he should be able to choose suitably "weird" numbers to guarantee this (algebraic independence and such).
The parity of the dimensions of the matrix are important here. In the original game, if n were odd, Barbara's strategy fails, since Alex can force her to make the first move in some row or column. [I'm not sure then if Alex has a sure win...].
In this game, Barbara would certainly have a winning strategy if n were odd, following a strategy like stephen suggests. She places a 1 in the corner. Alex plays wherever he likes:
if he played in the first row, she responds with a 1 in some empty column, first row;
if not, she picks some empty row to place a 1 in the first position.
From here Barbara can mirror Alex's moves in those two rows as before. Since the total number of still-empty places is now even, Alex is forced to make the first move in those two rows (which also have an even number of entries to be made).
[Then again, earlier today I managed to forget to square a 3, so perhaps my brain is on break :) ]
EDIT: (+1 hour)
Is the following accurate?: In the Barbara-first problem, Alex can always play in the same row as Barbara (since n is even). In particular, he can always finish a row. So he can guarantee that the newly finished row cannot be written as a linear combination of the others.
(+7 hours)
Ah, I knew that was too easy...I'll think on it some more, but I feel like for large enough n, Alex should be able to prevent the zero determinant...[that feeling is dwindling]
(+16 hours)
My Putnam group discussed this one for a bit last month, and a basic zero-row method was discussed. It didn't work for Barbara because Alex could block any row or column from becoming all zeros without much trouble. I think the same thing might happen here, and I'm not certain B can get away with just strategic zeros. If that's correct, then the 2x2 case is just too small to talk strategy, and the 3x3 falls into the odd case I discussed above. Can you work out a zero strategy for n=4 I wonder? I'll give it a shot...
(+1 day)
I knew you didn't have a zero row/column in mind; I had considered the permutation definition of determinant before but discarded it as I didn't think of a way to put it to use. Placing a zero in a maximally non-zero position is a good idea, and I'll try to think on it. I'm still not entirely convinced.
(+1 week)
Bah, less than a day left. I really don't know where to go with this one. If I think of anything after the question expires I'll be sure to email you.
- Anonymeil y a 1 décennie
I don't see how Alex can win here. Barbara places a "1" in the first row, first column. Now if Alex places his number anywhere but the first row, Barbara simply does as before, and mimics his numbers in a different row. If Alex places in the first row, Barbara mimics his placement in a different column.
Steve
@Ben - Yes, I completely ignored the parity; I'll continue to think about it. As for your edit, no, this is not always true. For example, the 2x2 case: Barbara can always force a row or column to be all zeroes, hence determinant is zero.
