Putnam A2, revised

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Putnam A2, revised

Postby Buttons » Mon Dec 08, 2008 2:41 pm UTC

Okay, so this year's Putnam had a sort-of interesting A2:

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

Except it's not that interesting, because
Spoiler:
Barbara has an easy winning strategy. If she just mirrors Alan's moves (reflecting over a vertical axis, say) then the first and last columns will be equal (as will the ith and 2009-ith), so the determinant is zero.
So, a more interesting variation: suppose Alan is trying to make the determinant zero, and Barbara is trying to make it nonzero. Now who wins?
Buttons
 
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Putnam A2, revised

Postby mike-l » Mon Dec 08, 2008 3:55 pm UTC

My inclination is that Barbara still wins, since she can guarantee the last play in each column, but the naive strategies I've come up with so far are slightly flawed.

Incidentally, what happens in the two different games in 2009? Alan can easily make the determinant zero by arbitrarily playing in the middle column first and using Barbara's strategy from your game, playing arbitrarily in the middle column again if Barbara plays there. Since there are an odd number of rows in the middle column, this essentially makes him 2nd player in the 2008 game. The game where Barbara is shooting for determinant zero seems more interesting than the 2008 case though.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l
 
Posts: 2715
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Putnam A2, revised

Postby Token » Mon Dec 08, 2008 4:47 pm UTC

mike-l wrote:My inclination is that Barbara still wins, since she can guarantee the last play in each column, but the naive strategies I've come up with so far are slightly flawed.

Barbara can guarantee the last play in each column in the 2x2 game, yet Alan still wins.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Token
 
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Putnam A2, revised

Postby heyitsguay » Tue Dec 09, 2008 12:57 am UTC

In a 2009x2009 game, Alan has a winning strategy. He can ensure that no two columns/rows end up being identical, because after the first 2009 rounds of play in different columns, the game essentially reduces to the 2008x2008 case with Barbara going first. Whatever she places in any column then, Alan can put a different entry in the same row of the corresponding column, and none will end up identical.

In the 2008x2008 case with Alan seeking a determinant of 0, Barbara still has a winning strategy, basically by doing what Alan did after round 2009 in the last example, I think.
User avatar
heyitsguay
 
Posts: 118
Joined: Thu Oct 16, 2008 6:21 am UTC

Re: Putnam A2, revised

Postby jestingrabbit » Tue Dec 09, 2008 1:06 am UTC

Having non zero determinant requires more than not having identical rows. No linear combination of rows can be zero.

I think the idea should be to start by resolving what happens when the matrices are small, and then trying to move that up. Even the three by three seems pretty convoluted.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5542
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Putnam A2, revised

Postby ConMan » Tue Dec 09, 2008 1:42 am UTC

It looks like Alan has a winning strategy for the 3x3 case:

Alan plays the last number and so he can guarantee that the row it appears in is l.i. from the other two rows. Thus, for him to have a winning strategy he has to be able to ensure that the first two rows to be completed are also l.i., i.e. are not multiples of each other.

WLOG, let Alan's first play be in the top-left corner. If Barbara makes her first play in the same row, then Alan can complete the row. This forces Barbara to start a new row, in which Alan can then play to make sure it's l.i. from the first row. If Barbara finishes the second row next play, then they just fill out the third row and as stated above Alan wins. If Barbara tries to start the third row instead, Alan just puts a second entry in that row guaranteeing pairs of rows are l.i., and again by having the last play he takes the win.

If, on the other hand, Barbara follows Alan's opening play by starting a row of her own, then Alan can put his second play in the third row. Barbara's next play must then be the second entry in a given row, to which Alan responds in a similar fashion to above to ensure that two of the rows cannot be l.d. If Barbara doesn't try to make one of the rows a multiple of another at this point, then Alan can play whatever he likes until endgame. But if she does make the play, then Alan plays in the third row, so Barbara has to complete one of her two rows and Alan can respond appropriately.

I'll try to draw some diagrams to help explain, and I suspect the strategy can be extended to any odd-dimensional matrix.

Edit: I've just noticed, in trying to make the diagrams, that Alan needs to keep an eye on the columns at the same time, but only really to prevent the possibility of, say, an all-zero column. I'm pretty sure the strategy otherwise holds.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.
User avatar
ConMan
Shepherd's Pie?
 
Posts: 1404
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Putnam A2, revised

Postby skeptical scientist » Tue Dec 09, 2008 1:51 am UTC

