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.