Infinite Latin Squares
A Latin square of order n is an n×n array of n symbols in which every symbol occurs exactly once in each row and column of the array. There are several very simple ways to obtain Latin squares of any given order n. For example, write the sequence of integers
Assume now we wish to construct an infinite Latin square. More accurately, the square expands in two directions: rightwards and downwards. The problem is to fill the square (or rather a quadrant) with integers 0, 1, 2, 3, ... so that every term of the sequence will appear in every row and every column of the quadrant exactly once. (I started the sequence with 0 for the convenience sake. The reason will become clear later. However, this should be obvious that any countable collection of arbitrary objects would serve as well.)
Will the cycling procedure that served us so well in the finite case work now? Can we cycle through an infinite sequence? In principle, we can. However, the result - 1, 2, 3, .... 0, where 0 follows all the rest of the numbers - is no longer a sequence. It is impossible to fit it into the second row of the quadrant. For a row in that table does not have a last cell whereas 0 is the very last element of the rotated sequence. The set remains countable as it was before. But now the order of elements is also important. There is no order preserving 1-1 correspondence between the two ordered sets, 0, 1, 2, 3, ... and 1, 2, 3, .... 0. If such one existed, what element from the first set would correspond to 0 in the second? Think of the next element. What would correspond to it from the second set?
Rudy Rucker poses the following problem:
"I have five fingers on my left hand," means the same thing as, "When I count up all the fingers on my left hand, the last number I say is five." What might "I have ∞ fingers on my left hand" mean?
The answer is that it would mean you have infinity-plus-one fingers. A curious thing about infinity is that you never count up to it. You count through every finite stage but never reach the last finger. If there is an "∞ finger", then it comes after an infinity of fingers and indicates that you have infinity fingers plus one more (which you named ∞). Still, the problem of constructing an infinite Latin square has infinitely many solutions. The applet below is intended to demonstrate one possible approach. Starting in the quadrant's corner with zero, we expand the square step by step, doubling its side on every step. With the side beyond 25, the font needed is so small that the numbers become blurred and indistinguishable. Instead, the applet shows a colorful carpet with a color for every term determined modulo a selected number.
The solution at hand derives from the traditional notion of the positional number system. Let's have a short table of a few first integers in the binary system.
We start with 0 - one (1) single number. Use this 1 as a clue. To get the second number, add 1 to zero just once. After that we shall have two (2) numbers: 0 and 1. Add 2 to the two of them to obtain the next two numbers. We have now four (4): 0, 1, 2, 3. Add 4 to all four in turn to get the next four, and so on. In the binary system, each step consists of writing all previously obtained numbers twice and prepending the binary digit 1 to the second copy of every number. The construction of the Latin square is very similar. First, fill the corner square of size 1x1 with the number 0. On the next step, we get a square of size 2x2. The latter consists of four squares equal in size to the square on the previous step. I'll denote them generically as Snw, Sne, Sse, and Ssw. Snw is the square from the previous step. Copy it into three other squares, and lastly add 1 (the side of Snw) to every element of Sne and Ssw. Assume a corner square of size 2n has been filled. Denote it as Snw. Copy it into adjacent squares Sne, Sse, and Ssw and add 2n to every element of Sne and Ssw. Every corner square of side 2n is a Latin square with elements 0, 1, ..., This construction solves problem M1123 from the Russian magazine Kvant [Cofman, p 107]: Is it possible to place into each cell of a doubly infinite array of square cells a natural number so that each row of the cells and every column contains any natural number exactly once? References
Latin Squares
|Contact| |Front page| |Contents| |Algebra| Copyright © 1996-2018 Alexander Bogomolny71471470 |