# binary representation

I've read the article "Two Pile Move Size Dynamic Nim" and I have some problems with proof.

Mainly, we have defined $g(N)$ where for each positive integer $N$, $g(N)$ is the greatest power of $2$ that divides $N$. For example: $g(1) = 1$, $g(24) = 8$ since $8 | 24$ and $16$ does not divide $24$, $g(12)=4$, and so on.

And I have the lemma: For all positive integers $x,N$, if $g(x) < g(N)$ and $x < N$, then $g(x) = g(N−x) = g(N+x)$. If $g(x) < g(N)$ and $x > N$ then $g(x) = g(N +x)$. I think that I have to use the binary representation but I'm not sure how to begin this proof.

• Can you provide a link to this article? Can you describe what the proof is about? What exactly do you not understand about it? – rwbogl May 6 '18 at 19:33

## 1 Answer

I will prove the case where $N > x$ and $g(N) > g(x)$. This should give you some ideas for the other parts.

If $N > x$ and $g(N) > g(x)$, then let $x = 2^m k_1$ and $N = 2^{m + d}k_2$, where $g(x) = 2^m$ and $g(N) = 2^{m + d}$ with $d > 0$. Then $$N - x = 2^m (2^d k_2 - k_1).$$ Since $2^m$ was the largest power of $2$ that divided $N$, the number $k_1$ must be odd. Since $d > 0$, the number $2^d k_2$ is even. Hence $2^d k_2 - k_1$ is odd, and is not divisible by any powers of $2$. Therefore the largest power of $2$ that divides $N - x$ is $2^m = g(x)$. In other words, $g(x) = g(N - x)$. The case $N + x$ is almost identical.

• If you factor out the largest power of 2, then the remaining factor must be odd. Both $c$ and $d$ are odd, so their difference is even. You seem to have that right! – rwbogl May 10 '18 at 15:23