0
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – rwbogl May 10 '18 at 15:23

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.