The squares of an infinite chessboard are numbered successively as follows: in the lower left corner (first row, first column) we put 0 (zero), and then in every other square we put the smallest nonnegative integer that does not appear to its left in the same row or below it in the same column. See it partially filled:
| | | | | | | | |
+---+---+---+---+---+---+---+---+--
| 5 | | | | | | | |
+---+---+---+---+---+---+---+---+--
| 4 | 5 | | | | | | |
+---+---+---+---+---+---+---+---+--
| 3 | 2 | 1 | | | | | |
+---+---+---+---+---+---+---+---+--
| 2 | 3 | 0 | 1 | | | | |
+---+---+---+---+---+---+---+---+--
| 1 | 0 | 3 | 2 | 5 | | | |
+---+---+---+---+---+---+---+---+--
| 0 | 1 | 2 | 3 | 4 | 5 | | |
+---+---+---+---+---+---+---+---+--Find the law that rules the numbers that fills the chessboard, so that in seconds, you can evaluate the number that is, for example, in the intersection of the 1000th row and the 100th column.
|
|
Submitted by pcbouhid
|
|
Rating: 3.4286 (7 votes)
|
|
|
Solution:
|
(Hide)
|
The law is the "XOR" operation (binary sum, without carrying), as the solvers figured out, though we have not a proof, yet.
From the bottom and left, the first row and the first column present sequential numbers starting from 0. So, the row numbers and column numbers are 1 greater than these numbers.
Letsīsee the cell (2,2) that is filled with a 0. The numbers at the bottom and at the left are 1 and 1. Expressing these numbers in binary system and summing them up, WITHOUT CARRYING, we achieve:
1 = 1 in binary notation.
1 = 1 in binary notation
Summing up these two numbers (without carrying): 1
1
-
0which is 0 in decimal notation.
See the cell (2,4), that is filled with 2:
1 = 1 in binary notation
3 = 11 in binary notation.
Summing up (without carrying): 1
11
--
10which is 2 in decimal notation. And so on.
So the number in the (x,y) cell is the sum of the binary notation of (x-1) with (y-1), without carrying.
Thus, the number in the cell (1000,100) is:
999 is equal to 1111100111 in binary notation.
99 is equal to 1100011 in binary notation.
Summing up (without carrying), we achieve:
1111100111
1100011
----------
1110000100which is 900 in decimal notation.
The proof is still open!
|
