Latin Squares in Practice and in Theory II
Feature Column Archive
Alex Bogomolny's Cut The Knot! website has a page on Orthogonal Latin Squares with some nice examples using the Galois field of order 4. There is a nice article by Edythe Parker Woodruff about her brother E. T. Parker's work on the ``Euler conjecture.'' Rob Beezer's Graeco-Latin Squares page shows a 10 x 10 ``Euler spoiler.'' The survey article by Charles Colbourn and Jeff Dinitz, from which the table of lower bounds on N(n) is reproduced, is available online.
1. Leonhard Euler's Puzzle of the 36 Officers
Une question fort curieuse is the way Euler introduces this puzzle. It involves 36 officers from six regiments. In this illustration we will distinguish the regiments by their colors: black, red, blue, green, purple and brown. Each regiment is represented by officers of six different ranks, which here we will characterize as King, Queen, Rook, Bishop, Knight, Pawn. Here they are (set in Eric Bentzen's Chess Alpha):
Ther problem is to line them up in a six by six array so that each row and each column holds one officer of each rank and one officer from each regiment.
Try it. It's impossible.
But if we replace ``six'' with ``five''
or with ``seven'' (adding yellow as the extra regiment and Joker as the extra rank)
the problem can be solved, as shown.
What is the matter with six? It's not just that it is composite, because the problem can be solved for 4, 8 and 9, and in fact for any number besides 2 (obviously impossible) and 6. Euler did not actually prove that 6 was impossible. (Or, après toutes les peines qu'on s'est données pour résoudre ce problème, on a été obligé de reconnoître qu'un tel arrangement est absolument impossible, quoiqu'on ne puisse pas en donner de démostration rigoureuse.) The proof waited from 1782 until 1900, when it was worked out by G. Tarry. Euler did show that there was a solution for any number of regiments (and of ranks) not of the form 4s+2. He remarked that his method does not work for numbers of that form. After his death, this remark metamorphosed into a conjecture that there was no solution for those numbers; the conjecture lived on until 1959 when E. T. Parker, R. C. Bose and S. Shrikhande, working separately and then together, showed that it was false for all s greater than one.
In this column we will explore the topic of mutually orthogonal latin squares, the modern setting for the problem of the officers and its generalizations.