Proof of XOR properties

525 Views Asked by At

I want to prove the following two properties of the Nim-sum/XOR operator $\oplus$ to better understand Nim games.

  1. For the position $n = a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k = 0$, changing any of the $a_i$ will result in $n \neq 0$.

  2. For the position $n = a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k \neq 0$, there exists at least one move such that modifying one of the $a_i$ values results in $n = 0$.

I hope I've stated those correctly. They're meant to prove that the XOR operator can be used to analyze Nim games in the sense that if you're in a losing position $n=0$, you have no choice but to give the opponent a winning position $n \neq 0$, and if you're in a winning position $n \neq 0$, you can force the opponent into a losing $n=0$ position.

My attempts:

  1. If we choose some $a_i$ and modify it to some new value $c_i$ such that $a_i \neq c_i$, this is the same as finding some $b_i$ such that $a_i \oplus b_i = c_i$ where $b_i \neq 0$. And this means we change $n$ to $a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k \oplus b_i = 0 \oplus b_i$, or just $b_i$. And since $b_i \neq 0$, we have $n \neq 0$. While this makes sense to me I don't know if it constitutes an adequate proof.

  2. I have no idea how to do this. I guess let $b_i = n$ and use that as the modifier because then $a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k \oplus b_i = n \oplus b_i$ which turns to $n \oplus n = 0$. But sometimes this results in an illegal move.

1

There are 1 best solutions below

0
On

If $a_i$ changes then at least one position in its binary representation must also change. This position corresponds to a column in the nim-sum. If the old column was $(x_1,x_2,\ldots,x_i,\ldots,x_n)$, the new column is $(x_1,x_2,\ldots,x_i+1,\ldots,x_n)$. Therefore, the new sum for that column is $\sum_{i=1}^n x_i + 1 = 0+1=1$.

For the second question, consider the largest heap $i$, and perform the nim-sum on all the heaps. Then, in $a_i$, alter precisely each position whose column sum is a $1$. Then each column sum will become zero.