Les deux carrés d’Euler

Deux carrés latins, un carré magique

Trente-six officiers, six régiments, six grades, un officier de chaque grade dans chaque régiment. Euler demande, en 1782, de les ranger en carré de sorte que chaque ligne et chaque colonne contienne un officier de chaque régiment et un de chaque grade. Il n’y parvient pas, se dit convaincu que c’est impossible sans savoir le démontrer, et conjecture qu’il en va de même pour dix, quatorze, dix-huit officiers de côté. Avec neuf ou vingt-cinq officiers, c’est facile. On verra pourquoi six résiste à sa méthode, et comment deux carrés bien choisis en fabriquent un troisième, magique.

La partie I pose les règles et range neuf officiers ; la partie II construit des carrés orthogonaux, borne leur nombre et explique les limites de la construction cyclique ; la partie III transforme deux carrés latins en un carré magique.

Soit $n\geqslant 2$.
Les lignes et les colonnes d’un tableau carré $n\times n$ sont numérotées de $0$ à $n-1$, et les calculs sur les indices et les symboles se font modulo $n$, dans $\mathbb{Z}/n\mathbb{Z}$.
Un carré latin d’ordre $n$ est un tableau $L=\bigl(L(i,j)\bigr)_{0\leqslant i,j<n}$ à valeurs dans $\{0,1,\ldots,n-1\}$ dont chaque ligne et chaque colonne contient chaque symbole exactement une fois.
Deux carrés latins $L$ et $M$ d’ordre $n$ sont orthogonaux si les $n^2$ couples $\bigl(L(i,j),M(i,j)\bigr)$ sont deux à deux distincts : chaque couple de symboles apparaît exactement une fois lorsqu’on superpose les deux carrés.
Euler écrivait le premier carré en lettres latines et le second en lettres grecques ; la superposition de deux carrés latins orthogonaux s’appelle depuis un carré gréco-latin.
Ranger $n^2$ officiers de $n$ régiments et de $n$ grades comme le demande Euler, c’est exactement construire un carré gréco-latin d’ordre $n$ : le premier carré donne le régiment, le second le grade.

I. Les officiers d’Euler

Vingt-cinq officiers. La couleur du fond donne le régiment, la forme du symbole central le grade. Chaque ligne et chaque colonne contient un officier de chaque régiment et un de chaque grade, et chaque combinaison régiment-grade apparaît exactement une fois. Le fond suit le carré latin $i+2j$ et le symbole central le carré latin $i+3j$, modulo $5$ : ce sont les deux carrés de la question 9, et ils ont une vertu de plus, que l’on découvrira.

1. Pour $n=3$, écrire les tableaux $L(i,j)=i+j$ et $M(i,j)=i+2j$ (modulo $3$).
Vérifier que ce sont deux carrés latins orthogonaux, et ranger neuf officiers de trois régiments et de trois grades.

2. Montrer qu’il n’existe pas deux carrés latins orthogonaux d’ordre $2$.

3. Soient $L$ et $M$ deux carrés latins orthogonaux d’ordre $n$ et $\sigma$ une permutation de $\{0,\ldots,n-1\}$.
Montrer que $\sigma\circ M$ est un carré latin orthogonal à $L$.
En déduire que, quitte à renommer les symboles, on peut supposer que la première ligne de chacun des deux carrés est $(0,1,\ldots,n-1)$.

II. Combien de carrés orthogonaux ?

Pour $k\in\{1,\ldots,n-1\}$, on note $L_k$ le tableau défini par $L_k(i,j)=i+kj$ modulo $n$.
Ainsi $L_1$ est le carré cyclique, et les carrés de la question 1 sont $L_1$ et $L_2$ pour $n=3$.

4. Montrer que $L_k$ est un carré latin si, et seulement si, $k$ est premier avec $n$.
Lorsque $k$ et $l$ sont premiers avec $n$, montrer que $L_k$ et $L_l$ sont orthogonaux si, et seulement si, $l-k$ est premier avec $n$.
En déduire deux carrés latins orthogonaux pour tout $n$ impair, et $p-1$ carrés latins deux à deux orthogonaux lorsque $n=p$ est premier.

5. Montrer qu’une famille de carrés latins d’ordre $n$ deux à deux orthogonaux compte au plus $n-1$ éléments.

6. Une transversale d’un carré latin $L$ est un ensemble de $n$ cases, une par ligne et une par colonne, dans lesquelles $L$ prend $n$ valeurs distinctes.
Montrer que si $M$ est orthogonal à $L$, alors, pour chaque symbole $s$, les cases où $M$ vaut $s$ forment une transversale de $L$.
Montrer que le carré cyclique $L_1$ n’a aucune transversale lorsque $n$ est pair.
En déduire que, pour $n$ pair, aucun carré latin n’est orthogonal à $L_1$ : la méthode de la question 1 ne rangera jamais trente-six officiers.

Euler l’avait vu : son carré cyclique ne trouve de compagnon que pour $n$ impair. Il conjectura que pour $n=6,10,14,\ldots$ aucun carré latin, cyclique ou non, n’en trouve. Il avait raison pour six et tort pour tous les autres. Mais deux carrés orthogonaux ne servent pas qu’à ranger des officiers.

III. Deux carrés pour un carré magique

Un carré magique d’ordre $n$ est un tableau $n\times n$ contenant chaque entier de $1$ à $n^2$ exactement une fois, dont toutes les lignes, toutes les colonnes et les deux diagonales ont la même somme.
Un carré latin est diagonal si sa diagonale principale, formée des cases $(i,i)$, et sa diagonale secondaire, formée des cases $(i,n-1-i)$, contiennent elles aussi chaque symbole exactement une fois.

Les résultats de la partie II peuvent être admis pour traiter cette partie.

7. Montrer que la somme commune des lignes d’un carré magique d’ordre $n$ vaut $n(n^2+1)/2$.

8. Soient $L$ et $M$ deux carrés latins orthogonaux d’ordre $n$.
On pose
$$C(i,j)=n\,L(i,j)+M(i,j)+1 .$$Montrer que $C$ contient chaque entier de $1$ à $n^2$ exactement une fois et que chacune de ses lignes et de ses colonnes a pour somme $n(n^2+1)/2$.
Montrer que si, de plus, sur chacune des deux diagonales, les symboles de $L$ ont pour somme $n(n-1)/2$ et ceux de $M$ également, alors $C$ est un carré magique.
C’est le cas en particulier lorsque $L$ et $M$ sont diagonaux.

9. On suppose $n$ premier avec $6$.
Montrer que $L_2$ et $L_3$ sont deux carrés latins diagonaux orthogonaux.
En déduire un carré magique d’ordre $n$, et l’écrire pour $n=5$.

10. Le Lo Shu, carré magique chinois vieux de plus de deux mille ans, est
$$\begin{pmatrix}4&9&2\\3&5&7\\8&1&6\end{pmatrix}.$$Montrer qu’il s’écrit $3L+M+1$ avec $L$ et $M$ deux carrés latins orthogonaux d’ordre $3$, que l’on déterminera.
Montrer qu’il n’existe aucun carré latin diagonal d’ordre $3$, et vérifier que le critère de la question 8 s’applique néanmoins.
Généraliser cette construction pour obtenir un carré magique de tout ordre impair.

Une constante bien choisie vaut une permutation : c’est le secret du Lo Shu.