7
$\begingroup$

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!

$\endgroup$
10
  • $\begingroup$ To clarify, should it be player B who draws the second line? $\endgroup$
    – Andy
    Nov 23, 2011 at 1:57
  • $\begingroup$ Yes, sorry. I edited. $\endgroup$ Nov 23, 2011 at 2:17
  • 2
    $\begingroup$ The proper questions to ask are: Given $N$, which player wins? And how? $\endgroup$
    – TonyK
    Nov 27, 2011 at 11:45
  • $\begingroup$ 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. $\endgroup$ Mar 9, 2012 at 10:00
  • 1
    $\begingroup$ 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). $\endgroup$ Mar 9, 2012 at 16:16

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Mar 9, 2012 at 0:50
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 9, 2012 at 21:14
  • $\begingroup$ @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.) $\endgroup$ Mar 9, 2012 at 21:18
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lee Mosher
    Mar 23, 2012 at 13:38
  • $\begingroup$ Yes, I understand know. I guess I just wanted someone to exhibit such a winning strategy for this game. Ideas? :) $\endgroup$ Oct 11, 2012 at 21:03
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I deleted my previous answer. $\endgroup$
    – Noah Stein
    Nov 27, 2011 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.