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!


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

| cite | improve this answer | |

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.