A Problem on an Infinite Checkerboard
Suppose that a nonnegative integer is put into each square of a checkerboard that extends indefinitely downward and to the right, the numbers being entered from left to right in the rows and the rows done from the top downward so that the entry in each cell is the smallest nonnegative integer that has not been yet used to its left in the same row and above it in the same column.
Thus the top left corner starts things off with 0 and the top row and the leftmost column are each completed with the positive integers 1,2,3,..., in order. The problem is to find the entry in the 100th row and 1000th column.
Well, if every time we fill another cell, we use only integers that have not so far appeared in the same column and the same row, then it is impossible to get a repeated integer in either the same column or the same row. Put another way, the process stipulated by the conditions of the problem leads to an infinite Latin square. This is amazing how the same problem may reappear in a different guise. Let's fill first few cells:

This is exactly the Latin Square we encountered in a different setting. We may actually prove that our old acquaintance satisfies the Description of the current problem. This is a nice exercise in induction.
Let's describe again the structure of the square. We construct it recursively starting with a single cell  a 1×1 square. The next step generates a 2×2 square, the third on  4×4, and so on. Step number N results in a

where 2^{N1} denotes a 2^{N1}×2^{N1} matrix whose entries are all equal to 2^{N1}. The four pieces may also be designated as S_{nw}, S_{ne}, S_{se}, and S_{sw}.
By construction, S_{N1} is a Latin square on the set of integers from 0 through 2^{N1}1. Assume that this square has the required property:
(P)  The entry in each cell is the smallest nonnegative integer that has not been yet used to its left in the same row and above it in the same column. 
We'll show then that the square S_{N} also has the property (P). All squares are symmetric with respect to the diagonal from the top left corner. Therefore, we need only consider two parts: S_{ne} and S_{se}. S_{ne} (as does S_{sw}) consists of elements the smallest of which is 2^{N1} whereas none of the elements of S_{se} exceeds
For S_{ne}, (P) may be reformulated as
(P') 
The entry in each cell is the smallest nonnegative integer not less than 
But clearly (P') holds for S_{ne} provided (P) holds for S_{nw}. Verification of (P) for, say S_{1}, is trivial. Which concludes the inductive proof.
Condition (P) is reminiscent of the Mex Rule which suggests that the nimsum must be of some use in solving our problem. Moreover, the explicit structure of our Latin square illuminates the relationship between the Mex Rule and the XOR operation applied on the set of all nonnegative integers.
Proposition
Assume we count rows and columns starting with 0: 0, 1, 2, and so on. Let a_{mn} denote the number that appears in the
a_{mn} = m ^ n. 
It follows that this particular Latin square serves as the "addition" table for the XOR operation over the set of nonnegative integers. In particular, using the binary representation,

[Of course, if initially rows and columns were counted starting with 1, then we should consider instead 99 ^ 999 which is 900!]
Exercises
 Prove the above Proposition. (Proof).
 Prove that the number of inversions in row #j = 0,1,2,... of S_{N} equals j2^{(N1)}.
References
 D. Gale, Tracking the Automatic Ant, SpringerVerlag, 1998, p. 189 on.
 R. Honsberger, In Polya's Footsteps, MAA, 1997
 A. M Yaglom, Y. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. 2, Dover Publications (December 1, 1987), #127
Latin Squares
 Latin Squares: An Introduction
 Two Simple Problems with Latin Squares
 Latin Squares. Simple Construction
 Orthogonal Latin Squares
 Marriage Problem, a constructive proof
 Robbers divide their loot
 Infinite Latin Squares
 A Problem on an Infinite Checkerboard
 Skyscrapers Puzzle
Contact Front page Contents Algebra Store
Copyright © 19962017 Alexander BogomolnyProposition
a_{mn} = m ^ n. 
Proof
Let m = 2^{a} + 2^{b} + 2^{c} + ..., a > b > ..., n = 2^{x} + 2^{y} + 2^{z} + ..., x > y > ... And set X = 0. If
The process will continue while either m or n are not zero. Every time one of them has a binary bit which is 0 in the other, this bit is removed from the number but added to X. At the end of the day, m = n = 0 whereas X contains m^n of the original m and n.
Contact Front page Contents Algebra Store
Copyright © 19962017 Alexander Bogomolny62031898 