# Subtraction Game

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 is equal to 1, that's when Alice loses. Am I correct?

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

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$.
• Ok, what's the solution? – n00bcoder123 Aug 13 '14 at 13:08
• Why not pick some $k$, Harsh, and then work out who wins for various small values of $N$, and see if you can find, and then prove, a pattern? – Gerry Myerson Aug 13 '14 at 13:18
• This is the what I am getting for k from 1 to 12: A B A A B A B A A B A B. Can't find a pattern – n00bcoder123 Aug 13 '14 at 13:33
• For odd $k$ the position is very simple: is $N$ odd or even?. For even $k$, there are a couple of layers of complexity. – Henry Aug 13 '14 at 13:42
• Ok, This is too hard,I give up. – n00bcoder123 Aug 13 '14 at 16:22