Today's problem has gotten me thinking about it several times for several reasons. In particular, the first time I came across it I was pretty sure I knew the answer but didn't really know how to formalize a proof. It was only a couple of years later, when I remembered the problem for no reason at all, that I was able to answer it completely.
Problem statement: imagine you have an infinite table with a checkerboard pattern. In the bottom leftmost corner you put a $0$. For every other cell, you insert the smallest non-negative integer that hasn't been used neither in the same row, to the left of the cell, nor in the same column, below it. So, for example, the first row will have the numbers $0, 1, 2, 3, \cdots $. What is the number that appears in the $1997$th row, $2018$th column?
Solution: the key here is to understand the way in which the board is filled. When I first solved the problem I started by filling a board on my own, to get a feel for the rules imposed. Doing so should make clear that, for example,
From now on we will renumber the rows and columns so that they start at $0$ and we will let $c(i,j) $ be the value in the $i $th row, $j $th column. Let $P(n)$ be the statement "the bottom left square of the table with side $2^n $ has, in every row, every single number from $0$ to $2^n -1$ and $\forall i,j \leq 2^n-1: c(i,j) = i \hat{} j $.
We will prove this by induction. The statement $P(0)$ is trivially true as the square with side $2^0 = 1$ is just the square with the number $0$ that the problem statement fills in for us, and $c(0,0) = 0 \hat{} 0 = 0$.
Assume $P(n)$ is true. We show that $P(n+1)$ is true as well. We have the "crossed out" square (call it square $0$) of the grid is already filled and we will fill the squares $1, 2$ and $3$ in this order. If $n = 2$ then this is our current position.
We start by filling in the square of size $2^n$ that is to the right of the square already filled. In every row, all numbers from $0$ to $2^n - 1$ have been used, so it should be fairly easy to see that the numbering on that square is going to be exactly the same as in the square $0$, except that we need to sum $2^n$ to each cell. We just need to check that the rule to compute the values still remains valid. Let $0 \leq i < 2^n$ and $0 \leq j < 2^n$. $(i, 2^n+j)$ is a valid pair for a row and a column of a cell in square $1$; $i \hat{} (2^n + j) = 2^n + (i \hat{} j) = 2^n + c(i,j)$ which is exactly the value we assigned to the cell $(i, 2^n + j)$. The reason why $i \hat{} (2^n + j) = 2^n + (i \hat{} j)$ is because $i < 2^n$. Just note that $2^n + j$ starts with a $1$ in binary, while $i$ has to start with a $0$ if we are to force the binary representations of $2^n + j$ and $i$ to have the same number of digits.
This puts us at:
Symmetry gives that square $2$ is just the same as square $1$. Showing that the XOR rule still works is completely analogous to the computation we just did for square $1$; we are now at:
So now we are left with understanding how square $3$ is filled in. Both to the left and below square $3$ all numbers from $2^n$ to $2^{n+1}-1$ have been used, so in each row and in each column we can still freely use any number from $0$ to $2^n - 1$. But that is exactly the same as if we were to fill square $0$, hence squares $3$ and $0$ are the same. Now let $0 \leq i, j < 2^n$. Then $(2^n + i, 2^n + j)$ is a pair of coordinates of a cell in square $3$ and it is immediate that $c(2^n+i, 2^n+j) = (2^n + i)\hat{}(2^n+j) = i\hat{}j = c(i,j)$, which is the value in the corresponding cell in square $0$, leaving us at
This concludes the inductive step, and hence the XOR rule works! To compute the value in the cell with row $1997$ and column $2018$ we just have to write $1996$ and $2017$ in binary:
$$1996 = 1024 + 512 + 256 + 128 + 64 + 8 + 4 \\
2017 = 1024 + 512 + 256 + 128 + 64 + 32 + 1$$
which means $1996$ is $11111001100$ in binary while $2017$ is $11111100001$, thus
$$c(1996, 2017) = 11111001100 \hat{} 11111100001 = 00000101101$$
And the number we are after is exactly $1 + 4 + 8 + 32 = 45$.
Let me know what you think!
-RGS
Problem statement: imagine you have an infinite table with a checkerboard pattern. In the bottom leftmost corner you put a $0$. For every other cell, you insert the smallest non-negative integer that hasn't been used neither in the same row, to the left of the cell, nor in the same column, below it. So, for example, the first row will have the numbers $0, 1, 2, 3, \cdots $. What is the number that appears in the $1997$th row, $2018$th column?
Solution: the key here is to understand the way in which the board is filled. When I first solved the problem I started by filling a board on my own, to get a feel for the rules imposed. Doing so should make clear that, for example,
- the number in the diagonal is always a $0$;
- the board is symmetric along the diagonal, i.e. the number in column $j $ and row $i$ is the same number as in row $j $ and column $i $.
The interested reader is left with trying to get a feel for the pattern involved in filling the board. We skip right into the full solution.
Claim: the number in the $i+1$th row and $j+1$th column is $i \hat{} j $, where $\hat{}$ is the binary XOR operation.
Notice how this aligns with the two (obvious) observations made:
- the diagonal only has zeros; in the diagonal the row $i $ and column $j $ are the same, $i = j $ and $x \hat{} x = 0$;
- being in row $i $ and column $j $ is the same as being in column $i $ and row $j $; $x \hat{} y = y \hat{} x $.
We will prove this by induction. The statement $P(0)$ is trivially true as the square with side $2^0 = 1$ is just the square with the number $0$ that the problem statement fills in for us, and $c(0,0) = 0 \hat{} 0 = 0$.
Assume $P(n)$ is true. We show that $P(n+1)$ is true as well. We have the "crossed out" square (call it square $0$) of the grid is already filled and we will fill the squares $1, 2$ and $3$ in this order. If $n = 2$ then this is our current position.
We start by filling in the square of size $2^n$ that is to the right of the square already filled. In every row, all numbers from $0$ to $2^n - 1$ have been used, so it should be fairly easy to see that the numbering on that square is going to be exactly the same as in the square $0$, except that we need to sum $2^n$ to each cell. We just need to check that the rule to compute the values still remains valid. Let $0 \leq i < 2^n$ and $0 \leq j < 2^n$. $(i, 2^n+j)$ is a valid pair for a row and a column of a cell in square $1$; $i \hat{} (2^n + j) = 2^n + (i \hat{} j) = 2^n + c(i,j)$ which is exactly the value we assigned to the cell $(i, 2^n + j)$. The reason why $i \hat{} (2^n + j) = 2^n + (i \hat{} j)$ is because $i < 2^n$. Just note that $2^n + j$ starts with a $1$ in binary, while $i$ has to start with a $0$ if we are to force the binary representations of $2^n + j$ and $i$ to have the same number of digits.
This puts us at:
Symmetry gives that square $2$ is just the same as square $1$. Showing that the XOR rule still works is completely analogous to the computation we just did for square $1$; we are now at:
So now we are left with understanding how square $3$ is filled in. Both to the left and below square $3$ all numbers from $2^n$ to $2^{n+1}-1$ have been used, so in each row and in each column we can still freely use any number from $0$ to $2^n - 1$. But that is exactly the same as if we were to fill square $0$, hence squares $3$ and $0$ are the same. Now let $0 \leq i, j < 2^n$. Then $(2^n + i, 2^n + j)$ is a pair of coordinates of a cell in square $3$ and it is immediate that $c(2^n+i, 2^n+j) = (2^n + i)\hat{}(2^n+j) = i\hat{}j = c(i,j)$, which is the value in the corresponding cell in square $0$, leaving us at
$$1996 = 1024 + 512 + 256 + 128 + 64 + 8 + 4 \\
2017 = 1024 + 512 + 256 + 128 + 64 + 32 + 1$$
which means $1996$ is $11111001100$ in binary while $2017$ is $11111100001$, thus
$$c(1996, 2017) = 11111001100 \hat{} 11111100001 = 00000101101$$
And the number we are after is exactly $1 + 4 + 8 + 32 = 45$.
Let me know what you think!
-RGS
Problem #05 - number me right
Reviewed by Unknown
on
January 23, 2018
Rating:
Reviewed by Unknown
on
January 23, 2018
Rating:
No comments: