Game of nim in which the number of heaps with odd coins is odd

Question

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?

Answer 1

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.

Answer 2

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.