# 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 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 2
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 S Every corner square of side 2 This construction solves problem M1123 from the Russian magazine ## References- J. Cofman,
*Numbers and Shapes Revisited*, Clarendon Press, 1995 - R. Rucker,
*Infinity and the Mind*, Princeton University Press, 1995
## 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
- Skyscrapers Puzzle
|Contact| |Front page| |Contents| |Algebra| Copyright © 1996-2018 Alexander Bogomolny66212171 |