2
$\begingroup$

I'm interested in the following game:

Given a pile of $n$ stones and a set $A\subset \Bbb{N}$, two players alternately remove an amount $a\in A$ of their choice of stones. The player who can no longer make a move loses.

Which player has the winning strategy based on $n$ and $A$?


A famous version of this game is where $A = \{1, 2, \dots, m\}$. Here the first player wins if $n$ is not divisible by $m+1$ and loses otherwise because of the following strategy:

  1. If the amount of stones $\tilde{n}$ left in the pile in your turn is not divisible by $m+1$, remove $\tilde{n} \pmod{m+1}$ (which is not $0$) stones, so the amount of stones left in the pile in your opponent's turn is divisible by $m+1$.
  2. If the amount of stones left in the pile in your turn is divisible by $m+1$, any amount of stones your remove will left an amount of stones not divisible by $m+1$ in the pile for your opponent's turn.

Of course, in this case, a player can't make a move iff there are no stones left in the pile, i.e., when the amount of stones left is $0$. As $0$ is divisible by $m+1$, the player who always receives a multiple stone quantity of $m+1$ will be the first to run out of moves.

Based on that, I think it makes sense to look for some invariant related to set $A$ (how was $m+1$ module congruence in this case), but I couldn't find any.

A particular case in which I am interested is the case where $A = \{m^2 : m\in\Bbb{N}\}$.

$\endgroup$

1 Answer 1

3
$\begingroup$

A Mathematical Investigation of Games of “Take-Away” [PDF] by Solomon W. Golomb may be of some use. In Section $4$ he discusses the particular case in which you’re interested and comes to the conclusion that a complete analysis may be ‘as difficult as the study of the distribution of the prime numbers’. The paper is from $1966$, so it’s quite possible that more is now known.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .