0
$\begingroup$

Suppose in the game of Nim there are 72 chips in the first pile, 60 chips in the second pile, and 100 chips in the third pile and it is your turn to play. How would you play?

Following the below formula for base two, how can I go about solving? enter image description here

$\endgroup$
  • $\begingroup$ First step: write out $72, 60,$ and $100$ in binary. Can you do that? $\endgroup$ – TonyK Apr 6 at 20:51
  • 1
    $\begingroup$ Yes I can do that: $\endgroup$ – MathStudent2 Apr 6 at 20:55
  • 1
    $\begingroup$ OK, then do it here please... $\endgroup$ – TonyK Apr 6 at 20:56
  • 1
    $\begingroup$ 72 = 1001000, 60= 111100, 100= 1100100 $\endgroup$ – MathStudent2 Apr 6 at 21:05
  • $\begingroup$ OK, second step is to compute the Nim sum $1001000_2\oplus 111100_2\oplus 1100100_2$. If you are a programmer, $\oplus$ is just the XOR operation. Can you do that? $\endgroup$ – TonyK Apr 6 at 21:15
2
$\begingroup$

$72\oplus 60 \oplus 100 = 16$ as a decent binary calculator will tell you. Or note that $$\begin{align} 72 &= 64+8= & 2^6 + 2^3 \\ 100 &= 64 + 32 + 4 = & 2^6 + 2^5 + 2^2 \\ 60 &= 32 + 16 + 8 + 4 = & 2^5 + 2^4 + 2^3 + 2^2 \\ \end{align}$$

and note that only $2^4$ is not cancelled by the same power in another sum, while all other $2^i$ are.

As $60\oplus 16 =44$ we just need to reduce the $60$ pile to a $44$ pile (the only pile here that contains the power $2^4$) to give the opponent a value of $44 \oplus 72 \oplus 100 = 0$ making him/her lose.

$\endgroup$
  • $\begingroup$ How do I reduce 60 to a 44 pile based on the power of 2's you broke down? $\endgroup$ – MathStudent2 Apr 9 at 2:26
  • $\begingroup$ @MathStudent2 you need to compensate the $16$ (reduce the sum from $16$ to $0$) to win and $60$ has the only $16$ in its binary expansion. So remove $16$ from the 60 pile, and leave $44$ in that pile. After that move the nim-sum of the numbers (their xor) is $0$ and the one whose turn it is (your opponent) loses. $\endgroup$ – Henno Brandsma Apr 9 at 3:55
  • $\begingroup$ Thank you Henno. Would you be able to review my other problem I posted on Wythoffs game? $\endgroup$ – MathStudent2 Apr 9 at 4:01
0
$\begingroup$

Compute the nim sum of $60, 72$ and $100$ (by writing in binary and adding without carry). Call this $x$. If $x=0$, there is no winning move.

Compute each of the nim sums $y=60+x,z=72+x$, and $w=100+x$. If $y<60$, then reducing $60$ to $y$ is a winning move. Same if $z<72$ or $w<100$.

$\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.