Nim addition- binary addition without carrying

Question

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.

Answer 1

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.

Answer 2

Using your first method, the number entered in row $r$, column $c$ is the smallest non-negative integer not appearing earlier in row $r$ or column $c$; call this number $r\oplus c$. Then $r\oplus c$ is the smallest non-negative integer that does not belong to the set

$$\{r\oplus c':c'<c\}\cup\{r'\oplus c:r'<r\}\;;$$

this is commonly called the minimum excluded number and denoted by

$$\operatorname{mex}\Big(\{r\oplus c':c'<c\}\cup\{r'\oplus c:r'<r\}\Big)\;,$$

as in this article. This is equal to the non-carrying binary sum (or exclusive OR) of $r$ and $c$. The article gives a proof, but it’s pretty concise; I’ll try to expand it a bit. For non-negative integers $m$ and $n$ let $m\dot+n$ be the non-carrying binary sum of $m$ and $n$.

The proof is by induction. Suppose that we’ve already filled in all of the numbers $r\oplus c'$ with $c'<c$ and $r'\oplus c$ with $r'<r$, i.e., all of the numbers to the left of $r\oplus c$ in row $r$ and above it in column $c$, and suppose that that $r\oplus c'=r\dot+c'$ for $c'<c$ and $r'\oplus c=r'\dot+c$ for $r'<r$; we’ll show that this implies that $r\oplus c=r\dot+c$.

Let $n=r\dot+ c$. Then $r\dot+n=r\dot+r\dot+c=c$, since $r\dot+r=0$; that is, $c$ is the only non-negative integer whose noncarrying binary sum with $r$ is $n$. It follows that $r\oplus c'=r\dot+c'\ne n$ for each $c'<c$ and hence that $n\notin\{r\oplus c':c'<c\}$. Similarly, $r$ is the only non-negative integer whose noncarrying binary sum with $r$ is $n$, so $r'\oplus c=r'\dot+c\ne n$ for each $r'<r$, and $n\notin\{r'\oplus c:r'<r\}$. In other words, $n\notin\{r\oplus c':c'<c\}\cup\{r'\oplus c:r'<r\}$: $n=r\dot+c$ does not appear to the left of or above $r\oplus c$ and is at least a candidate to be $r\oplus c$.

Now suppose that $k<n=r\dot+c$; we want to show that $k\in\{r\oplus c':c'<c\}\cup\{r'\oplus c:r'<r\}$, i.e., that $k$ appears either to the left of or above $r\oplus c$, so that $r\oplus c\ne k$. This will imply that $n$ is the smallest available number and hence the value that we assign to $r\oplus c$. To do this, let $\ell=k\dot+n=k\dot+r\dot+c$.

Claim: Either $r>\ell\dot+r=k\dot+c$, or $c>\ell\dot+c=k\dot+r$.

Suppose for the moment that the claim is true. If $r>k\dot+c$, let $r'=k\dot+c$; then $k=(k\dot+c)\dot+c=r'\dot+c=r'\oplus c$ appears to the left of $r\oplus c$ in row $r$ and is not available to be $r\oplus c$. Similarly, if $c>k\dot+r$, let $c'=k\dot+r$; then $k=r\dot+(k\dot+r)=r\dot+c'=r\oplus c'$ appears above $r\oplus c$ in column $c$ and is not available to be $r\oplus c$. In either case $k$ is not available to be $r\oplus c$. Since $k$ was an arbitrary non-negative integer less than $n=r\dot+c$, it follows that $n$ is the smallest available integer and hence that $r\oplus c=n=r\dot+c$. This completes the induction step (apart from the proof of the claim), and the result follows.

Proof of Claim: Consider the most significant (leftmost) bit of the binary representation of $\ell$: it must be present in exactly one or all three of $k,r$, and $c$. If that bit were present in $k$, it would be zeroed out in $\ell\dot+k$, which would then be less than $k$. However, $\ell\dot+k=r\dot+c=n>k$, so this isn’t the case, and it must therefore be present in $r$ or in $c$. But then the same argument shows that if it’s present in $r$, then $\ell\dot+r<r$, and if it’s present in $c$, then $\ell\dot+c<c$, proving the claim. $\dashv$