COMBINATOIRE ANALYSE

Existence et construction de modèles

Un certain nombre de modèles ont été tout particulièrement étudiés, c'est le cas des carrés latins, sans doute parce qu'un mathématicien célèbre comme Euler fit à leur sujet une conjecture malheureuse et qu'il fallut attendre 177 ans pour prouver son inexactitude. En introduisant des notions comme celle d'orthogonalité, on a pu établir des liens étroits entre les carrés latins et certaines géométries finies, ou encore avec d'autres modèles comme les blocs incomplets équilibrés, ce qui a permis souvent d'étudier le même objet avec des optiques différentes.

Un carré latin d'ordre n est une matrice carrée A = (a_ij), _1≤i, _j≤n dont les coefficients a_ij sont 1, 2, ..., n et dans laquelle chaque entier k apparaît une et une seule fois dans chaque ligne et chaque colonne (1 ≤ k ≤ n). Il existe naturellement un carré latin d'ordre n pour tout n ≥ 1. Par exemple, la table de multiplication d'un groupe fini d'ordre n est un carré latin. En fait, un carré latin peut être considéré comme la table de multiplication d'un système algébrique dont la loi est seulement supposée simplifiable. Soit l_n le nombre de carrés latins d'ordre n ; jusqu'à ce jour, on a pu déterminer les valeurs exactes de l_n pour 1 ≤ n ≤ 8. Pour calculer l₈, on a dû recourir à l'usage d'ordinateurs, mais même avec ceux-ci, en l'absence de nouvelles méthodes, on ne peut espérer aller bien loin dans cette direction. En revanche, l'orthogonalité a permis de trouver des résultats plus intéressants. Soit A = (a_ij) et B = (b_ij), deux carrés latins d'ordre n ; on dit qu'ils sont orthogonaux si tous les n² couples (a_ij, b_ij), où i, j = 1, 2, ..., n, sont distincts. Par exemple, les deux carrés latins d'ordre 4 indiqués ci-dessous sont orthogonaux :

Soit C la matrice ayant pour coefficients les couples (a_ij, b_ij) ; dans C tous les n² couples (1, 1), (1, 2), ..., (n, n) apparaissent une et une seule fois. Dans l'exemple ci-dessus, on obtient la matrice :

On dit parfois que C est un carré gréco-latin. On s'est alors posé le problème de savoir s'il existe une paire de carrés latins orthogonaux pour tout n. Avec un peu de patience, il est facile de construire de telles paires pour n = 3, 4 et 5 et même pour des entiers supérieurs à 6. C'est Euler qui en 1782 formula ce problème en termes récréatifs. Supposons, en effet, que, dans six régiments donnés, on relève, dans chacun, six officiers, tous de grades différents, et qu'on veuille disposer ces trente-six officiers dans un carré de six cases de côté, de sorte que dans chaque ligne et dans chaque colonne il y ait un représentant de chaque régiment et un représentant de chaque grade. Une telle disposition est-elle possible ? La réponse est non, et ce n'est qu'en 1900 que Tarry démontra cette impossibilité par une analyse très systématique de tous les cas possibles. Le problème des trente-six officiers était donc impossible. Si l'on numérote de 1 à 6 les six régiments et les six grades, chacun des officiers peut être repéré par un couple (i, j), où 1 ≤ i, j ≤ 6 ; le premier indice i désigne son régiment et le second j son grade. Vouloir un représentant de chaque régiment (resp. grade) dans chaque ligne et chaque colonne et vouloir quand même disposer les trente-six officiers, c'est chercher à satisfaire aux trois exigences :

– Les premiers indices i forment un carré latin ;

– Les seconds indices j forment un carré latin ;

– Les deux carrés latins ainsi formés sont orthogonaux.

L'impossibilité du problème des trente-six officiers démontrée par Tarry équivaut donc à l'impossibilité de construire deux carrés latins d'ordre 6 orthogonaux. Euler n'ayant pu réussir[...]