A Transversal Achievement Game on a Grid - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T23:02:32Z http://mathoverflow.net/feeds/question/29607 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid A Transversal Achievement Game on a Grid Martin Erickson 2010-06-26T12:52:40Z 2010-06-30T16:35:29Z <p>Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid. The first player (if any) to occupy some transversal (i.e., a set of n cells having no two cells in the same row or column) is the winner. What is the outcome of the game given best possible play by both players?</p> http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid/29631#29631 Answer by David Eppstein for A Transversal Achievement Game on a Grid David Eppstein 2010-06-26T18:31:11Z 2010-06-26T18:31:11Z <p>Every game like this, in which moving is always an advantage and the winning conditions are symmetric, is won or drawn by the first player. See <a href="http://en.wikipedia.org/wiki/Strategy-stealing_argument" rel="nofollow">strategy-stealing argument</a>. In this case, although it is possible to get a draw (one player fills up one column and the other player fills up another column, for instance), it looks difficult enough to do so that I suspect the result is a first player win. Of course, this is not the same as finding an explicit winning strategy.</p> http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid/29670#29670 Answer by Gerhard Paseman for A Transversal Achievement Game on a Grid Gerhard Paseman 2010-06-27T02:52:19Z 2010-06-27T02:52:19Z <p>Unless I am missing something, the game will always end in a loss for both players. In the case n=2, the second player plays on the same diagonal as the first player. For larger n, the penultimate move of player 2 is to block the unique winning move determined by player 1's first (n-1) moves. Player 1's last move would then be to block player 2's winning move, if one exists.</p> <p>This is based on my reading of the rules, which tells me that every configuration of n+1 marks of one player loses, that marks are not overwritten or replaced once made, and that each players places only one mark during their turn.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.06.26</p> http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid/29671#29671 Answer by Douglas S. Stones for A Transversal Achievement Game on a Grid Douglas S. Stones 2010-06-27T03:06:40Z 2010-06-27T04:34:26Z <p>This question can be phrased in terms of (0,1)-matrix <a href="http://en.wikipedia.org/wiki/Permanent" rel="nofollow">permanents</a>. Player 1 places copies of the number 1 and player 2 places copies of the number 0, and empty cells count as 0. Player 1 wants to achieve a non-zero permanent.</p> <p>Permuting the rows and columns, or taking the matrix transpose gives an equivalent game.</p> <p>EDIT: I was actually quite surprised at how easy it is for the o's to make a losing mistake! Consider the position on the left in the diagram below (after 4 o's have been placed and 3 x's have been placed, with x to move). An equivalent position seems like a very natural position to arise. Surprisingly, x can force the win from here! I put in yellow the forced moves by o (otherwise x goes in that square and o loses).</p> <p><img src="http://i71.photobucket.com/albums/i144/goitre19/game2-1.jpg"></p> <p>Consequently, o has made a mistake in allowing the first position above, and can win instead as illustrated in the following sketch, for example.</p> <p><img src="http://i71.photobucket.com/albums/i144/goitre19/game3.jpg"></p> http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid/29747#29747 Answer by Michael Albert for A Transversal Achievement Game on a Grid Michael Albert 2010-06-28T03:50:08Z 2010-06-28T03:50:08Z <p>Unless my code is wrong (always a real possibility) the 4x4 case is a first player win.</p> <p>Vincent Vatter suggested looking at the related game where X wins by building a permutation, and O wins otherwise (i.e. by blocking a permutation). Note that in this game, O does not win simply by forming a permutation, but only by blocking X from doing so.</p> <p>The reason for looking at this game is that it's relatively easy to see that if X wins the modified game, both as first and second player in some size $k$, then she also does so in size $k+1$. The hope would then be to show that the outcomes of the two games are related somehow.</p> http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid/29808#29808 Answer by Vince Vatter for A Transversal Achievement Game on a Grid Vince Vatter 2010-06-28T16:04:08Z 2010-06-28T16:04:08Z <p>As Michael Albert mentioned, an interesting variant is when X wins by building a permutation, while O wins only by preventing X from building a permutation. (The standard term for such a game is maker-breaker.)</p> <p>According to my coding (which should not be regarded as infallible), X wins this game on a $4\times 4$ grid both when X goes first and when O goes first. By a straight-forward inductive argument, this implies that X wins the maker-breaker game on an $n\times n$ grid for all $n\ge 4$.</p> <p>The question remains of whether this has anything to do with the version of the game posed by Martin, where both X and O are trying to build permutations.</p>