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.

enter image description here

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.

  • 1
    $\begingroup$ The heart of the proof is "Whatever $A$ does, $B$ can return to the diagonal, and $(1,1)$ is a losing position." But formally, induction is the right approach, and this proof is fine. $\endgroup$ – Thomas Andrews Nov 18 '15 at 0:39

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


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.