Histoire et cultureNotion · Glossaire
problème des 36 officiers
Le problème des 36 officiers demande si l'on peut placer 36 officiers, issus de 6 régiments et de 6 grades avec un officier pour chaque couple régiment-grade, dans une grille 6 × 6 afin que chaque ligne et chaque colonne contienne exactement une fois chaque régiment et chaque grade. Il équivaut à chercher deux carrés latins orthogonaux d'ordre 6, autrement dit un carré gréco-latin d'ordre 6, et une telle disposition est impossible.
Sommaire
Ce que vous allez apprendre
- Reformuler la contrainte des 36 officiers dans une grille 6 × 6.
- Relier le problème aux carrés latins orthogonaux.
- Tester une construction et repérer un couple répété.
- Distinguer l'échec d'un essai de la preuve exhaustive de l'impossibilité.
En clair
Imaginez 36 officiers à placer dans une grille de 6 lignes et 6 colonnes. Chacun porte deux étiquettes : l'une indique son régiment, de A à F, l'autre son grade, de 1 à 6. Dans chaque ligne comme dans chaque colonne, les six régiments doivent apparaître une seule fois, et les six grades aussi.
La difficulté vient du respect simultané de ces deux répartitions. Chaque contrainte se réalise séparément avec un carré latin, mais aucune paire de carrés latins d'ordre 6 ne satisfait leur combinaison.
Définition
Le problème des 36 officiers demande de remplir les 36 cases d'un carré 6 × 6 avec les couples formés par 6 régiments et 6 grades. Chaque couple doit représenter un officier distinct. Toute ligne et toute colonne doivent contenir chacun des six régiments exactement une fois, ainsi que chacun des six grades exactement une fois.
Si l'on inscrit seulement les régiments, la grille obtenue est un carré latin d'ordre 6. Les grades forment un second carré latin du même ordre. Les deux carrés sont dits orthogonaux lorsque leur superposition fait apparaître chacun des 36 couples régiment-grade une fois et une seule. Cette superposition est aussi appelée carré gréco-latin.
Pour l'ordre 6, un tel couple de carrés orthogonaux n'existe pas. Euler formula cette impossibilité comme une conjecture en 1782, puis Gaston Tarry la confirma en 1900 par une vérification exhaustive de tous les cas.
Un exemple, pas à pas
Essayons une construction régulière. Les lignes et les colonnes sont numérotées de 0 à 5. Les régiments A à F correspondent aux nombres 0 à 5, et les grades restent numérotés de 1 à 6.
1. Pour une case située à la ligne r et à la colonne c, le numéro du régiment R et le grade G sont choisis par les deux règles suivantes :
Le reste modulo 6 est toujours pris entre 0 et 5.
2. Sur chaque ligne et chaque colonne, R parcourt 0 à 5 une fois. Il en va de même pour G après le décalage de 1 : les deux grilles sont donc bien des carrés latins.
3. À la case de coordonnées (0, 0), les règles donnent R = 0 et G = 1, soit le couple A1. À la case (3, 3), elles donnent encore R = 0 et G = 1.
Le contrôle échoue : A1 apparaît deux fois, alors que chacun des 36 couples devrait apparaître exactement une fois. Cette construction ne résout donc pas le problème ; la répétition surlignée rend l'échec directement vérifiable.
En pratique
Pour tester une disposition proposée, commencez par chaque ligne puis chaque colonne. Comptez les régiments et les grades séparément : une valeur répétée ou absente suffit à rejeter la disposition.
Si ces deux contrôles réussissent, examinez ensuite les couples régiment-grade dans les 36 cases. Le carré gréco-latin est la bonne représentation lorsque chaque couple doit être unique ; un seul carré latin suffit si une seule catégorie doit être répartie.
Pour l'ordre 6, chercher une nouvelle permutation ne peut pas mener à une solution complète. Le résultat de Tarry permet de conclure à l'impossibilité, plutôt que de confondre un long échec de recherche avec une simple difficulté de construction.
À ne pas confondre
Carré latin et carré gréco-latin. Un carré latin contrôle une seule famille de six symboles. Le carré gréco-latin superpose deux carrés latins et exige en plus l'unicité de leurs 36 couples. Deux grilles correctes séparément peuvent donc échouer ensemble.
Conjecture et preuve. En 1782, Euler conjecture l'impossibilité à l'ordre 6. La conclusion devient établie lorsque Tarry vérifie exhaustivement tous les cas en 1900 ; multiplier les essais infructueux ne suffit pas à produire cette preuve.
Officiers distincts et étiquettes distinctes. Les 36 officiers sont distingués par leur couple régiment-grade. Répéter un régiment dans une ligne viole déjà une contrainte ; répéter un couple viole aussi l'orthogonalité, même si les deux grilles restent latines séparément.
Limites et pièges
Contrôle incomplet. Voir six régiments et six grades différents dans chaque ligne ne suffit pas. Les colonnes doivent satisfaire exactement les mêmes contraintes ; sinon, la disposition est rejetée avant même le test des couples.
Deux carrés latins ne sont pas nécessairement orthogonaux. Dans l'exemple, chaque grille passe ses contrôles de lignes et de colonnes, mais le couple A1 occupe deux cases. Il faut donc vérifier les 36 superpositions.
Échec d'une méthode et impossibilité générale. Le doublon A1 invalide seulement la construction essayée. Pour conclure qu'aucun arrangement d'ordre 6 n'existe, il faut le résultat exhaustif obtenu par Tarry en 1900.
Le nombre 36 est structurel. Il vient des 6 régiments multipliés par les 6 grades. Modifier ce nombre change l'ordre du problème ; l'impossibilité affirmée ici concerne précisément le carré 6 × 6.
Pour aller plus loin
Le carré latin isole la première structure du problème : une occurrence de chaque symbole par ligne et par colonne.
La fiche Euler Leonhard replace l'auteur de la conjecture dans l'histoire des mathématiques.
L'analyse combinatoire donne le cadre général des problèmes où il faut compter ou organiser des configurations sous contraintes.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres