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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Apr 5, 2016 at 15:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .