Stones game proof by induction

Question

I'm struggling with proof by induction for the following game

Two players called P2 and P2 are playing a game with a starting number of stones. Player always plays first, and the two players move in alternating turns. The game's rules are as follows: In a single move, a player can remove either 2, 3, or 5 stones from the game board. If a player is unable to make a move, that player loses the game.

A player wins where the number of stones $n$ is $n≥1$, and $n mod 7 = 0$ or $n mod 7 = 1$.

For a proof by induction, I pick $n = 0$ as by base case (here P1 will win)

Do I need to have a second base case for $n = 1$, since if I choose that as the inductive step surely I'm just proving that $2 mod 7 = 1$ which is self-evident.

How do I express these base cases?

My attempt at the proof is as follows:

Base case.: $n = 0$ (is a multiple of 7) first player loses

Inductive case: Assume the theorem is true for $n = k$. Prove it is true for $n = k$

1. Show it is true for $n = 1$ $1 mod 7 = 1$ so p1 loses

2. Assume it is true for $n = k$ $n mod 7 == 0$ OR $n mod 7 == 1$ so p1 loses.

Clearly this is not correct!

Answer 1

According to the general theory of such games the set ${\mathbb N}_{\geq0}$ of positions $n$ is the disjoint union $W\cup L$ of two sets, characterized as follows:

• If $n\in W$ then the next player can enforce a win;
• If $n\in L$ the next player cannot avoid a loss.

From these properties we can surmise that $$\eqalign{n\in W&\quad\Rightarrow\quad \{n-2,n-3,n-5\}\ \ {\rm contains\ an\ element\ of}\ L\ ,\cr n\in L&\quad\Rightarrow\quad \{n-2,n-3,n-5\}\subset W\ .\cr}\tag{1}$$ Contrary to what you are writing $0$ and $1$ are losing positions. It follows that $\{2,3,4,5,6\}\subset W$, since from all of these numbers there is a legal move leading to $0$ or $1$. Going stepwise up using $(1)$ one arrives at the conjecture that all numbers $n=7j+k$, $\>0\leq k\leq6$, with $k\in\{0,1\}$ are in $L$, and all numbers $n=7j+k$ with $k\in\{2,3,4,5,6\}$ are in $W$.

To prove this conjecture we do not use induction on $n$, but on $j$. For $j=0$ we have already shown that the claim is true. I leave it to you to perform the step $j\rightsquigarrow j+1$.