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.
I don't understand Josh70679's answer. But maybe this is what he meant, since I agree with his result.
Assuming that this is a 0-based chessboard (by that I mean, that F(0,0)=0, F(3,1)=2, F(3,2)=1, etc...), and
Where | = the bitwise or operator... the value of a cell is given by:
F(x,y) = 2*(x|y) - (x+y)
also read as 2 times the bitwise result of x OR y less the sum of x and y.
the value at the 1000th row and 100th column would be F(99,999) would be
900.
Edited on October 28, 2005, 2:40 pm
answer
