Drawing lines and removing squares - an Alice and Bob game

2011-11-23T00:57:29Z

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!

Answer by Per Alexandersson for Drawing lines and removing squares - an Alice and Bob game

2011-12-11T11:29:05Z

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.

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

Drawing lines and removing squares - an Alice and Bob game

Answer by Per Alexandersson for Drawing lines and removing squares - an Alice and Bob game