Drawing lines and removing squares - an Alice and Bob game - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:55:36Z http://mathoverflow.net/feeds/question/81674 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81674/drawing-lines-and-removing-squares-an-alice-and-bob-game Drawing lines and removing squares - an Alice and Bob game Cosmin Pohoata 2011-11-23T00:57:29Z 2012-04-06T02:22:00Z <p>Thought about the following while in a Complex Analysis lecture:</p> <p>Let there be a $N \times N$ grid of squares and two players $A$ and $B$. First, $A$ needs to draw a line $l$ that needs to intersect the grid; then, $B$ has to select a square cut by $l$ and remove it from the grid; then, $B$ has to draw a line intersecting the grid but which doesn't cut the previously removed square, and so on ($A$ has to remove a square cut by the previous line and draw a new line intersecting the grid but not cutting the previously removed squares etc). The loser is the the one can't draw any more lines. Is there a winning strategies for some player? Find it.</p> <p>I just did the small cases $N=2$ and $N=3$ manually and got that the answer is yes.</p> <p>Any imput is welcome!</p> http://mathoverflow.net/questions/81674/drawing-lines-and-removing-squares-an-alice-and-bob-game/83174#83174 Answer by Per Alexandersson for Drawing lines and removing squares - an Alice and Bob game Per Alexandersson 2011-12-11T11:29:05Z 2011-12-11T11:29:05Z <p>There should be a winning strategy; In each step, the player chooses a square to remove (a finite set of choices), and a line (which is also a finite set, since a line is essentially a certain set of squares).</p> <p>Thus, each play consists of an element from $Squares \times Lines$ which is a finite set. These are the valid moves, and the grid configuration (subsets of $n^2$), is also finite, are the game states. </p> <p>Now, clearly, some game states are terminal, meaning some player have won. Now, using backtracking, we may (theoretically) find which states are winning states.</p> <p>That is, from each winning state, one can only reach a losing state, and from each losing state, we can reach at least one winning state.</p> <p>The winning strategy is essentially a list of all winning states, and since this set is finite and unique, there must be a winning strategy.</p>