Περὶ εἶδους νέου quadratorum magicorum
A la fin du XVIIIe siècle, le génial Leonhard Euler s'intéresse au problème des 36 officiers, le genre de problème que l'on donne à quelqu'un pour s'en débarrasser plusieurs heures, le temps qu'il comprenne que c'est en fait insoluble.
Le soucis, c'est que quand on donne un problème de ce type à des mathématiciens, ça ne les occupe pas simplement quelques heures, mais au moins plusieurs siècles...
Le problème des 36 officiers
Pour assurer son prestige et sa renommée, le roi de votre choix se doit d'organiser un défilé militaire d'envergure comptant 36 officiers, de 6 grades et de 6 régiments différents de sorte que chaque association grade/régiment soit présente. Les officiers défileront en formant un carré 6x6, tout en veillant à ce que, sur chaque ligne et chaque colonne, on ne retrouve ni deux régiments identiques, ni deux grades identiques.
Facile, il suffit de faire ça :
Six grades : rois, dames, tour, fou, cavalier, pion
Six régiments : rose, blanc, noir, bleu, vert, orange
Bien sûr, cette solution est fausse, sinon, ça serait trop facile : la cinquième colonne compte deux fous et la dernière colonne possède deux tours.
Pour résumer, le problème des 36 officiers consiste à remplir un carré 6x6 à l'aide de 36 officiers de différents grades et régiments en respectant les trois contraintes :
- Chaque ligne et colonne doit comporter les 6 régiments différents
- Chaque ligne et colonne doit comporter les 6 grades différents
- Chacun des 36 officiers doit apparaître une unique fois dans le carré.
En général, remplir deux conditions sur trois n'est pas particulièrement difficile. Mais dès qu'il s'agit de remplir les trois conditions à la fois, les choses se compliquent toujours. Après de nombreux essais infructueux, Euler conjecturera dans son article de 1779 "Recherches sur une nouvelle espèce de quarrés magiques" que le problème est tout simplement impossible, mais sans réussir à savoir exactement pourquoi.
Euler prendra l'habitude de noter les 6 régiments par les lettres latines a, b, c, d, e et f, et les 6 grades par les lettres grecques α, β, γ, δ, ε et ζ. Un carré respectant les 3 conditions du problème sera donc baptisé "carré gréco-latin".
Bien sûr, le problème peut se généraliser à 49, 64, 81, 100 ou n'importe quel nombre carré d'officiers, et c'est à ce moment là que la question devient intéressante. Pour quelle valeur de n existe-t-il des carrés gréco-latins d'ordre n, c'est à dire, de dimension n×n ? Euler se risquera à conjecturer que le problème des n² officiers est impossibles dès que n est de la forme 4n+2 ("impairement pair", c'est à dire 2, 6, 10, 14 ...). Il a eu tord.
Le problème des 4 officiers
Simplifions le problème, et rangeons 4 officiers de 2 grades et de 2 régiments dans un carré 2×2. Ainsi simplifié, le problème devient trivialement impossible : à partir du moment où deux officiers de même régiment sont placés, il ne reste plus de place libre pour les deux autres :
Où placer le deuxième régiment ?...
Bref : le problème des 2² officiers est impossible.
Le problème des 9 officiers
Simplifions un peu moins : 9 officiers de 3 grades et de 3 régiments.
Avant de chercher à construire un carré gréco-latin, on peut commencer par simplement construire des carrés latins : un carré latin est une grille de dimension n×n contenant n symboles différents où chaque ligne et chaque colonne ne possède jamais deux symboles identiques (une version simplifiée d'un sudoku, en fait...).
Des carrés latins de taille 3×3, on peut en construire 12 différents. Si on s'impose un ordre précis pour la première ligne, on se reistreint à seulement deux carrés latins différents :
Les deux carrés latins d'ordre 3, produit à partir des symboles 0, 1 et 2
Par le plus grand des hasards, il se trouve que ces deux carrés latins sont "orthogonaux", c'est à dire que si on réunit les deux carrés en un seul, on obtient les 9 couples possibles de chiffres parmi 0, 1 et 2 :
L'unique carré gréco-latin d'ordre 3
Du coup, il suffit d'associer le premier chiffre de chaque couple au régiment, et le deuxième au grade, et on obtient enfin une solution valable pour un problème d'officier :
La solution au problème des 9 officiers
Bref : le problème des 3² officiers est possible.
Le problème des 25 officiers
Place au problème des 25 officiers : 5 grades et 5 régiments. Maintenant que l'on a une méthode, cela devrait fonctionner. Il faut donc commencer par fabriquer tous les carrés latins disponibles de taille 5×5. On en compte en tout 161280 (A002860), et 924 (A173103) lorsque la première ligne est fixée. Hors de question de tous les construire, voyons une méthode qui permet d'en générer quelques uns.
Une façon plutôt simple de construire un carré latin est de se fixer une constante entière C entre 1 et 4 ; chaque ligne du carré s'obtient à partir de la précédente en ajoutant la constante que l'on a choisi. Si les résultats dépassent 5, on soustrait 5 aux résultats (calculs "modulo 5") :
Quatre carrés latins d'ordre 5 construits par la méthode de la constante
Il n'y a plus qu'à prendre deux de ces carrés latins pour fabriquer un carré gréco-latin, et donc, une solution au problème des 25 officiers.
Une solution au problème des 25 officiers.
Cette méthode ne portant à ma connaissance aucun nom, je me permets de la baptiser "méthode de la constante".
A noter que cette méthode permet de répondre au super problème des 25 officiers où il faut placer 25 officiers de 5 grades, 5 régiments, chacun accompagné d'un instrument de musique parmi 5 et d'un animal parmi 5 dans un carré 5×5, de façon à ce que, lorsque l'on choisit deux officiers parmi les 25, exactement une des propriétés suivante est vérifiée :
- ils partagent une même ligne ou une même colonne
- ils partagent un même grade
- ils partagent un même régiment
- ils partagent un même instrument
- ils partagent un même animal.
Pour cela, il suffit de fabriquer un carré gréco-super-latin à partir des 4 carrés latins, où chacun de ces carrés latins donnera l'une des caractéristique :
J'ai déjà pris mon billet pour assister à ce défilé militaire où un cavalier rose joue du clavier en présence d'un lapin.
Bref : le problème des 5² officiers est possible.
Le problème des 16 et 64 officiers
Revenons au problème des 16 officiers (4 régiments de 4 grades) pour voir ce qui pose problème avec la méthode des 25, en commençant par générer des carrés latins par la méthode de la constante :
Trois Deux carrés latins d'ordre 4 construits par la méthode de la constante
Première désillusion : la méthode de la constante ne génère pas forcément des carrés latins... En fait, on obtient un carré latin par cette méthode dans le seul cas où la constante C et la taille de la grille n sont premiers entre eux. Avec C=2 et n=4, forcément, ça ne fonctionne pas.
Pas grave, il reste deux carrés latins, avec lesquels on peut tenter de construire un carré gréco-latin :
Carré non gréco-latin d'ordre 4.
Deuxième désillusion : certains couples se retrouvent deux fois dans la grille, ce n'est donc pas un carré gréco-latin.
En fait, si on appelle C et C' les constantes des deux grilles que l'on assemble, il est nécéssaire que C'–C soit premier avec n pour que les deux carrés latins forment un carré gréco-latin. Bref, la méthode ne fonctionne pas du tout pour n=4, puisque, avec C=3 et C'=1, la différence C'–C=2 n'est pas première avec 4.
On peut aussi vérifier que cette méthode ne donnera rien pour n=6, puisque les seules constantes C acceptables sont C=1 et C'=5 or, C'–C = 4 n'est pas premier avec 6. Cela ne nous aide pas pour résoudre le problème original des 36 officiers.
La méthode se généralise cependant parfaitement à tous les entiers impairs strictement supérieurs à 3 (5, 7, 9, 11, ...) . Dans ce cas, les constantes C=1 et C = n – 1 donnent deux carrés latins parfaitement orthogonaux.
Fort heureusement, la méthode de la constante peut être généralisée pour construire des carrés grécos-latins, mais seulement dans le cas où l'ordre n est l'ordre d'un corps fini, c'est à dire, un nombre de la forme pk, où p est un nombre premier. Puisque n=4=2², le problème des 16 officiers peut tout de même être résolu. Je ne vais pas détailler la méthode (puisqu'elle n'est intéressante que pour les ordres n=4 et n=8), mais elle donne ceci :
Défilé militaire coréen
De même, puisque 8=23, le problème des 64 officiers peut lui aussi être résolu de cette façon :
Défilé militaire goth
Bref : les problèmes des 4² et 8² officiers sont possibles.
Le problème des 144 officiers
Plus compliqué : le problème des 144 officiers, avec 12 régiments de 12 grades.
Avec n=12, la méthode de la constante est vouée à l'échec. Les constantes acceptables (premières avec 12) sont C=1, 5, 7 et 11. Dans tous les cas, les différences C'-C donneront quelque chose de pair, donc, non premier avec 12.
De manière plus générale, dès que n est un nombre pair, les constantes acceptables seront impaires, si bien que les différences C-C' seront paires, ie, non premier avec n. Bref : si n est pair, pas de méthode de la constante.
La méthode des corps finis ne fonctionne pas non plus, puisque 12 n'est pas la puissance d'un nombre premier.
Heureusement, 12 = 3 × 4, et on a vu que des carrés grécos-latins existent pour n=3 et n=4. Si on pouvait réussir à rassembler ces petits carrés gréco-latins en un seul grand carré gréco-latins, ça serait chouette... Et on peut le faire, grâce à la méthode du produit cartésien !
Prenons pour ça deux carrés latins U et V respectivement d'ordre 4 et 3. On peut alors construire un carré latin UV d'ordre 12 en concaténant à chaque symbole de U le carré latin V. Le résultat, c'est un carré latin d'ordre 12 où les symboles sont la concaténation des symboles de U et de V.
Carré latin d'ordre 12, obtenu comme produit cartésien de deux carrés latins d'ordre 4 et 3.
Ce qui est intéressant avec cette méthode, c'est que lorsque des carrés latins U et U' (respectivement V et V') sont orthogonaux, alors le produit cartésien UV sera orthogonal à U'V'. En l'appliquant aux carrés gréco-latins d'ordre 3 et 4 vu un peu plus haut, on obtient alors quelque chose comme ça :
Carré gréco-latin d'ordre 12, obtenu comme produit cartésien de deux carrés gréco-latin d'ordre 4 et 3.
Je suis prêt à louer les droits cette image à tout escroc astrologue qui en fera la demande
Bref, le problème des 12² officiers est possible.
Le problème des 36, 100, 484 ou 1764 officiers
Résumons :
- Problème des 1² officier : trivial
- Problème des 2² officiers : impossible
- Problème des 3² officiers : possible (méthode de la constante)
- Problème des 4² officiers : possible (méthode des corps finis)
- Problème des 5² officiers : possible (méthode de la constante)
- Problème des 6² officiers : ???
- Problème des 7² officiers : possible (méthode de la constante)
- Problème des 8² officiers : possible (méthode des corps finis)
- Problème des 9² officiers : possible (méthode de la constante, méthode des corps finis ou méthode du produit cartésien)
- Problème des 10² officiers : ???
- Problème des 11² officiers : possible (méthode de la constante)
- Problème des 12² officiers : possible (méthode du produit cartésien)
- Problème des 13² officiers : possible (méthode de la constante)
- Problème des 14² officiers : ???
- Etc.
De manière plus générale, la méthode de la constante permet d'obtenir tous les carrés gréco-latins d'ordre impair (sauf n=1 et n=3), la méthode des corps finis permet d'obtenir les ordres 4 et 8, et la méthode du produit cartésien permet d'obtenir les ordres multiples de 4 supérieurs. Il manque donc les ordres n=4k+2, qu'aucune méthode présentée ne permet de construire. C'est d'ailleurs pour cela que Euler a conjecturé que l'ensemble de ces carrés gréco-latins était impossible.
Mais en 1901, Gaston Terry prend son courage à deux mains et passe en revue les 13 433 520 carrés latins d'ordre 6 pour voir si certains d'entre eux pourraient former un carré gréco-latin. Je vous rassure : il commence par réduire de 13 433 520 à 17 le nombre de cas possibles.
Résultat des courses : non ! Le problème des 36 officiers d'Euler est enfin prouvé comme étant impossible.
En 1942, Henry Mann montre qu'il existe deux types de carrés latins : ceux que l'on peut associer à un groupe, et les autres. Jusque là, toutes les méthodes présentées construisent des carrés latins de la première catégorie, basées sur des groupe. Il démontre alors que si un carré gréco-latin d'ordre n=4k+2 existe, il ne sera pas construit à partir d'un carré latin basé sur un groupe.
La conséquence, c'est que si ces carrés grécos-latins introuvables existent réellement, alors il faudra découvrir des méthodes de constructions complètement inédites.
En 1959, S.S. Shrikhande et R.C Bose publient un petit papier indiquant qu'ils ont réussi à démontrer l'existence de carrés gréco-latins d'ordre 4k+2 pour tout k ⩾ 5. Pour montrer qu'ils ne plaisantent pas, ils accompagnent le papier du premier carré gréco-latin d'ordre 22 (que le courage m'empêche de reproduire ici).
Parallèlement à ça, E. T. Parker publie le premier carré gréco-latin d'ordre 10. Pour le trouver, il a laissé tourner pendant une heure le UNIVAC 1206, un super-calculateur militaire (de 1959) :
Le premier carré gréco-latin d'ordre 10, découvert par E.T. Parker
En 1960, Parker, Shrikhande et Bose s'associent pour enfin montrer que, pour tout k ⩾ 2, il existe bien un carré latin d'ordre 4k+2. Ils se permettent même de dénombrer le nombre de carrés latins mutellement orthogonaux en fonction de n.
Bref : le problème des n² officiers est possible pour tout n, sauf pour n=2 et n=6 !
Sources :
Recherches sur une nouvelle espèce de quarrés magiques, Leonhard Euler
Le problème des 36 officiers, Gaston Tarry
Greco-Latin Squares and a Mistaken Conjecture of Euler, Dominic Klyve & Lee Stemkoski
Carrés grécos-latins, Jean-Paul Davalan - pour générer des carrés grécos-latins d'ordre pk.
/http%3A%2F%2Fstorage.canalblog.com%2F53%2F54%2F210892%2F92246854_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F42%2F63%2F210892%2F38514689_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F03%2F84%2F210892%2F101783289_o.png)
/http%3A%2F%2Fstorage.canalblog.com%2F17%2F55%2F210892%2F98494979_o.jpg)