Nim Subtraction Game Variant

Question

I recently read about the Nim Subtraction Game. I have a variant: Suppose you have $N$ stones and two players Alice and Bob, who can choose to pick either 1 stones or $K$ stones. If Alice plays first, when will she lose? I think the answer is when ($N$ mod $K)=1$, Alice would lose. Am I correct?

Edit: I am wrong. Could anyone provide an optimal solution?

Answer 1

Assuming that this is a standard game (the player who has no legal move loses) then Alice certainly wins when $N=1$, so your expression is not correct in that particular case, though it is correct when $N=k+1$.

Alice also loses when $N=2$, if $k\gt 2$, and so on. So there are parity issues.

As far as I can tell from the patterns:

• If $k$ is odd then Alice wins when $N$ is odd and loses when $N$ is even.

• If k is even it seems to get more complicated. Write $N$ as $a(2k(k+1))+bk+c$ with $0 \le c \lt k$ and $0 \le b \lt 2(k+1)$. Then:

  • Alice wins if $b-c$ is even and $2\le b-c \le k+2$ or if $b-c$ is odd and either $b-c \lt 2$ or $k+2 \lt b-c$.
  • Alice loses if $b-c$ is odd and $2\le b-c \le k+2$ or if $b-c$ is even and either $b-c \lt 2$ or $k+2 \lt b-c$.