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:

 
01234567...
10325476...
23016745...
32107654...
45670123...
54761038...
67452301...
78543210...
...........................

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

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

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 2N-1 - 1. Furthermore, every row and every column of both Sne and Ssw are formed by a distinct permutation of the set {2N-1, 2N-1 + 1, 2N-1 + 2, ..., 2N - 1}. Therefore, elements in Sse automatically satisfy (P) since by the inductive assumption this is true for Snw.

For Sne, (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 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.

Proposition

Assume we count rows and columns starting with 0: 0, 1, 2, and so on. Let amn 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 SN 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

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

Copyright © 1996-2017 Alexander Bogomolny

Proposition

  amn = m ^ n.

Proof

Let m = 2a + 2b + 2c + ..., a > b > ..., n = 2x + 2y + 2z + ..., x > y > ... And set X = 0. If a = x then (m, n) lies in the Ssw square of the smallest square SN that contains (m, n). By dropping 2a from m and 2x from n, the point is moved into SN-1 without changing m^n. If, say, a > x, (m, n) lies in Sse. Add 2a to X and drop it from m. The point will move into SN-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| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62031898

Search by google: