For which $n$ the first player has a strategy so that he wins no matter how the other player plays

combinatorial-game-theorycontest-mathrecreational-mathematics

The Question

From Junior O-level Tournament of the Towns paper, Fall 2020:

There are $n$ stones in a heap. Two players play the game by
alternatively taking either $1$ stone from the heap or a prime number
of stones which divides the current number of stones in the heap. The
player who takes the last stone wins. For which $n$ the first player has
a strategy so that he wins no matter how the other player plays?

My Understanding

Let player $A$ play first and player $B$ second. Also, let a heap with $n$ stones be an $n$-heap.

My initial observations:

  1. $A$ wins any $p$-heap for a prime number $p$.

  2. If an $n$-heap is
    winning for $B$, then the $(n + 1)$-heap is winning for $A$, since
    $A$ can remove $1$ stone and then use $B$'s winning strategy for the
    $n$-heap (since for $n$-heap $A$ moves second).

I couldn't think of anything else so I tried finding a pattern with some examples.

\begin{array}{|c|c|c|c|}
\hline
n& \text{winner} \\ \hline
1 &A \\ \hline
2 & A\\ \hline
3 & A\\ \hline
4 & B\\ \hline
5 & A\\ \hline
6 & A\\ \hline
7 & A\\ \hline
8 & B\\ \hline
9 & A\\ \hline
10 & A\\ \hline
11 & A\\ \hline
12 & B\\ \hline
\end{array}

Since it seems $B$ wins exactly when $n = 4k$, I tried to prove this by induction on $k$.

Basis: the claim holds for $k \leq 3$ as shown in the examples.

Inductive hypothesis: Suppose that $B$ wins exactly when $n = 4k$ for arbitrary $k$.

Now I try to prove that $4k + 1$, $4k + 2$, $4k + 3$ have winning strategies for $A$ and that $4k + 4$ has a winning strategy for $B$.

$\textbf{(4k + 1)-heap:}$ $A$ wins by observation 2.

$\textbf{(4k + 2)-heap:}$ $4k + 2 = 2(2k + 1)$ which is even. $A$ can remove 2 stones to get a $4k$-heap which is winning for $A$ since now $B$ moves first.

Now I am stuck for the $(4k + 3)$-heap and $(4k + 4)$-heap. I don't want a complete solution, instead I just want a hint and some confirmation that this is a way to solve this problem. Also if you have an easier way, I would like a hint to discover it!

Best Answer

Yes, you've found a good way of attacking the problem, and you've already got most of the way there.

Hints:

  • The number of stones that can be removed from a pile of size $\ 4k+4\ $ can only be $\ 1,2\ $ or an odd prime.
  • A number of the form $\ 4k+3\ $ must have at least one prime factor $\ p\equiv3\pmod{4}\ $.
Related Question