Carré gréco-latin

Un carré gréco-latin d'ordre 5.

Un carré gréco-latin ou carré eulérien d'ordre n, sur deux ensembles G et L de chacun n symboles, est un tableau carré de n lignes et n colonnes, contenant les nModèle:2 couples de Modèle:Lnobr, et où toute ligne et toute colonne contient exactement une fois chaque élément de L (en première position dans l'un des n couples) et chaque élément de G (en seconde position). Il s'agit de la superposition de deux carrés latins orthogonaux l'un à l'autre. On dit aussi « carré bilatin ».

Le nom « gréco-latin » vient du fait que l'on utilisait souvent pour G et L le début des alphabets grec et latin.

Exemples

Un carré gréco-latin d'ordre 4.

Deux carrés latins orthogonaux

Considérons les deux carrés latins d'ordre 4 suivants, sur les ensembles L = {A, B, C, D} et G = {α, β, γ, δ} :

$\left[\begin{array}{cccc}A& B& C& D\\ B& A& D& C\\ C& D& A& B\\ D& C& B& A\end{array}\right]\left[\begin{array}{cccc}\alpha & \gamma & \delta & \beta \\ \beta & \delta & \gamma & \alpha \\ \gamma & \alpha & \beta & \delta \\ \delta & \beta & \alpha & \gamma \end{array}\right].$

Leur superposition (ci-contre) est un carré gréco-latin car aucun couple de L × G n'est répété (donc chaque couple apparaît une fois et une seule) : on dit que les deux carrés latins sont orthogonaux.

Deux carrés latins non orthogonaux

Remplaçons le second des deux carrés latins ci-dessus par le suivant :

$\left[\begin{array}{cccc}\alpha & \beta & \gamma & \delta \\ \gamma & \delta & \alpha & \beta \\ \beta & \gamma & \delta & \alpha \\ \delta & \alpha & \beta & \gamma \end{array}\right].$

Il n'est plus orthogonal au premier, c'est-à-dire que leur superposition ne donne pas un carré gréco-latin :

$\left[\begin{array}{cccc}A\alpha & B\beta & C\gamma & D\delta \\ B\gamma & A\delta & D\alpha & C\beta \\ C\beta & D\gamma & A\delta & B\alpha \\ D\delta & C\alpha & B\beta & A\gamma \end{array}\right].$

On remarque en effet que quatre couples apparaissent deux fois (et que quatre sont absents).

Histoire

Prémices

Une édition posthume (1725) des Recreations mathematiques et physiques de Jacques Ozanam propose (vol. 4, Modèle:P.) de construire un carré gréco-latin d'ordre 4, dans un casse-tête formulé en termes de cartes à jouer : le problème est de prendre tous les as, rois, dames et valets d'un jeu standard et de les disposer sur une grille 4×4 de telle sorte que chaque ligne et chaque colonne contienne les quatre enseignes ([[Trèfle (carte à jouer)|trèfle Modèle:Ctrèfle]], [[Carreau (carte à jouer)|carreau Modèle:Ccarreau]], [[Cœur (carte à jouer)|cœur Modèle:Ccœur]], [[Pique (carte à jouer)|pique Modèle:Cpique]]) et les quatre valeurs. Il y a plusieurs solutions.

Les travaux d'Euler et ses deux conjectures

Problème des 36 officiers : il n'existe pas de carré gréco-latin d'ordre 6.

En 1779, le mathématicien suisse Leonhard Euler définit et étudie en détail les carrés gréco-latins d'ordre n, sur les alphabets grec et latin puis sur les entiers strictement positifs. Il produit des méthodes pour en construire si n est impair ou multiple de 4. Il reste donc à traiter le cas où n est congru à 2 modulo 4. Il remarque qu'il n'existe pas de carré gréco-latin d'ordre 2 et illustre l'ordre 6 par son « problème des 36 officiers » : Modèle:Citation bloc Il conjecture que ce problème n'a pas de solution : Modèle:Citation bloc et même que plus généralement, pour tout n congru à 2 modulo 4, il n'existe aucun carré gréco-latin d'ordre n : Modèle:Citation bloc

