Carré gréco-latin
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 n2 couples de 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é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 modifier
Deux carrés latins orthogonaux modifier
Considérons les deux carrés latins d'ordre 4 suivants, sur les ensembles L = {A, B, C, D} et G = {α, β, γ, δ} :
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 modifier
Remplaçons le second des deux carrés latins ci-dessus par le suivant :
Il n'est plus orthogonal au premier, c'est-à-dire que leur superposition ne donne pas un carré gréco-latin :
On remarque en effet que quatre couples apparaissent deux fois (et que quatre sont absents).
Histoire modifier
Prémices modifier
Une édition posthume (1725) des Recreations 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 formulé en termes de cartes à jouer[1] : 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 ♣, carreau ♦, cœur ♥, pique ♠) et les quatre valeurs. Il y a plusieurs solutions.
Les travaux d'Euler et ses deux conjectures modifier
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[2]. 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[3] 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 » :
« 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[4]. »
Il conjecture que ce problème n'a pas de solution :
« 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[4]. »
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 :
« 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[5]. »
Première conjecture confirmée et seconde réfutée modifier
En 1842, grâce à une recherche exhaustive des cas et par croisement des résultats, le Danois Thomas Clausen parvient, selon toute vraisemblance[6], à 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[6], est due au Français Gaston Tarry, en 1901[7].
En 1959-1960, Bose, Parker (en) et Shrikhande infirment complètement la seconde[6] : 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.
Applications modifier
- 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.
- Certains carrés gréco-latins permettent de construire certains carrés magiques. Plus précisément : dans un carré gréco-latin d'ordre n sur G = L = {0, 1, … , n – 1}, en remplaçant chaque couple (x, y) par le nombre nx + y, on obtient un carré constitué des nombres de 0 à n2 – 1, ayant même somme sur chaque ligne et chaque colonne (mais pas toujours sur les deux diagonales, et inversement un carré magique normal d'ordre n peut ne pas être issu d'un carré gréco-latin).
Notes et références modifier
- (en) Donald Knuth, The Art of Computer Programming, vol. 4A, p. 3.
- L. Euler, Recherches sur une nouvelle espèce de quarrés magiques, E530, présenté à l'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).
- Euler, op. cit., § 17.
- Euler, op. cit., § 1.
- Euler, op. cit., § 144.
- (en) Dominic Klyve et Lee Stemkoski, « Graeco-Latin Squares and a Mistaken Conjecture of Euler », College Mathematics Journal (en), vol. 37, no 1, , p. 2-15 (lire en ligne).
- G. Tarry, « Le problème des 36 officiers (I) », Comptes rendus de l'Association française pour l'avancement des sciences, vol. 1, , p. 122-123 et G. Tarry, « (II) », C. R. Assoc. Franç. Av. Sci., vol. 2, , p. 170-203.
Voir aussi modifier
Bibliographie modifier
- Sean Bailly, « Et le problème des 36 officiers d'Euler devint quantique », Pour la science, no 540, , p. 68-71
