0
$\begingroup$

Problem: We have two heaps of coins with 100 and 99 coins. Two players take some coins alternately, either at least one, at most 10, from the first one, or at least one, at most 9 from the second. The winner is who takes the last coin. How shall the game be played to win?

I think this is supposed to be solve using NIM strategy and Grundy numbers. Some hints on what general strategy to use on these problems would be nice. Also, an in-depth analysis of the problem would be helpful as a model that would allow me to approach other similar problems.

$\endgroup$
1
$\begingroup$

Hint: Start by computing the Grundy numbers for each heap individually. There are simple related formulas for them. Then you want the Grundy numbers of the two heaps to be equal so they sum to $0$.

$\endgroup$
1
$\begingroup$

First compute the Grundy number, using the mex formula, for the heap of size $n$ and moves 1 to 10. This is a recursive process, which is periodic (in this case) with period 11: $\operatorname{mex}(n)=n \pmod{11}$.

Then for the heap with moves $1$ to $9$ we get a period of $10$ and values $\operatorname{mex}(n)=n \pmod{10}$.

It's simple to write a small program to do this, or make a table by hand.

So $\operatorname{mex}(100)=1$ for the first heap and $\operatorname{mex}(99)=9$ for the second. So the first player wins by making the value of the first heap $9$ (moving to $97$) so that the total value is $0$ (this is a xor-sum of heaps, recall) or by making the second heap value $1$, by moving to $91$...

$\endgroup$
  • $\begingroup$ If the first pile is periodic with period $11$, why is $12$ equivalent to $2$? It should be $1$. If you move to $(98,99)$ I move to $(97,99)$ and claim I will win. $\endgroup$ – Ross Millikan May 14 at 14:39
  • $\begingroup$ @RossMillikan it's periodic from $11$ onwards, so $11 \equiv 22$ and $12 \equiv 23$ etc. $\endgroup$ – Henno Brandsma May 14 at 14:41
  • $\begingroup$ No, it is periodic from the start, so $12 \equiv 1$. Let us play the first pile starting with $12$. I take $1$, not $2$, and win. Similarly for the second pile. The numbers are just the number of stones mod $11$ for the first pile and mod $10$ for the second. $\endgroup$ – Ross Millikan May 14 at 14:43
  • $\begingroup$ @RossMillikan and I said the Grundy value of $12$ is $2$ not that $12$ and $2$ are equivalent. $\endgroup$ – Henno Brandsma May 14 at 14:43
  • $\begingroup$ OK, then lets play $(12,2)$, which you claim is a P position. I move to $(2,2)$ and win. I claim $(12,1)$ is a P position. Your move? $\endgroup$ – Ross Millikan May 14 at 14:44

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.