Catherine the Great and Leonhard Euler
Catherine the Great and Leonhard Euler · Source

According to legend, Empress Catherine the Great posed this puzzle to the celebrated mathematician Leonhard Euler.

“Among 36 officers there are equal numbers of lancers, dragoons, hussars, cuirassiers, horse guards and grenadiers, and also equal numbers of generals, colonels, majors, captains, lieutenants and second lieutenants. Each branch’s regiment is represented by officers of all six ranks. Can the officers be arranged in a 6×6 square so that every column and every row contains officers of every regiment and every rank?”

To avoid confusion over unfamiliar military ranks, let us state it more simply:

“Arrange 36 officers from six different regiments and of six different military ranks in a square, so that every column and every row contains exactly one officer of each regiment and each rank.”

Try finding such an arrangement yourself. Begin, for example, with a 3×3 or 4×4 square. The puzzle is also said to be easy with five ranks and five regiments, or seven ranks and seven regiments. Solutions appear later in the article.

The problem was formulated in 1779 in a memoir of the St Petersburg Academy of Sciences, An Investigation of a New Type of Magic Square. The memoir began with the problem “On 36 officers”.

Academician Euler struggled with it for a long time. He solved it for 25 officers. After unsuccessful searches in the case of 36, however, he concluded that “such an arrangement is impossible, although we cannot give a rigorous proof of this”. Thus another mathematical conjecture arose.

Thousands of mathematicians subsequently worked on it. Only in 1959 was it proved that the problem can be solved for every square number greater than 2×2, except thirty-six. Mathematicians used computers to prove that solutions exist for every number of regiments and ranks greater than two, except six.

Latin squares

Euler’s thirty-six officers problem initiated the study of “Latin squares”.

A Latin square of order n is an n×n square table filled with n distinct elements from a set, each appearing exactly once in every row and column.

Leonhard Euler used letters of the Latin alphabet, giving the squares their name; more precisely, he used Graeco-Latin squares.

Orthogonal Latin squares of order 5×5
Orthogonal Latin squares of order 5×5 · Source

Two Latin squares of the same order are orthogonal if, when superimposed, all the resulting letter pairs are distinct. Euler began their study.

His thirty-six officers problem likewise requires an “orthogonal Latin square” in which two sets of attributes, such as ranks and regiments, simultaneously obey the Latin-square rules.

Consider the solution for 5×5, represented visually using chess pieces. A 5×5 table can be filled with pieces of five different ranks and five different colours.

A 5×5 table filled with chess pieces of five different ranks and five different colours
A 5×5 table filled with chess pieces of five different ranks and five different colours · Source

Here is the generalization for ranks 1–7, represented by chess pieces, and regiments, represented by colours. Cases 2 and 6 have no solutions.

Generalization of the thirty-six officers puzzle for ranks 1–7, represented by chess pieces, and regiments, represented by colours. Cases 2 and 6 have no solutions.
Generalization of the thirty-six officers puzzle for ranks 1–7, represented by chess pieces, and regiments, represented by colours. Cases 2 and 6 have no solutions. · Source

Jacques Ozanam mentioned squares resembling Latin squares as early as 1725. A collection of mathematical and physical problems gives the following: “Arrange 16 playing cards — the aces, kings, queens and jacks of all four suits — in a square so that every suit and every rank occurs exactly once in each row and column.”

This problem has 6912 solutions. If the same condition is imposed on the diagonals, the number decreases by a factor of 6, to 1152.

In the 1920s–1930s, intensive study of nonassociative algebraic structures led to quasigroup theory, closely connected with Latin squares because there is a one-to-one correspondence between Latin squares and quasigroup Cayley tables.

A new era of the puzzle began in 2016, when researchers at the University of Cambridge arrived at the unexpected idea of making the entries quantum: quantum Latin squares.

Latin squares have extensive applications in algebra, combinatorics, statistics, cryptography, game theory and coding theory. Perhaps their best-known application, however, is sudoku.

Bibliography

  1. Bavrin, I. I.; Fribus, E. A. Historical Problems: A Book for Students. Moscow: Prosveshcheniye, 1994. 128 pp. [In Russian]
  2. Malykh, A. E.; Kalenkova, A. S. “L. Euler’s Investigation of Magic Squares”. In Proceedings of the All-Russian Conference for Young Researchers with International Participation, Mathematics and Interdisciplinary Research — 2016, Perm, 16−19 May 2016. Perm: Perm State National Research University, 2016, pp. 30−34. [In Russian]
  3. Euler L. Recherches sur une nouvelle espece de quarres maqicues. — Verh. Zeeuwsch. Genootsch. Wetensch. Vlissengen., 1782. — Vol. 9. — P. 85–239.
  4. Malykh, A. E. “Euler’s Creation of the Combinatorial Theory of Latin Squares”. Studies in the History of Mathematics. Moscow: Nauka, 1983, vol. XXVII, pp. 102–123. [In Russian]
  5. Tarry G. Le problème des 36 officiers // C.R. Assoc. France Av. Sci. — 1900. — V.29. — N.2. — P. 170–203.
  6. Bose R. C., Nair K. R. On complete sets of Latin squares // Sankhya. — 1941. — V.5. — Part 4. — P. 361–382.