Première conjecture confirmée et seconde réfutée

En 1842, grâce à une recherche exhaustive des cas et par croisement des résultats, le Danois Thomas Clausen parvient, selon toute vraisemblance, à démontrer la première conjecture d'Euler : il n'existe aucun carré gréco-latin d'ordre 6. Mais sa preuve ne nous est pas parvenue. La première preuve publiée, qui suit la même méthode, est due au Français Gaston Tarry, en 1901.

En 1959-1960, Bose, Modèle:Lien et Shrikhande infirment complètement la seconde : hormis les deux exceptions déjà connues (n = 2 et n = 6), il existe des carrés gréco-latins d'ordre n pour tout n ≡ 2 (mod 4) donc finalement : pour tout n.

Construction de carrés gréco-latins à partir de corps finis

Pour tout nombre primaire $n=p^{\alpha }$, le corps fini ${𝔽}_n$ permet de construire $n-1$ carré latins d'ordre $n$ deux à deux orthogonaux, donc $(\genfrac{}{}{0ex}{}{n-1}{2})$ carrés gréco-latins.

Ces carrés sont les tables de Cayley des lois $*$ définies sur ${𝔽}_n$ par $x*y=ax+y$ pour $a$ décrivant les éléments non nuls de ${𝔽}_q$.

Par exemple, pour $n=3$, les deux carrés obtenus sont $\begin{array}{ccc}0& 1& 2\\ 1& 2& 0\\ 2& 0& 1\end{array}$ (pour $a=1$) et $\begin{array}{ccc}0& 1& 2\\ 2& 0& 1\\ 1& 2& 0\end{array}$ (pour $a=2$), conduisant au carré gréco-latin $\begin{array}{ccc}(0,0)& (1,1)& (2,2)\\ (1,2)& (2,0)& (0,1)\\ (2,1)& (0,2)& (1,0)\end{array}$. Des exemples pour $n=4$ et $n=9$ sont donnés dans .

Application aux plans finis

L'existence d'un plan fini (affine ou projectif) d'ordre $n$ (dont les droites comportent $n$ points) équivaut à l’existence de $n-1$ carrés latins d'ordre $n$ deux à deux orthogonaux.

Ce résultat, couplé avec la propriété précédente, permet de montrer qu'il existe des plans finis pour tout ordre $n$ qui est un nombre primaire.

Inversement, l'inexistence de carré gréco-latin d'ordre 6 montre l'inexistence de plan fini d'ordre 6.

Application aux carrés magiques

Tout carré eulérien donne naissance à un carré semi-magique, dont les lignes et les colonnes ont même somme. Si l'on se ramène à $G=L=\{1,\cdots ,n\}$, et si l'on remplace le couple $(x,y)$ du carré eulérien par l'entier $(x-1)n+y$, on on obtient un carré semi-magique, et ce carré est de plus magique si les deux carré latins de départ sont "diagonaux" (i.e. si leurs deux diagonales sont composées d'éléments distincts).

Par exemple, le carré eulérien formé des deux carrés latins diagonaux $\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\\ 4& 3& 2& 1\\ 2& 1& 4& 3\end{array}$ et $\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\\ 2& 1& 4& 3\\ 3& 4& 1& 2\end{array}$ fournit le carré magique $\begin{array}{cccc}1& 6& 1& 16\\ 12& 15& 2& 5\\ 14& 9& 8& 3\\ 7& 4& 13& 10\end{array}$. Cependant on n'obtient pas ainsi tous les carrés magiques.

Autres applications

• Georges Perec a structuré son roman La Vie mode d'emploi (publié en 1978) sur un carré gréco-latin d'ordre 10.
• Les carrés gréco-latins sont utilisés dans les plans d'expériences et les planifications de tournois.

Voir aussi

Bibliographie

• Modèle:Article

Articles connexes

• Sudoku