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.
This proof isn't entirely original--some of the ideas came from things I found doing a Google search on "XOR" and "Latin Square". But I assembled the ideas to form the following proof, myself. It's not a perfectly formal proof (for you math purists), but if you follow along slowly, using an example as you go, I think you'll be convinced of the validity.
We start by presenting a third method of constructing the result, and then showing that this method will yield the same result as both the method described in this puzzle, as well as the XOR table for all integers. By proving that both results are equal to a third result, we can conclude that they're equal to each other.
Here's the third method.
(1) Start with a single cell and put a zero in it. (this is iteration 0)
(2) Double the size (length and width) of the array of squares. If you call the array we had up to this point S1, consider that we've added 3 more squares: one to the right of S1, which we'll call S2; one directly above S1, which we'll call S3, and one directly above S2, which we'll call S4. Here they are visually.
S3 S4
S1 S2
The contents of S1 have already been filled; we want to fill the other three.
(3) Replicate all the cells from S1 into S2 and add 2^n, where n is the iteration we're on. (At iteration 0, 2^0 = 1, so we add 1 to the single cell we just moved to S2.)
(4) Replicate all the cells from S2 into S3 (with no change).
(5) Replicate all the cells from S1 into S4 (with no change). Iteration 0 now looks like this
1 0
0 1
(6) Add one to the iteration number and go back to step (2).
At the end of iteration 2 we have (spacing inserted to show the squares S1, S2, S3 and S4).
3 2 1 0
2 3 0 1
1 0 3 2
0 1 2 3
At the end of iteration 3
7 6 5 4 3 2 1 0
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4
2 3 0 1 6 7 4 5
1 0 3 2 5 4 7 6
0 1 2 3 4 5 6 7
Continue, until the square is as big as you like.
Lemma: At the end of each iteration, the result is a "Latin Square" with side = 2^n. A Latin Square is simply a square array of numbers in which every row and column contain every number from 0 to s-1 (where s is the number of cells on one edge), and no row or column contains the same number twice.
This is relatively easy to prove by induction--I'll leave it as an "exercise for the reader." It follows similar logic to the first of the two parts in the proof below.
---------------------------------------------------------------------------
Part 1: The method in the original puzzle (filling each cell with the smallest number not already present to the left or below it) yields this same result as this third method. We proceed by induction: Prove the case for iteration 0, assume it's true for iteration n, and show that it's true for n+1.
We can see by inspection that it's true for iteration 0. The 2x2 array above is exactly what you get when you follow the rules of the puzzle to fill a 2x2 square.
So, we assume that we have a 2^n x 2^n array filled with numbers according to the rule of the puzzle. Call this S1 as above, and construct S2, S3, and S4 as above. By filling S2 as described in our method above, we can see that every cell follows the rule of the puzzle for numbers 2^n + 1 through 2^(n+1). All we've done is add a constant to every number...it just changes the lowest allowable number. So, knowing that S1 follows the rules of the puzzle (always picking the smallest number not already present below or to the left), S2 is just the same solution starting at 2^n + 1 instead of 0.
Furthermore, since all the numbers from 0 through 2^n are used in every row in S1 (by the lemma above), we can't use any of those numbers in S2 when we append S2 to the right of S1. So S1 and S2 together must follow the puzzle rules for every cell in that rectangle.
By a symmetrical argument we can replicate S2 to S3, and still be confident that we've followed the rules in the puzzle for S3.
Finally, we can replicate S1 to S4 as is. We know we're safe doing this, because none of the numbers in S1 exist in S2 or S3. Therefore, since S1 follows the rules of the puzzle, so does S4, since there's no conflict with the numbers to the left (S3) or below (S2), and it's already a valid arrangement when there's nothing to the left or below it...it's a copy of S1!
Hence this method produces the same result as the puzzle.
---------------------------------------------------------------------------
Part 2: This third method constructs the XOR table for all integers. We proceed by induction as above.
Again we can see by inspection that it's true for iteration 0 (the 1x1 square), since 0xor0 = 0.
Assume it's true (that it is an XOR table) for iteration n, where the square size is 2^n on each side. (we'll use iteration 2 as an example, where the square size is 4x4--see above illustration--lower left quarter).
In iteration n+1, again consider the 4 squares S1, S2, S3 and S4 as described above...S1 is just iteration n. (In our example, iteration 3 is the 8x8 square above--visually divided into the four squares we're talking about).
To discuss the XOR operation, we'll look at the binary representation of every number. In the nth iteration every number in the square can be represented as an n-digit binary number (with leading zeros on some of them). (In our example, the 4x4 grid looks like this:
11 10 01 00
10 11 00 01
01 00 11 10
00 01 10 11)
Going to the next iteration (n+1), we first prefix every existing number with a 0 (which doesn't change it's value--it just makes it a (n+1)-digit binary number). (In our example...
011 010 001 000
010 011 000 001
001 000 011 010
000 001 010 011)
Then we follow the instructions for the third method to create S2 from S1. In binary, all we do is change the first digit of each cell in S2 from a zero to a 1. (In our example, S1 and S2 look like this in binary...
011 010 001 000 111 110 101 100
010 011 000 001 110 111 100 101
001 000 011 010 101 100 111 110
000 001 010 011 100 101 110 111)
Consider any cell in S1 in row a, column b (counting rows and columns from the lower left starting at 0). Because of our inductive assumption, this cell contains the value a xor b. (in our example, let's choose row 1 column 2. We see that the value there in iteration 1 is 11, And, sure enough 1 xor 2 is 3, or 11 in binary.) The corresponding cell in S2 would be in row 0a, column 1b (here, 0a means the digit 0 followed by a, and 1b is the digit 1 followed by b). (In our example, 0a would be 001, 1b would be 110, so the cell we're referring to happens to contain 111.) 0a xor 1b (assuming a and b are the same length binary numbers) produces 1 followed by (a xor b), which is exactly what's in that cell, by construction. So, S1 a valid extension of the XOR table for all cells in it.
A symmetrical argument works for square S3. Just flip the rows and columns.
For square S4, we would consider the value (1a xor 1b). Since 1 xor 1 = 0 this is just a xor b. This would imply that S4 should be identical to S1, which exactly what this third construction method tells us to do.
So, this method does indeed produce the XOR table for all integers.
---------------------------------------------------------------------------
Finally, since two things equal to a third are equal to each other--we have our proof.
A proof!
