1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

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

$\endgroup$
3
  • $\begingroup$ Well done. Solving a 5-point tournament of the towns problem is quite a feat! $\endgroup$ Mar 1 at 10:53
  • $\begingroup$ Oh thanks. I am new to this sort of thing but its quite fun. $\endgroup$
    – Tom Finet
    Mar 1 at 11:49
  • 1
    $\begingroup$ I should also commend you for including the source of the problem in your question. It is always a good idea to do this, and it was unfortunate that a subsequent edit (by someone else) removed that information. I have now restored it with a link to the paper in which the problem appears. If you're interested in trying other similar problems, past tournament of the towns papers, currently up to fall 2015, can be found here. Later papers can be found here. $\endgroup$ Mar 2 at 4:22

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.