0
$\begingroup$

Consider a Nim game in which the number of heaps with an odd number of coins is odd. Which player can guarantee a win and why?

My idea is if the number of piles with an odd number of coins is odd then the total number of coins is odd and the nim-sum is non-zero, so the first player can start off the game by making the nim-sum zero and following the balancing strategy to win from there. Am I correct? How would I go about generalizing/formalizing this idea?

$\endgroup$
4
  • $\begingroup$ All you've said here is to apply the general strategy for winning nim ("making the nim-sum zero"). Probably the question wants you to state a more specific strategy for this particular case (how do you make the nim-sum zero)? $\endgroup$
    – Ted
    Apr 5, 2016 at 3:21
  • $\begingroup$ Would it not suffice to show that the nim-sum will be nonzero if the number of heaps with an odd number of coins is odd (the total number of coins in the game is odd)? I do already know how the first player can win if that condition holds $\endgroup$
    – Jim Jj
    Apr 5, 2016 at 3:29
  • $\begingroup$ The way the question is phrased "What is the winning strategy?" sounds to me like it's not asking you just to prove that the first player has a winning strategy (i.e. showing that the nim-sum is nonzero), but to specialize the general nim winning-strategy to this particular case and get a simpler strategy for this particular case. I thought there was a simpler strategy, but then I made a mistake, so maybe what you're doing is fine. $\endgroup$
    – Ted
    Apr 5, 2016 at 3:46
  • $\begingroup$ Sorry that was my mistake, the question is actually phrased as "which player can guarantee a win and why?". Original post has been edited $\endgroup$
    – Jim Jj
    Apr 5, 2016 at 5:02

2 Answers 2

1
$\begingroup$

Here’s one fairly straightforward generalization. Let the sizes of the piles be $n_1,\ldots,n_p$, let $k\in\Bbb Z^+$, and for $i=1,\ldots,p$ let $r_i=n_i\bmod 2^k$, the remainder when $n_i$ is divided by $2^k$. Let

$$m=\left|\left\{i\in\{1,\ldots,p\}:r_i\ge 2^{k-1}\right\}\right|\;,$$

the number of piles for which $r_i\ge 2^{k-1}$; if $m$ is odd, so is the nim sum $\bigoplus_{i=1}^pn_i$, and the first player has a winning strategy. (Your question is about the case $k=1$.)

For $i=1,\ldots,p$ let

$$n_i=\sum_{\ell\ge 0}b_\ell^{(i)}2^\ell\;,$$

where each $b_\ell^{(i)}\in\{0,1\}$; this is the binary expansion of $n_i$, padded on the left with infinitely many zeroes. For $\ell\ge 0$ let

$$b_\ell=\bigoplus_{i=1}^pb_\ell^{(i)}\;,$$

the nim sum of the $\ell$-th bits in the binary expansions of the $n_i$. By definition the nim sum of the $n_i$ is the binary number whose $\ell$-th bit is $b_\ell$:

$$\bigoplus_{i=1}^pn_i=\sum_{\ell\ge 0}b_\ell 2^\ell\;.$$

This is $0$ if and only if each $b_\ell=0$.

Let $\ell=k-1$. For $i=1,\ldots,p$ we have $n_i=2^kq_i+r_i$ for some non-negative integer $q_i$, and

$$\begin{align*} n_i&=\sum_{j\ge k}b_j^{(i)}2^j+\sum_{j=0}^\ell b_j^{(i)}2^j\\ &=2^k\sum_{j\ge 0}b_{k+j}^{(i)}2^j+\sum_{j=0}^\ell b_j^{(i)}2^j\;, \end{align*}$$

where evidently

$$0\le\sum_{j=0}^\ell b_j^{(i)}2^j<2^k\;.$$

Thus, by the uniqueness clause of the division algorithm we must have

$$r_i=\sum_{j=0}^\ell b_j^{(i)}2^j\;.$$

Since $\sum_{j=0}^{\ell-1}2^j<2^\ell$, it’s clear that $r_i\ge 2^\ell$ if and only if $b_\ell^{(i)}=1$. Thus,

$$b_\ell=\bigoplus_{i=1}^pb_\ell^{(i)}=1\;,$$

since exactly $m$ of the terms in this nim sum are $1$, and $m$ is odd. In particular, then, $\bigoplus_{i=1}^pn_i\ne 0$, and the first player has a winning strategy.

$\endgroup$
0
$\begingroup$

This is correct. You just need to prove that the nim-sum is non-zero (and it sounds like already how to do it) and that proves that the first player has a win. There's not much more to it.

$\endgroup$
1
  • $\begingroup$ My question was more of how I would go about proving that the nim-sum is non-zero $\endgroup$
    – Jim Jj
    Apr 5, 2016 at 15:36

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.