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 2N-1 denotes a 2N-1×2N-1 matrix whose entries are all equal to 2N-1. The four pieces may also be designated as Snw, Sne, Sse, and Ssw.
By construction, SN-1 is a Latin square on the set of integers from 0 through 2N-1-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 SN 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: Sne and Sse. Sne (as does Ssw) consists of elements the smallest of which is 2N-1 whereas none of the elements of Sse exceeds
For Sne, (P) may be reformulated as
The entry in each cell is the smallest nonnegative integer not less than |
But clearly (P') holds for Sne provided (P) holds for Snw. Verification of (P) for, say S1, is trivial. Which concludes the inductive proof.
Condition (P) is reminiscent of the Mex Rule which suggests that the nim-sum 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.
Assume we count rows and columns starting with 0: 0, 1, 2, and so on. Let amn denote the number that appears in the
|amn = m ^ n.|
[Of course, if initially rows and columns were counted starting with 1, then we should consider instead 99 ^ 999 which is 900!]
- Prove the above Proposition. (Proof).
- Prove that the number of inversions in row #j = 0,1,2,... of SN equals j2(N-1).
- D. Gale, Tracking the Automatic Ant, Springer-Verlag, 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
|amn = m ^ n.|
Let m = 2a + 2b + 2c + ..., a > b > ..., n = 2x + 2y + 2z + ..., 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.