Voir la source de Carré gréco-latin

[[Image:Greco-latin.png|vignette|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 ''n''{{2}} [[Couple (mathématiques)|couples]] de {{lnobr|Produit cartésien|''L'' × ''G''}}, 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é latin|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 [[alphabet]]s [[Alphabet grec|grec]] et [[Alphabet latin|latin]].

== Exemples ==
[[Fichier:GrecoLatinSquare-Order4.svg|vignette|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'' = {α, β, γ, δ} :
<center><math>
\begin{bmatrix}
A&B&C&D\\
B&A&D&C\\
C&D&A&B\\
D&C&B&A\\
\end{bmatrix}
\quad \quad
\begin{bmatrix}
\alpha&\gamma&\delta&\beta\\
\beta&\delta&\gamma&\alpha\\
\gamma&\alpha&\beta&\delta\\
\delta&\beta&\alpha&\gamma
\end{bmatrix}.
</math></center>
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 :

<center><math>
\begin{bmatrix} 
\alpha&\beta&\gamma&\delta\\
\gamma&\delta&\alpha&\beta\\
\beta&\gamma&\delta&\alpha\\
\delta&\alpha&\beta&\gamma\\
\end{bmatrix}.
</math></center>

Il n'est plus orthogonal au premier, c'est-à-dire que leur superposition ne donne pas un carré gréco-latin :
<center><math>
\begin{bmatrix} 
A\alpha&{\color{Blue}B\beta}&C\gamma&{\color{Orange}D\delta}\\
B\gamma&{\color{Red}A\delta}&D\alpha&{\color{Green}C\beta}\\
{\color{Green}C\beta}&D\gamma&{\color{Red}A\delta}&B\alpha\\
{\color{Orange}D\delta}&C\alpha&{\color{Blue}B\beta}&A\gamma\\
\end{bmatrix}.
</math></center>

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

== Histoire ==

=== Prémices ===
<!--antérieurs : cf. KS, note p. 3-->
Une édition posthume ([[1725]]) des ''Recreations<!--Sic : sans accents, cf. http://www-cs-faculty.stanford.edu/~uno/err4f0.textxt--> mathematiques et physiques'' de [[Jacques Ozanam]] propose (vol. 4, {{p.|434}}) de construire un carré gréco-latin d'ordre 4, dans un [[Casse-tête numériques et logiques|casse-tête]] formulé en termes de [[Carte à jouer|cartes à jouer]]<ref>{{en}} [[Donald Knuth]], ''[[The Art of Computer Programming]]'', vol. 4A, {{p.|3}}.</ref> : le problème est de prendre tous les [[As (carte à jouer)|as]], [[Roi (carte à jouer)|rois]], [[Dame (carte à jouer)|dames]] et [[Valet (carte à jouer)|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 [[Enseigne (carte à jouer)|enseignes]] ([[Trèfle (carte à jouer)|trèfle {{ctrèfle}}]], [[Carreau (carte à jouer)|carreau {{ccarreau}}]], [[Cœur (carte à jouer)|cœur {{ccœur}}]], [[Pique (carte à jouer)|pique {{cpique}}]])
et les quatre valeurs. Il y a plusieurs solutions.

=== Les travaux d'Euler et ses deux conjectures ===
[[Image:Euler 36.svg|vignette|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 [[entier naturel|entiers strictement positifs]]<ref>L. Euler, ''Recherches sur une nouvelle espèce de quarrés magiques'', [https://scholarlycommons.pacific.edu/cgi/viewcontent.cgi?article=1529&context=euler-works E530], présenté à l'[[Académie russe des beaux-arts|Académie de Saint-Pétersbourg]] le 8 mars 1779. Fait remarquable, cet article d'Euler est écrit en français, et est le seul publié dans un journal [[néerlandais]] (en 1782).</ref>. Il produit des méthodes pour en construire si ''n'' est [[Parité (arithmétique)|impair]] ou [[multiple (mathématiques)|multiple]] de 4. Il reste donc à traiter le cas où ''n'' est [[Congruence sur les entiers|congru à 2 modulo 4]]. Il remarque<ref>Euler, {{op. cit.}}, § 17.</ref> 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 » :
{{Citation bloc|<!--NE PAS "RECTIFIER" LA TYPO, conforme à l'original de E530-->36 Officiers de six différens grades et tirès de six Régimens différens, qu'il s'agissoit de ranger dans un quarré, de manière que sur chaque ligne tant horizontale que verticale il se trouva six Officiers tant de différens caractères que de Régimens différens<ref name=EulerIntro>Euler, {{op. cit.}}, § 1.</ref>.}}
Il [[conjecture]] que ce problème n'a pas de solution :
{{Citation bloc|<!--NE PAS "RECTIFIER" LA TYPO, conforme à l'original de E530-->Or, après toutes les peines qu'on s'est donné 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émonstration rigoureuse<ref name=EulerIntro/>.
}}
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'' :
{{Citation bloc|1=<!--NE PAS "RECTIFIER" LA TYPO, conforme à l'original de E530-->J'ai examiné par cette méthode un très grand nombre de quarrés […] et je n'ai pas hésité d'en conclure, qu'on ne sçauroit produire aucun quarré complet de 36 carrés, et que la même impossibilité s'étende aux cas de n=10, n=14 et en général à tous les nombres impairement pairs<ref>Euler, {{op. cit.}}, § 144.</ref>.}}

=== 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 (astronome)|Thomas Clausen]] parvient, selon toute vraisemblance<ref name=KS/>, à 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<ref name=KS/>, est due au Français [[Gaston Tarry]], en 1901<ref>{{Article|auteur=G. Tarry|titre=Le problème des 36 officiers (I)|revue=Comptes rendus de l'Association française pour l'avancement des sciences|vol=1|p.=122-123|année=1900}} et {{Article|auteur=G. Tarry|titre=(II)|revue=C. R. Assoc. Franç. Av. Sci.|vol=2|p.=170-203|année=1901}}.</ref>.

En [[1959]]-[[1960]], [[Raj Chandra Bose|Bose]], {{Lien|langue=en|trad=E. T. Parker|fr=Ernest Parker|texte=Parker}} et [[Sharadchandra Shankar Shrikhande|Shrikhande]] infirment complètement la seconde<ref name=KS>{{Article|lang=en|titre=Graeco-Latin Squares and a Mistaken Conjecture of Euler|auteur=Dominic Klyve|auteur2=Lee Stemkoski|revue={{Lien|College Mathematics Journal}}|vol=37|numéro=1|année=2006|p.=2-15|url=http://www.math.uci.edu/~brusso/klyveStemkoskiCollMathJ2006.pdf}}.</ref> : 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]] <math>n=p^\alpha</math>, le corps fini <math>\mathbb{F}_n</math> permet de construire <math>n-1</math> carré latins d'ordre <math>n</math> deux à deux orthogonaux, donc <math>\binom{n-1}{2}</math> carrés gréco-latins<ref>{{Ouvrage|auteur1=André Warusfel|titre=Structures algébriques finies|éditeur=HACHETTE UNIVERSITE|année=1971|passage=242-243}}</ref>.

Ces carrés sont les [[Table de Cayley|tables de Cayley]] des lois <math>*</math> définies sur <math>\mathbb{F}_n</math> par <math>x*y=ax+y</math> pour <math>a</math> décrivant les éléments non nuls de <math>\mathbb{F}_q</math>.

Par exemple, pour <math>n=3</math>, les deux carrés obtenus sont <math>\begin{matrix} 0 & 1 & 2 \\ 1 & 2 & 0\\ 2& 0 & 1\end{matrix}</math> (pour  <math>a=1</math>) et <math>\begin{matrix} 0 & 1 & 2 \\ 2 & 0 & 1\\ 1& 2 & 0\end{matrix}</math> (pour <math>a=2</math>), conduisant au carré gréco-latin <math>\begin{matrix} (0,0) & (1,1) & (2,2) \\ (1,2) & (2,0) & (0,1)\\ (2,1)& (0,2) & (1,0)\end{matrix}</math>. Des exemples pour <math>n=4</math> et <math>n=9</math> sont donnés dans <ref name=":1">{{Ouvrage|auteur1=Jacques Bouteloup|titre=Carrés magiques, carrés latins et eulériens|éditeur=Éditions du Choix|année=1991|passage=20, 109-116}}</ref>.

== Application aux plans finis ==
L'existence d'un [[Géométrie finie|plan fini]] (affine ou projectif) d'ordre <math>n</math> (dont les droites comportent <math>n</math> points) équivaut à l’existence de <math>n-1</math> carrés latins d'ordre <math>n</math> deux à deux orthogonaux<ref name=":0" />.

Ce résultat, couplé avec la propriété précédente, permet de montrer qu'il existe des plans finis pour tout ordre <math>n</math> qui est un nombre primaire<ref name=":0" />.

Inversement, l'inexistence de carré gréco-latin d'ordre 6 montre l'inexistence de plan fini d'ordre 6<ref name=":0" />.

== Application aux carrés magiques ==
Tout carré eulérien donne naissance à un [[Carré magique (mathématiques)|carré semi-magique]], dont les lignes et les colonnes ont même somme<ref name=":1" />. Si l'on se ramène à <math>G=L=\{1,\cdots,n\}</math>, et si l'on remplace le couple <math>(x,y)</math> du carré eulérien par l'entier <math>(x-1)n+y</math>, on on obtient un [[Carré magique (mathématiques)|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 <math>\begin{matrix} 1 & 2 & 3 &4 \\ 3 & 4 & 1 & 2\\ 4 & 3 & 2 & 1\\ 2& 1 & 4 & 3\end{matrix}</math> et <math>\begin{matrix} 1 & 2 & 3 &4 \\ 4 & 3 & 2 & 1\\ 2& 1 & 4 & 3\\ 3 & 4 & 1 & 2\end{matrix}</math> fournit le carré magique <math>\begin{matrix} 1 & 6 & 1 &16 \\ 12 & 15 & 2 & 5\\ 14& 9 & 8 & 3\\ 7 & 4 & 13 & 10\end{matrix}</math><ref name=":0">{{Article|auteur1=Olivier Méjane|titre=Plans finis et carrés latin|périodique=Quadrature|numéro=120|pages=25-30|date=avril-mai-juin 2021|lire en ligne=https://www.quadrature.info/produit/numero-120/|accès url=payant}}</ref>. 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 [[Plan d'expériences|plans d'expériences]] et les planifications de tournois.

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Bibliographie ===
* {{Article| titre=Et le problème des 36 officiers d'Euler devint quantique| auteur1=Sean Bailly| périodique=[[Pour la science]]| numéro=540| date=octobre 2022| pages=68-71}}

=== Articles connexes ===
* [[Sudoku]]

{{Portail|mathématiques}}

[[Catégorie:Permutation]]
[[Catégorie:Mathématiques récréatives]]
[[Catégorie:Plan d'expériences]]
[[Catégorie:Carré|Greco latin]]