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

Question

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!

Answer 1

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

Answer 2

I have used lonza leggiera's hints to complete my solution.

$4k + 3$ must have a prime factor $p \not = 2$ since $4k + 3$ is odd. Then either

• $p \equiv 0 \pmod{4}$, then $p = 4x$ which is not prime,
• $p \equiv 1 \pmod{4}$, then $p = 4x + 1$,
• $p \equiv 2 \pmod{4}$, then $p = 4x + 2$ which implies $p = 2$, but have already established $p \not = 2$,
• $p \equiv 3 \pmod{4}$, then $p = 4x + 3$.

If all prime factors satisfy $p \equiv 1 \pmod{4}$, then $4k + 3$ would satify $4k + 3 \equiv 1 \pmod{4}$ which is false. Hence at least one $p$ must satisfy $p \equiv 3 \pmod{4}$.

$A$ can then remove $4x + 3$ stones from the heap which means the heap has $4k + 3 - (4x + 3) = 4(k - x)$ stones. By the inductive hypothesis a $4(k - x)$-heap is winning for $B$. Hence the $(4k + 3)$-heap is winning for $A$.

Now for the $(4k + 4)$-heap. Again let $p$ be a prime factor of $4(k + 1)$, then either

• $p \equiv 0 \pmod{4}$, then $p = 4x$ which is not prime,
• $p \equiv 1 \pmod{4}$, then $p = 4x + 1$,
• $p \equiv 2 \pmod{4}$, then $p = 2$, or
• $p \equiv 3 \pmod{4}$, then $p = 4x + 3$.

If $p = 2$ then $A$ can reduce the heap to a $(4k + 2)$-heap which we have established is always winning for $A$. No good.

If $p = 4x + 1$, then $4k + 4 - (4x + 1) = 4(k - x) + 3$ which we have established is always winning for $A$. No good.

If $p = 4x + 3$, then $4k + 4 - (4x + 3) = 4(k - x) + 1$ which we have established is always winning for $A$, hence $(4k + 4)$-heap is always winning for $B$.