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!
 A: 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.
EDIT: There is a theorem for this, Zermelo's theorem, which guarantees that there is a winning strategy for one of the players.
A: By the way, here's a proof for the much simpler case when "line" means "either row or column".

Claim. There is a winning strategy for $A$ if $N$ is not a multiple of 3 and
  for $B$ if $N$ is a multiple of 3.

We will describe any intermediate state of the game by two parameters $m$ and $n$. The first parameter $m$ is the number of lines in the same direction as the currently chosen line which are not the chosen one and which contain no black square. The second parameter $n$ is the number of lines in the perpendicular direction which contain no black square. Note that after $A$s first move, the state will be $(m,n)=(N-1,N)$ and after $B$s first move, the state will be $(m,n)=(N-2,N-1)$.
On any subsequent move, if the state at the start of the move is $(m,n)$, then the player can leave the board in any of the states $(m-1,n)$, $(m-1,n-1)$, $(n-1,m)$, or $(n-2,m)$ which has non-negative entries. To see this suppose without loss that the currently chosen line is a row of the grid. To achieve $(m-1,n)$, we choose a square in this row and a column which is already blocked (say the one containing the very first blackened square), then we choose any of the $m$ rows. To achieve $(m-1,n-1)$, we blacken a square in one of the $n$ columns not already containing a black square and then choose any of the $m$ available rows. The other two are similar, except that after blackening the square, we choose a column. Note that these cover all the available choices, so they are the only states possible. Note that the only situation where there are no available moves is $(m,n)=(0,0)$. Hence leaving the state at $(0,0)$ is a win.
Now we will call a state ``good'' if either $m$ is even and $2n\le m$ or $\frac{m+1}{2}<n\le 2m$ and $n\equiv 2m\pmod 3$. Note that the winning state $(m,n)=(0,0)$ is good. We will prove that good states are exactly the ones which are wins for the second player. This amounts to proving two facts:
(1) It is impossible to go in one move from a good state to another
good state.
(2) For any bad (that is, not good) state, one can go to a good state
in one move.
The fact that these conditions imply the state is a second player win is clear. If the second player has left the game in a good state, then either he has won already or, by (1), the first player must return it to him in a bad state. Hence the first player cannot have won, and, by (2), the second player can again return it in a good state. If $N\equiv 0\pmod 3$,
then the state $(m,n)=(N-2,N-1)$ is good and hence $B$ has the winning strategy. Otherwise the state $(m,n)=(N-2,N-1)$ is bad and $A$ has the winning strategy. In either case the winning strategy is to always leave the game in a good state. For how to do this see the proof of (2) below.
To prove (1), first suppose we are in a  good state $(m,n)=(2r,s)$ with $s\le r$.  If we move to $(m^{\prime},n^{\prime})=(2r-1,s)$ or $(2r-1,s-1)$, then the first coordinate $m^{\prime}$ is odd and the second coordinate is small $n^{\prime}\le s\le \frac{m^{\prime}+1}{2}$. Hence we are in a bad state. If we move to $(m^{\prime},n^{\prime})=(s-1,2r)$ or $(s-2,2r)$, then the second coordinate is too big $n^{\prime}=2r>2(s-1)\ge 2n^{\prime}$. Thus again we are in a bad state. Next, suppose we are in a good state $(m,n)=(r,2r-3s)$ for $0\le s<r/2$. If we move to $(m^{\prime},n^{\prime})=(r-1,2r-3s)$ or $(r-1,2r-3s-1)$, then the second coordinate is too big $n^{\prime}\ge 2r-3s-1\ge 2r-3\frac{r-1}{2}-1=\frac{r+1}{2} > \frac{m^{\prime}}{2}$ and the congruence modulo 3 is wrong $n^{\prime}-2m^{\prime}\equiv 2{\rm ~or~} 1\pmod 3$. Hence we are in a bad state. If we move to $(m^{\prime},n^{\prime})=(2r-3s-1,r)$ or $(2r-3s-2,r)$, then $2n^{\prime}=2r>m^{\prime}$ and again $n^{\prime}-2m^{\prime}$ is not a multiple of 3, so we are again in a bad state.
To prove (2), note that bad states $(m,n)$ satisfy one of the conditions: $n\ge 2m+1$; $m/2<n<2m$ and $n-2m$ is not a multiple of 3; or, $m$ is odd and $n<m/2$. In the first case, we move to $(m^{\prime},n^{\prime})=(n-1,m)$ or
$(n-2,m)$ whichever gives $m^{\prime}$ even. Then we will have $2n^{\prime}=2m\le n-1$. If we have equality, then $n-1=m^{\prime}$ is even so $2n^{\prime}\le m^{\prime}$ and if not then $2n^{\prime}=2m\le n-2\le m^{\prime}$. In the second case, we move to either $(m^{\prime},n^{\prime})=(m-1,n)$ or $(m-1,n-1)$, whichever gives
$n^{\prime}-2m^{\prime}$ a multiple of 3. For such a point we have
$$\frac{m^{\prime}}{2}=\frac{m-1}{2}\le n-1\le n^{\prime}\le 2m-1=2m^{\prime}+1.$$
The lower bound does not quite agree with the second case in the definition of good points above, but the equality case falls in the first case of good points. The upper bound also does not agree, but equality would give $n^{\prime}-2m^{\prime}=1$, failing the mod 3 condition. Hence we must have the reqired inequality $n^{\prime}\le 2m^{\prime}$. Thus we are at a good point. In the third case, we move to $(m^{\prime},n^{\prime})=(m-1,n)$, then
$m^{\prime}=m-1$ is even and $2n^{\prime}=2n\le m-1=m^{\prime}$ so we are in a
good state.