ConMan wrote:Alan plays the last number and so he can guarantee that the row it appears in is l.i. from the other two rows. Thus, for him to have a winning strategy he has to be able to ensure that the first two rows to be completed are also l.i., i.e. are not multiples of each other.

Not true. For example:
\begin{bmatrix}
0 &1 &1\\
0 &0 &1\\
0 &1 &x
\end{bmatrix}

Alan's last move is the x. The first two rows are linearly independent, and Alan plays the last number in the third row, but Alan can't ensure that it is linearly independent from rows one and two.

Edit: you seem to have realized this problem yourself. However, handwaving is not going to cut it.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6150
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Putnam A2, revised

Postby ConMan » Wed Dec 10, 2008 11:48 am UTC

skeptical scientist wrote:
ConMan wrote:Alan plays the last number and so he can guarantee that the row it appears in is l.i. from the other two rows. Thus, for him to have a winning strategy he has to be able to ensure that the first two rows to be completed are also l.i., i.e. are not multiples of each other.

Not true. For example:
\begin{bmatrix}
0 &1 &1\\
0 &0 &1\\
0 &1 &x
\end{bmatrix}

Alan's last move is the x. The first two rows are linearly independent, and Alan plays the last number in the third row, but Alan can't ensure that it is linearly independent from rows one and two.

Edit: you seem to have realized this problem yourself. However, handwaving is not going to cut it.


I still suspect Alan can force the win, but I haven't worked through all the cases yet.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.
User avatar
ConMan
Shepherd's Pie?
 
Posts: 1404
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Putnam A2, revised

Postby Cleverbeans » Wed Dec 10, 2008 6:31 pm UTC

I think Alan has a forced win in the 3X3 case. The overall plan is to create an identical row or column. Their are three column and rows, so A's first move will claim one row and one column. B now moves, and no matter where she plays it will either have a distinct row or column (or both) from A's first play. WLOG assume that a second column is claimed, leaving one column completely blank. A's plan is to now ensure that the second column claimed by B's first move is identical to the unclaimed column by mirroring moves in that column. If B makes a move on the initial column where then A puts an arbitrary entry into the last spot on that column and B is in zugswang being forced to make a move that A can again mirror. This should work in higher order cases for odd by odd matrices by choosing an arbitrary row/column to start as the "move wasting" row then mirror with B's first play column and using the same move wasting strategy.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln
User avatar
Cleverbeans
 
Posts: 1281
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: Putnam A2, revised

Postby Torn Apart By Dingos » Wed Dec 10, 2008 6:35 pm UTC

Alan has a winning strategy for the 3x3 case by only placing zeroes. I'm not going to write it out, but there aren't that many cases to consider. It seems like this doesn't work for the 4x4 case though. One thing I tried was for Alan to place three zeroes in a row so he will only need to worry about a 3x3 minor (in which Barbara has already placed one or two numbers). Unfortunately, I haven't been able to force a win from there.
User avatar
Torn Apart By Dingos
 
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Putnam A2, revised

Postby Token » Wed Dec 10, 2008 10:45 pm UTC

Torn Apart By Dingos wrote:Alan has a winning strategy for the 3x3 case by only placing zeroes.

In the NxN case, for N odd, Alan can easily make the determinant zero by mirroring Barbara, so we're interested in how Alan can make it NON-zero. Placing only zeroes is going to make that task somewhat difficult.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Token
 
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Putnam A2, revised

Postby ConMan » Wed Dec 10, 2008 11:47 pm UTC

Yeah, I've been playing "Alan wants a non-zero determinant". I think his best strategy will tend to avoid placing zeros (because of the risk of a zero row or column), and I think I've managed to prove that in the situation where Barbara starts by playing a zero in the same row or column as his starting move that he can force a win in the 3x3 case.

Edit: Actually, it *looks* like Barbara has a winning first move. I'm going to have to make sure I didn't make any mistakes, though (which is likely). I think that if Barbara plays a zero in a position that shares neither row nor column to Alan's first move then she wins. I need to work out what her winning strategy is, though.

Edit 2: Yep, Barbara wins with that move. Alan has a response that forces it to the second-last move, but he's got no chance unless Barbara slips up. Full strategy to come.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.
User avatar
ConMan
Shepherd's Pie?
 
Posts: 1404
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Putnam A2, revised

Postby ConMan » Thu Dec 18, 2008 6:06 am UTC

Ok, hopefully the necro justifies the double post, because I'm about to post Barbara's winning strategy for the 3x3 case.

