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.

It looks like the rule comes in two parts: 

First, the bottom row and left-most column are steadily increasing by one as they go to the right or up respectively. 

Second, for each integer n, if you divide the grid into squares of size 2^n, each of these squares is symmetrical about each of its diagonals. 

Using this, you can fill in the grid with exponentially-increasing speed.  If i'm right, entry (1000, 100) is 900 or 908, depending on whether the first box is (1,1) or (0,0).  I'll flesh out my algorithm for finding a specific entry later, if i have time.

Edited on October 28, 2005, 1:28 pm

Posted by Josh70679 on 2005-10-28 13:07:38