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:

0 1 2 3 4 5 6 7 ... 1 0 3 2 5 4 7 6 ... 2 3 0 1 6 7 4 5 ... 3 2 1 0 7 6 5 4 ... 4 5 6 7 0 1 2 3 ... 5 4 7 6 1 0 3 8 ... 6 7 4 5 2 3 0 1 ... 7 8 5 4 3 2 1 0 ... ... ... ... ... ... ... ... ... ...

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 2^N-1×2^N-1 square which I denote as S_N-1. On the next step, the square S_N combines four pieces:

SN-1 SN-1 + 2N-1 SN-1 + 2N-1 SN-1

where 2^N-1 denotes a 2^N-1×2^N-1 matrix whose entries are all equal to 2^N-1. The four pieces may also be designated as S_nw, S_ne, S_se, and S_sw.

By construction, S_N-1 is a Latin square on the set of integers from 0 through 2^N-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 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^N-1 whereas none of the elements of S_se exceeds 2^N-1 - 1. Furthermore, every row and every column of both S_ne and S_sw are formed by a distinct permutation of the set {2^N-1, 2^N-1 + 1, 2^N-1 + 2, ..., 2^N - 1}. Therefore, elements in S_se automatically satisfy (P) since by the inductive assumption this is true for S_nw.

For S_ne, (P) may be reformulated as

(P')	The entry in each cell is the smallest nonnegative integer not less than 2N-1 that has not been yet used to its left in the same row and above it in the same column.

But clearly (P') holds for S_ne provided (P) holds for S_nw. Verification of (P) for, say S₁, 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.

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 (m, n)-cell. Then

amn = 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,

a100, 1000 = 100 ^ 1000 = (1100100)2 ^ (1111101000)2 = (1110001100)2 = 908.

[Of course, if initially rows and columns were counted starting with 1, then we should consider instead 99 ^ 999 which is 900!]

Exercises

1. Prove the above Proposition. (Proof).
2. Prove that the number of inversions in row #j = 0,1,2,... of S_N equals j2^(N-1).

References

1. D. Gale, Tracking the Automatic Ant, Springer-Verlag, 1998, p. 189 on.
2. R. Honsberger, In Polya's Footsteps, MAA, 1997
3. 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
  • Latin Squares (An Interactive Gizmo)
• Two Simple Problems with Latin Squares
• Latin Squares. Simple Construction
• Orthogonal Latin Squares
  • An Interactive Gadget: Orthogonal Latin Squares
• Marriage Problem, a constructive proof
  • Marriage Problem, two proofs
  • Marriage Problem. An Interactive Demontsration of a Constructive Proof
    • Marriage Theorem, Solutions to Problems
• Robbers divide their loot
• Infinite Latin Squares
  • A Problem on an Infinite Checkerboard
• Skyscrapers Puzzle

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Proposition

amn = 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 a = x then (m, n) lies in the S_sw square of the smallest square S_N that contains (m, n). By dropping 2^a from m and 2^x from n, the point is moved into S_N-1 without changing m^n. If, say, a > x, (m, n) lies in S_se. Add 2^a to X and drop it from m. The point will move into S_N-1. X will become the original m^n.

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|

Copyright © 1996-2018 Alexander Bogomolny