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$.
  • $\begingroup$ Ok, what's the solution? $\endgroup$ – n00bcoder123 Aug 13 '14 at 13:08
  • 2
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Aug 13 '14 at 13:18
  • $\begingroup$ 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 $\endgroup$ – n00bcoder123 Aug 13 '14 at 13:33
  • $\begingroup$ For odd $k$ the position is very simple: is $N$ odd or even?. For even $k$, there are a couple of layers of complexity. $\endgroup$ – Henry Aug 13 '14 at 13:42
  • $\begingroup$ Ok, This is too hard,I give up. $\endgroup$ – n00bcoder123 Aug 13 '14 at 16: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.