[Math] Nim addition- binary addition without carrying

binarycombinatorial-game-theorygame theorynumber theory

A nim addition table is essentially created by putting, in any cell, the smallest number not to the left of the cell and not above that cell in its column. However, I know for a fact that nim addition is equivalent to binary addition without carrying. How does the first method of creating a nim addition table translate to the second method? I am certain it has something to do with the fact that the nim table cycles every $\mathbb{Z}/2^n$.

I know that binary addition without carrying is the same as writing out 2 numbers as a sum of powers of 2, scratching out powers appearing in both sums, and adding the remaining. So in essence, I am asking how the first method I mentioned of creating a nim addition table translates to this method. Note that I am not asking about the actual game.

Best Answer

So, to interpret your question, you have two different procedures for filling out a table of numbers which has a definite top and left edge, but continues indefinitely down and to the right. First is

  1. Don't fill in any cell before all the positions directly above and directly to the left of it are filled.

  2. Write in each cell the smallest nonnegative integer that doesn't appear in any cell directly above it or directly to the left of it

The second is

Write in the cell with (zero-based) coordinates $(i,j)$ the number $i\oplus j$, where $\oplus$ is the bitwise XOR operation (that is, as you say, binary addition with no carries).

And you want to prove that these two methods result in the same value in each cell of the table.

We can prove that by long induction on $i$ and $j$. For the induction step we imagine that the cells above and to the left of $(i,j)$ have already been filled with the $\oplus$ of their coordinates, and we want to prove that step (2) of the first procedure results in exactly $i\oplus j$.

One half of this is easy: since $\oplus$ is a group operation, $i\oplus j$ cannot equal $i\oplus b$ or $a\oplus j$ for any $b\ne j$ or $a\ne i$ -- in particular not for any smaller $a$ or $b$.

We then need to prove that $i\oplus j$ is the least number that hasn't yet been used in the same row or column. In other words, every $c < i\oplus j$ must already have been used somewhere.

Consider the most significant bit position where $c$ differs from $i\oplus j$. Because $c$ is less than $i\oplus j$, there must be a 0 in this position of $c$ and a 1 in the position of $i\oplus j$. The latter 1 must come from either $i$ or $j$. Assume it comes from $i$ (the other case is exactly similar). Then flipping that bit of $i$ produces a number $a_0$ such that $a_0\oplus j$ agrees with $c$ up to and including the bit position of first difference. With appropriate adjustments to the less significant bits we can get an $a$ such that $a\oplus j=c$. And this $a$ must be less than $i$, because $a$ and $i$ first differ on a bit position that has 1 in $i$ and 0 in $a$.

This completes the induction step, and thus the proof.

Related Question