MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Drawing lines and removing squares - an Alice and Bob game

Thought about the following while in a Complex Analysis lecture:

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.

I just did the small cases $N=2$ and $N=3$ manually and got that the answer is yes.

Any imput is welcome!

-
To clarify, should it be player B who draws the second line? – Andy Nov 23 2011 at 1:57
Yes, sorry. I edited. – Cosmin Pohoata Nov 23 2011 at 2:17
The proper questions to ask are: Given $N$, which player wins? And how? – TonyK Nov 27 2011 at 11:45
I don't understand. A new square is removed in each turn, and you can draw a line iff there is at least one square not removed. Thus, the game always ends after exactly $N^2$ turns, and as the players alternate taking turns, A wins iff $N$ is odd. – Zsbán Ambrus Mar 9 2012 at 10:00
No, for example you can't draw a line if the border of 3 sides of the $N \times N$ squared has been removed (any line intersecting the other squares will necessary intersect one of the 3 sides). – Cosmin Pohoata Mar 9 2012 at 16:16

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).

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.

Now, clearly, some game states are terminal, meaning some player have won. Now, using backtracking, we may (theoretically) find which states are winning states.

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.

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.

-
I'm afraid I didn't get this. Can you please elaborate on the phrase "now, using backtracking..."; why are there some states winning states independent of what the other player does? – Cosmin Pohoata Mar 9 2012 at 0:50
@Cosmin Pohoata Winning states are by definition guaranteed to give a win, independent of the other players choices. For example, say you play the following game: There is a stack of N sticks, and Alice and Bob takes turn to remove 1,2 or 3 sticks. The one that removes the last stick wins. Clearly, 0 is a winning position. Now, how could one create 0? Well, from 1,2 and 3, so these are losing positions (you do not want to leave these numbers to your opponent). Then, 4 must be a winning position, since from 4, we can only reach losing positions. Thus, every integer divisible by 4 is winning. – Per Alexandersson Mar 9 2012 at 21:14
@Cosmin Pohoata Winning and losing positions are thus defined recursively, from a winning state, you can only reach losing states, and from every losing state, one can reach at least one winning state. Explicitly finding these states, is done by backtracking. (For this to be well, defined, there should be no way for a player to force the game into a loop, i.e. the states must be a partially ordered.) – Per Alexandersson Mar 9 2012 at 21:18
Paxinum's explanation is the proof of the general theorem about any finite, complete information game for 2 players which always terminates. E.g. tic-tac-toe, go, chess, your squares and lines game. Not bridge or poker, which lack "complete information", because each player hides their cards. The conclusion is that as long as each terminal state of the game is labelled a win for one or the other players, then one of the players has a winning strategy. – Lee Mosher Mar 23 2012 at 13:38
Yes, I understand know. I guess I just wanted someone to exhibit such a winning strategy for this game. Ideas? :) – Cosmin Pohoata Oct 11 at 21:03