Carré gréco-latin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Carré gréco-latin d'ordre 5

Un carré gréco-latin est un tableau carré de n lignes et n colonnes remplies avec n2 paires distinctes, et où chaque ligne et chaque colonne ne contient qu'un seul exemplaire. Il s'agit de la superposition de deux carrés latins orthogonaux. Si les deux carrés latins n'étaient pas orthogonaux, alors une paire pourrait apparaître plus d'une fois. On dit aussi carré bilatin.

Le nom « gréco-latin » vient du fait que l'on utilisait souvent une paire composée de lettres provenant de l'alphabet grec et latin. Mais aujourd'hui on privilégie le nom « carrés latins orthogonaux » mais ce nom fait penser à deux carrés (deux tableaux) séparés au lieu d'un seul, ce qui engendrait des confusions. D'ailleurs, il est très confus de parler de par exemple « deux » carrés latins orthogonaux : s'agit-il d'un seul tableau qui contient deux carrés latins qui sont orthogonaux ? Ou s'agit-il de deux tableaux qui chacun contient deux carrés latins qui sont orthogonaux ?

Exemples[modifier | modifier le code]

Carrés latins orthogonaux[modifier | modifier le code]

Soient deux carrés latins

 
A_1 = 
\begin{bmatrix} 
 A & C & B & D \\
 D & B & C & A \\
 C & A & D & B \\
 B & D & A & C \\
\end{bmatrix}
\quad \quad
A_2 = 
\begin{bmatrix}
 1 & 4 & 3 & 2 \\
 3 & 2 & 1 & 4 \\
 2 & 3 & 4 & 1 \\
 4 & 1 & 2 & 3 \\
\end{bmatrix}

Si A est le carré A_1 ou A_2, A[i,j] correspond à l'élément en ligne i, colonne j de A. La combinaison des carrés, A_1 + A_2 est définie par : l'élément en ligne i et colonne j de A_1 + A_2 est la paire (A_1[i,j],A_2[i,j]).

Les deux carrés latins A_1 et A_2 sont orthogonaux si chaque paire du carré A_1 + A_2 n'apparaît qu'une seule fois.

La combinaison de deux carrés latins orthogonaux donne un carré gréco-latin (ici d'ordre 4 pour A_1 + A_2) :

A_1 + A_2 = 
\begin{bmatrix}
 A,1 & C,4 & B,3 & D,2 \\
 D,3 & B,2 & C,1 & A,4 \\
 C,2 & A,3 & D,4 & B,1 \\
 B,4 & D,1 & A,2 & C,3 \\
\end{bmatrix}

Deux carrés latins non-orthogonaux[modifier | modifier le code]

Maintenant, nous utilisons un autre carré latin pour le second élément de la paire :

A_2' = 
\begin{bmatrix}
 1 & 2 & 3 & 4 \\
 4 & 1 & 2 & 3 \\
 3 & 4 & 1 & 2 \\
 2 & 3 & 4 & 1 \\
\end{bmatrix}

La combinaison avec le carré précédent ne donne pas un carré gréco-latin :

A_1 + A'_2 = 
\begin{bmatrix}
 A,1 & C,2 & B,3 & D,4 \\
 D,4 & B,1 & C,2 & A,3 \\
 C,3 & {\color{Red}A,4} & D,1 & B,2 \\
 B,2 & D,3 & {\color{Red}A,4} & C,1 \\
\end{bmatrix}

On remarque en effet que la paire A,4 apparaît deux fois (et que la paire D,2 est absente). Les carrés latins A_1 et A'_2 ne sont pas orthogonaux et ne peuvent pas former un carré gréco-latin.

Analyses et démonstrations[modifier | modifier le code]

Le problème des officiers[modifier | modifier le code]

Problème des 36 officiers : un carré gréco-latin d'ordre 6 est impossible à résoudre

En 1782, le mathématicien suisse Leonhard Euler imagine le problème mathématique suivant : on considère six régiments différents, chaque régiment possédant six officiers de grades distincts. On se demande maintenant comment placer les 36 officiers dans une grille de 6x6, à raison d'un officier par case, de telle manière que chaque ligne et chaque colonne contienne tous les grades et tous les régiments.

Il s'agit d'un carré gréco-latin d'ordre 6 (un carré latin pour les régiments, un carré grec pour les grades), problème dont la résolution est impossible. Euler l'avait déjà pressenti à l'époque, sans toutefois donner une démonstration formelle à sa conjecture. Il dira :

Or, après toutes les peines qu’on s’est données pour résoudre ce problème, on a été obligé de reconnaître qu’un tel arrangement est absolument impossible, quoiqu’on ne puisse pas en donner de démonstration rigoureuse.

En 1901, le français Gaston Tarry démontre formellement l'impossibilité du résultat grâce à une recherche exhaustive des cas et par croisement des résultats.

Extension à d'autres ordres[modifier | modifier le code]

En 1958, Bose (en), Parker (en) et Shrikhande (en) ont démontré l'existence de carrés gréco-latins pour tous les ordres, sauf pour l'ordre 2 et l'ordre 6 (la démonstration de ce dernier ayant déjà été faite par Tarry).

Lien avec les carrés magiques[modifier | modifier le code]

Le carré gréco-latin formé par la combinaison de deux carrés latins orthogonaux, tous deux représentés par des nombres de 0 à n-1, peut être vu comme la représentation en base n d'un carré magique. Autrement dit, la paire de nombres (a_{i,j}, b_{i,j}) à l'indice (i,j) peut être vue en base 10 comme le nombre c_{i,j} = a_{i,j}.n^1 + b_{i,j}.n^0. La matrice formée en faisant ce changement de base sur un carré gréco-latin est un carré magique. Cette méthode est très pratique pour créer des carrés magiques, difficiles à générer automatiquement pour un ordre n quelconque.

Articles connexes[modifier | modifier le code]