I have been given the following math puzzle:
You are given a matrix that is filled by the following rule:
Every cell i,j is evaluated by taking the lowest non-negative number that is not present in the column above it or the row to its left. (by this rule, first row / column of matrix should be 0,1,2,3...)
The first elements of the matrix are
\begin{bmatrix}0&1&2&3&4&...\\1&0&3&2&5\\2&3&0&1&6\\3&2&1&0&7\\4&5&6&7&0\\... \end{bmatrix}
i.e. A(2,3) = lowest non-negative not present in {2,3,0} and not in {3,2} . giving us A(2,3)=1
The puzzle asks for a direct formula of A(i,j).
[Spoiler alert] The answer: (hover with mouse to view answer)
A(i,j) = XOR(i,j)
I solved the puzzle but only via pattern matching,
My question is: how does the way we built the matrix connect with the answer ?
I found a refrence of the table under Nimber (defined as the values of nim heaps) http://en.wikipedia.org/wiki/Nimber#mediaviewer/File:Z2%5E4;_Cayley_table;_binary.svg , maybe this would help make a connection i couldn't.
We can construct the matrix in chunks to explain the pattern; in particular, suppose we generate matrices $M_n$ of size $2^n\times 2^n$ with the desired property. Let's look at the structure of $M_1$ and $M_2$: $$M_1=\begin{bmatrix}0 && 1 \\ 1 && 0\end{bmatrix}$$ $$M_2=\begin{bmatrix}0 && 1 && 2 && 3 \\ 1 && 0 && 3 && 2 \\ 2 && 3 && 0 && 1 \\ 3 && 2 && 1 && 0\end{bmatrix}.$$ What is notable here is that $M_2$ can be decomposed into four $2\times 2$ sections as: $$M_2=\begin{bmatrix}A && B \\ C &&D\end{bmatrix}$$ Clearly, the upper left corner $A$ of $M_2$ equals $M_1$ from definition. Then, the upper right corner $B$ of $M_2$ has $M_1$ to its left, hence cannot contain $0$ or $1$ anywhere, as each row of $M_1$ has $0$ and $1$ in it. However, if we generate $B$ with the rules, "each element of $B$ is the lowest element other than $0$ or $1$ not to its left or above it", we have essentially deleted $0$ and $1$ from the problem - and end up shifting the problem by adding $2$ to every element of $M_1$. Denote this matrix $B=M_1+2$. We can argue the same for $C$. Then, $D$ equals $M_1$, since above and to its left are $B$ and $C$ which use only $2$ and $3$ - which is irrelevant, as $D$ can be constructed without using $2$ or $3$. Thus, we can write: $$M_2=\begin{bmatrix}M_1 && M_1+2\\M_1+2&&M_1\end{bmatrix}.$$ In fact, we can write: $$M_0=\begin{bmatrix}0\end{bmatrix}$$ $$M_{n+1}=\begin{bmatrix}M_n && M_n + 2^n\\M_n+2^n && M_n\end{bmatrix}$$ to recursively define the matrix. The correctness of this is proven analogously as the decomposition of $M_2$ into copies of $M_1$ - we just use induction and note that $M_n$ uses every integer in $[0,2^n)$ in every row and column and that the upper left and bottom right quadrants mustn't use those numbers, leading to them being shifted.
How does this relate to XOR? Well, suppose we wish to calculate the element at row $x$ and column $y$ of $M_{n+1}$ (for $2^{n+1}>x,y$). Then, if we see $$M_{n+1}=\begin{bmatrix}M_n && M_n + 2^n\\M_n+2^n && M_n\end{bmatrix}$$ if the $n^{th}$ bit of $x$ is $0$, then the element is on the left half of the matrix. If the $n^{th}$ bit of $y$ is $0$, then the element is on the top half of the matrix. Noting that if we define $x’$ and $y’$ to be $x$ and $y$ truncated to $(n-1)$ bits, then these describe the position of $(x,y)$ relative to whichever quadrant it lies in - its position in $M_n$, essentially. Then, the above form tells us that we add $2^n$ to the value at position $(x’,y’)$ in $M_n$ if and only if the $n^{th}$ bit of $x$ and $y$ differ (as if they are the same, the expression is $M_n$ and otherwise it is $M_n+2^n$. However, then we apply this recursively - now we examine the $(n-1)^{th}$ bits of $x’$ and $y’$ (which are the same as those bits in $x$ and $y$) and add $2^{n-1}$ if they disagree - and we keep summing all these terms until we’ve gone through every bit. Oh, except that’s also how we XOR numbers together!