Originally Posted by
Aquafina I have attached the image of the chessboard
The squares of an infinite chessboard are numbered as follows: in the first row and first column we put 0, and then in every other square we put the smallest non-negative integer that does not appear anywhere below it in the same column or anywhere to the left of it in the same row.
What number will appear in the 1000th row and 700th column? Can i generalize this?
I think the number in the 1000th row and 700th column will be 348, but I don't have a complete proof of that.
The pattern that you see from the first few rows and columns makes it clear that things happen in powers of 2.
$\displaystyle \begin{array}{cccc|cccc|cccccccc}
6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\
5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\
4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\ \cline{1-8}
3&\multicolumn{1}{c|}{2}&1&0&7&6&5&4&11&10&9&8&15& 14&13&12\\
2&\multicolumn{1}{c|}{3}&0&1&6&7&4&5&10&11&8&9&14& 15&12&13\\ \cline{1-4}
1&\multicolumn{1}{c|}{0}&3&2&5&4&7&6&9&8&11&10&13& 12&15&14\\
0&\multicolumn{1}{c|}{1}&2&3&4&5&6&7&8&9&10&11&12& 13&14&15
\end{array}$
(The TeX compiler used for the Forum won't allow me to display more than the bottom 7 rows. You'll have to add a couple more to make the pattern more obviously visible.)
The bottom left 2×2 block consists of 0s on the southwest–northeast diagonal, and 1s in the off-diagonal positions. The bottom left 4×4 block consists of two copies of the bottom left 2×2 block, on the diagonal; and copies of that same block with 2 added to each element, in the off-diagonal positions. The bottom left 8×8 block consists of two copies of the bottom left 4×4 block, on the diagonal; and copies of that same block with 4 added to each element, in the off-diagonal positions. And so on, building up blocks of size $\displaystyle 2^n\times2^n$, each such block consisting of two copies of the previous block, on the diagonal; and two copies of the previous block with $\displaystyle 2^{n-1}$ added to each element, in the off-diagonal positions.
So, how do we compute the number in the (m,n)-position? The book-keeping becomes much easier if you start numbering rows and columns from 0 rather than 1. So the bottom left corner of the chessboard is row 0 and column 0. The algorithm that seems to work (though I don't have a proof for it) is to form the binary representation of m and n, and then take their bitwise sum (mod 2). That gives the binary representation of the number in the (m,n)-position.
If it's not clear what that means, here's an example. We want to know the number in the 1000th row and 700th column. But if the numbering starts at 0 rather than 1, that means we should take m=999 and n=699. The first step is write these numbers in base 2, getting m = 11111100111 and n = 1010111011. Now "add" these numbers together, treating 1+1 as 0 (or using what computer scientists call a XOR gate):
Code:
1111100111
1010111011
0101011100
The resulting number 101011100 is the base 2 representation of 348.
As I said, I don't have a proof of that, but try it on some smaller numbers and you'll see that it works.