1
$\begingroup$

I am required to give an example of nim game such that:

  1. the initial position is an N-position,
  2. there are exactly three optimal moves from the initial position,
  3. every pile has at least 20 chips,
  4. every pile has a different (nonempty) number of chips

How could I design such a nim? I am in a mess now. Could anyone help me? If possible, could you teach me how to think in solving this problem? I'm really messed...

$\endgroup$
2
  • $\begingroup$ Do you know how to decide if a position is N? And what a winning move must do? $\endgroup$ Jun 28 '18 at 5:57
  • $\begingroup$ @HagenvonEitzen I know Bouton's Thm. But I don't know how to use it. $\endgroup$
    – user450201
    Jun 28 '18 at 7:12
3
$\begingroup$

We want three different positive integers $a,b,c\ge20$ such that $d:=a\oplus b\oplus c$ is non-zero (the criterion for $N$-positions) and all three piles can be decreased in a way to make this sum zero, i.e., $a\oplus d<a$, $b\oplus d<b$, and $c\oplus d<c$. For the last conditions, it suffices to achieve that the most significant bit of $d$ is set in all of $a,b,c$. So fore example if all of $a,b,c$ are between $16$ and $31$, inclusive, then so will be $d$. In fact, if we try the minimal possible (according solely to $a,b,c\ge20$) choices for $a,b,c$, $$\begin{align}a&=20=10100_2\\b&=21=10101_2\\c&=22=10110_2\end{align}$$ we find $d=10111_2=23$ and $$\begin{align}a\oplus d&=00011_2=3<a\\b\oplus d&=00010_2=2<b\\c\oplus d &=00001_2=1<c\end{align}$$ i.e., the three winning moves are to take $17$ tokens off $a$, or $19$ tokens off $b$, or $21$ tokens off $c$.

$\endgroup$

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.