Proof: Board Game Strategy

Question

We have a sequence of squares, extending infinitely up and infinitely to the right, and a coin is in one of the squares. Player A and then Player B take turns moving the coin. The players always have four options: move left one or two spaces, or else move down one or two spaces. A player loses if she/he moves the coin off the board.

---

We want to prove using induction that if Player A begins on square $(n,n)$, then Player A does not have a winning strategy.

---

Here is an outline of my proof so far:

Claim: If Player A begins on square $(n,n)$, then he does not have a winning strategy. Proof: We want to show that Player A does not have a winning strategy if he begins on square (n,n) for all positive integers (n). We will do this by using strong induction on n.

Base case: Suppose player A begins on square $(1,1)$. Player A has no winning strategy, because where ever he moves, he will be off the board, and he will lose. Suppose player A begins on square $(2,2)$. Then Player A has no winning strategy, because he can either move to the left $1$, or down $1$, without moving off the board. If he moves to the left $1$, or down $1$, then Player B will move to square $(1,1)$, which we have already shown has no winning strategy. Thus, if player A begins on square $(1,1)$ or square $(2,2)$, he has no winning strategy.

Inductive step: Suppose square $(1,1)$, square $(2,2)$ ...square $(n-1,n-1)$, square $(n,n)$ (for some fixed $n$) has no winning strategy. We want to show that square $(n+1,n+1)$ has no winning strategy as well. If player A is on square $(n+1,n+1)$, then no matter where he moves, player B will always be able to move to either square $(n-1,n-1)$ , or square $(n,n)$. This would put player A on square $(n,n)$ or square $(n-1,n-1)$ which have no winning strategy. Thus, square $(n+1,n+1)$ has no winning strategy.

This completes the induction, and we have proved the claim.

---

1) Have I fully proved this?

2) Is this proof over complicated?

3) Is there any other way to prove this more efficiently?

Any help would be appreciated.

Answer 1

The proof is correct. Indeed, we can prove more: Player B has a winning strategy.

Let $D=\{\langle n,n\rangle:n\in\Bbb Z^+\}$; if Player A is on the diagonal $D$, either Player A has no legal move (and has therefore lost), or every legal move that A has takes the coin off $D$. A move of $k$ squares away from $D$ in one of the legal directions followed by a move of $k$ squares in the other legal direction returns the coin to the diagonal, so Player B can always return the coin to the diagonal after Player A’s move. This already shows that Player B always has a legal response to Player A and therefore cannot lose.

However, we can also note that if Player A is now at $\langle n,n\rangle$, and Player B plays the ‘return to the diagonal’ strategy, Player A will be at $\langle n-1,n-1\rangle$ or $\langle n-2,n-2\rangle$ at his next turn. Since $n$ can be decreased only finitely many times before reaching $1$, Player A will eventually have no legal move, and Player B will win. (In other words, the game is finite.)