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?
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.
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.
