2 player game about removing powers

game theory

Two players play a game with $n$ counters. Taking turns,
each player must remove a number of counters which is a power of $d$. The
person who removes the last counter wins. For any general value of $d$,
determine for which values of $n$ the first player has a winning strategy,
and for which values of $n$ the second player wins.

Attempt case $d=2$: in this case I sum the binary version of $n$ and if it is even the first player loses, if odd they win.

Best Answer

We will split natural numbers into two sets, winning $W$ and losing $L$, with properties:

  1. $0 \in L$
  2. For any number in $W$, there is a move that gives number in $L$.
  3. For any number in $L$ other then $0$, any move gives number in $W$.

Then it's clear that 1st player wins iff $n \in W$.

We can take $W$ and $L$ such as:

  • $x \in W$ if $x \mod {d + 1}$ is either odd, or equal to $d$
  • $x \in L$ if $x \mod {d + 1}$ is even and not equal to $d$
  1. If $x \in W$ and $x < d$, then $x \mod {d + 1}$ is odd. The only possible move will give $x - 1$, which is either $0$, or even $\mod d + 1$, thus in $L$.
  2. If $x \in W$ and $x = d$, then move "take $d^1$" gives us number $0 \in L$.
  3. If $x \in W$, $x > d$ and $x \mod {d + 1}$ is even, then move "take $d^0$" gives us number that is odd $\mod d + 1$ and not equal to $d$, thus in $L$.
  4. If $x \in W$, $x > d$ and $x = d \pmod {d + 1}$, then move "take $d^1$" gives us number equal to $0 \mod {d + 1}$, thus in $L$.
  5. If $x \in L$ and $x \ne 0 \pmod {d + 1}$, then any move will either decrease or increase $x \mod {d + 1}$ by $1$, thus giving us number that is even $\mod {d + 1}$ and thus in $W$.
  6. If $x \in L$ and $x = 0 \pmod {d + 1}$, then any move will give us number that $\mod d + 1$ is either $1$ or $d$, and thus again in $W$.

Note that if $d$ is odd, then $W$ is just set of all odd numbers, $L$ is set of all even numbers, and strategy doesn't matter: any move that takes even number gives an odd, and vice versa.

Related Question