samedi 25 août 2007
Carrés gréco-latins
Par Didier Müller, samedi 25 août 2007 à 17:12 - Théorèmes et démonstrations
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. Euler donna le nom "gréco-latin" à ces carrés car il utilisait souvent une paire composée de lettres provenant des alphabets grec et latin.
Carré gréco-latin d'ordre 5
En 1782, Leonhard Euler imagine le problème mathématique suivant. On considère six régiments différents, chaque régiment possède 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 sur chaque ligne et chaque colonne contiennent 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é latin 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.
Euler crut pouvoir généraliser son constat en conjecturant qu’il n’y avait pas de telles dispositions pour 4k + 2 avec k ≥ 1. En 1959, avec l’aide d’ordinateurs, deux mathématiciens américains, Bose et Shrikhande, trouvèrent des contre-exemples à la conjecture d’Euler. La même année, Parker trouva un contre-exemple d’ordre dix. En 1960, Parker, Bose et Shrikhande démontrèrent que la conjecture d’Euler était fausse pour tous les n ≥ 10.
A voir
lu 17302 fois