First, let's simplify things by naming the matrix and its entries:
M=\begin{bmatrix}
m_{11} & m_{12} & m_{13} \\
m_{21} & m_{22} & m_{23} \\
m_{31} & m_{32} & m_{33}
\end{bmatrix}


WLOG, Alan's first move will be either m11 = 0 or m11 = 1.

Case 1: m11 = 0
Barbara plays m12 = 0. If Alan plays any move other than placing a non-zero in m13, Barbara plays m13 = 0 and wins. So, let Alan play WLOG m13 = 1. Notice that now \det M = m_{21}m_{32} - m_{22}m_{31}, so Barbara's next two moves, no matter what Alan plays, will be m21 = 0 followed by either m22 = 0 or m31 = 0.
Case 2: m11 = 1
In this case, Barbara plays m22 = 0. Let's now break Alan's second move down to a few sub-cases written in their most general terms (I put Alan's non-zero moves as 1, but the strategy holds no matter what he chooses).

Case 2.1: m12 = 0, m21 = 0, m23 = 0, m32 = 0
Clearly, in all these cases, Alan moved has lined two zeroes up, so Barbara just has to put the third zero in the row or column.

Case 2.2: m13 = 0 (equivalent to m31 = 0)
Barbara plays m33 = 0, forcing Alan to play m23 = 1 to avoid an all-zero 3rd column. Barbara then plays m32 = 0, and Alan can't block both the 2nd column and the 3rd row from becoming all-zero at Barbara's next turn.

Case 2.3: m33 = 0
Barbara plays m13 = 0, and it continues as for Case 2.2.

Case 2.4: m12 = 1 (equivalent to m21 = 1)
Barbara plays m23 = 0. To keep the 2nd row from being all zeroes, Alan must play m21 = 1. Barbara responds with m33 = 0, forcing Alan to play m13 = 0. At this point, \det M = m_{32}, so Barbara just sets this to zero to win.

Case 2.5: m13 = 1 (equivalent to m31 = 1
Barbara plays m32 = 0, and Alan must avoid the zero 2nd column by playing m12 = 1. Now \det M = m_{23}m_{31} - m_{21}m_{33}, so like in Case 1 Barbara just zeros the two terms out one at a time.

Case 2.6: m23 = 1 (equivalent to m23 = 1)
Barbara plays m32 = 0, and like Case 2.5 Alan must play m12 = 1. This time, \det M = m_{31} - m_{21}m_{33}, so Barbara plays m31 = 0 and then one of m21 = 0 or m33 = 0.

Case 2.7: m33 = 1
Barbara plays m12 = 0 and Alan must respond with m32 = 1, and this turns into a rearrangement of the second half of Case 2.6.

And that's it. If I've missed a case, or given incorrect reasoning, feel free to correct me.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.
User avatar
ConMan
Shepherd's Pie?
 
Posts: 1404
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Putnam A2, revised

Postby Token » Thu Dec 18, 2008 2:49 pm UTC

There's a slight problem with what you've done - Alan is not restricted to placing ones or zeroes. Wlog the first non-zero move is a one, but after that you can't restrict. I don't think that really affects your argument, just means that your determinant calculations get messier.

There is an argument which ignores the problem and actually simplifies the argument by removing cases.

Proposition
Barbara has a winning strategy which only requires her to place zeroes.

Lemma
Barbara can ensure that either:
(i) three of her four moves are all in the same row/column, or
(ii) her four moves form a 2x2 minor of the matrix.

Proof of Lemma
Since we only care about position of moves, rather than what number is placed, mark Alan's moves as Xs and Barbara's moves as Os.

WLOG, Alan plays X11. Barbara responds with O22. Alan now has four equivalent moves (X12, X13, X23, X33), and it's a simple exercise to check that Barbara can force (i) or (ii) in all four cases (it's like tic-tac-toe would be if one player had an extra winning condition and the other didn't have one at all).

Proof of Proposition
Barbara places only zeroes, and forces either a zero row/column or a zero 2x2 minor. QED.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Token
 
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Putnam A2, revised

Postby jestingrabbit » Thu Dec 18, 2008 3:56 pm UTC

That's a clear cut approach Token, but I'm not seeing an easy generalisation to higher dimensions.

The minors are a lot larger there... although all that you need is a zero row or two rows which are zero everywhere except in one particular column (with the particular column shared by both rows) or three rows which are zero everywhere but two columns or etc.

From that I'm guessing that Barbara has the winning strategy but proving it would be an absolute bastard.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
User avatar
jestingrabbit
 
Posts: 5542
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney


Return to Mathematics

Who is online

Users browsing this forum: No registered users and 8 guests