problème de Kirkman

Imaginez quinze cartes portant les lettres A à O. Chaque jour, vous les distribuez en cinq paquets de trois, puis vous recommencez le lendemain avec de nouveaux paquets. Au bout de sept jours, chaque lettre doit avoir côtoyé une fois, et une seule, chacune des quatorze autres.

La difficulté n’est donc pas seulement de former des groupes sans doublon dans une journée. Il faut coordonner toute la semaine pour qu’aucune paire ne se répète et qu’aucune ne manque.

Le problème de Kirkman, ou problème des quinze demoiselles, porte sur un ensemble de quinze éléments. Il faut construire sept partitions successives de cet ensemble. Chaque partition, appelée ici un jour, contient cinq triplets disjoints : chaque élément apparaît donc exactement une fois par jour. Sur l’ensemble des sept jours, toute paire d’éléments doit appartenir à un unique triplet.

Cette organisation relève des designs combinatoires et des systèmes de triples. Les quinze éléments déterminent $\left(\genfrac{}{}{0px}{}{15}{2}\right)=105\backslash binom\{15\}\{2\}=105$ paires. Un triplet contient trois paires, si bien qu’il faut 105 ÷ 3 = 35 triplets. Les sept partitions en fournissent précisément 7 × 5 = 35. Ce comptage est nécessaire, mais il faut encore vérifier qu’aucune paire n’est répétée.

Thomas Penyngton Kirkman a énoncé, résolu et publié ce problème en 1850. Sa solution précède la généralisation formulée par Steiner sous le nom de système de triples de Steiner. Le problème particulier impose en plus que les triplets se rangent en journées complètes.

Les participantes sont A à O.
Données : 15 lettres ; 7 jours ; 5 groupes par jour ; 3 lettres par groupe ; chaque paire doit apparaître une fois.

1. Comptons les contraintes. Les 15 lettres forment $\left(\genfrac{}{}{0px}{}{15}{2}\right)=105\backslash binom\{15\}\{2\}=105$ paires. Un triplet en réunit trois, donc 35 triplets sont nécessaires. Le calendrier en compte exactement 7 × 5 = 35.

2. Utilisons cette répartition :
Jour 1 : ABC, DHL, EJO, FKM, GIN.
Jour 2 : ADE, BHJ, CMN, FIO, GKL.
Jour 3 : AFG, BIK, CLO, DJN, EHM.
Jour 4 : AHI, BLN, CEF, DKO, GJM.
Jour 5 : AJK, BMO, CDG, EIL, FHN.
Jour 6 : ALM, BDF, CIJ, EKN, GHO.
Jour 7 : ANO, BEG, CHK, DIM, FJL.

3. Chaque ligne contient une fois les lettres A à O : les cinq groupes d’un même jour sont donc disjoints. Pour A, les partenaires successifs sont B et C, D et E, F et G, H et I, J et K, L et M, puis N et O. Les quatorze autres lettres sont toutes rencontrées une fois.

4. Pour le contrôle complet, relevez les trois paires de chacun des 35 triplets. Si aucune ne se répète, les 105 paires relevées sont nécessairement toutes les paires possibles. La répartition satisfait alors le problème.

Pour chercher une solution à la main, quinze cartes marquées A à O rendent les contraintes visibles. Après chaque journée, on barre les trois paires contenues dans chaque paquet. Une paire déjà barrée signale immédiatement qu’il faut modifier la répartition.

Pour contrôler un calendrier proposé, deux tests sont nécessaires. Chaque journée doit employer les quinze lettres une seule fois, puis la liste globale doit contenir les 105 paires sans répétition. Le seul comptage des 35 groupes ne suffit pas.

Pour étudier la structure plutôt que l’histoire des quinze demoiselles, on remplace les participantes par des éléments abstraits. On conserve alors les deux règles observables : des triplets disjoints dans chaque partition et une occurrence unique de chaque paire sur l’ensemble des partitions.

Un système de triples de Steiner. Il exige que chaque paire appartienne à un unique triplet, mais ses triplets ne sont pas nécessairement présentés comme des journées qui partitionnent tous les éléments. Dans le problème de Kirkman, chaque jour doit former cinq groupes disjoints couvrant les quinze participantes.

Une simple partition en triplets. Une partition ne contrôle qu’une journée : chaque participante y apparaît une fois. Le problème de Kirkman contrôle aussi les rencontres entre journées. Deux groupes valides séparément échouent dès qu’ils reproduisent une même paire.

Des journées correctes ne garantissent pas une semaine correcte. Cinq triplets peuvent couvrir les quinze éléments sans répétition le même jour, tout en reproduisant une paire déjà rencontrée. Il faut donc contrôler les paires sur les sept jours.

Le bon total ne suffit pas. Trente-cinq triplets contiennent bien 105 occurrences de paires. Si une paire apparaît deux fois, une autre manque nécessairement. Le contrôle doit porter sur l’unicité des paires, pas seulement sur leur nombre.

Les sept jours ne sont pas un choix arbitraire. Chaque participante rencontre deux nouvelles personnes par jour. Pour rencontrer les quatorze autres exactement une fois, il faut donc 14 ÷ 2 = 7 jours.

Une généralisation doit passer deux tests de divisibilité. Avec un nombre d’éléments noté n, former seulement des triplets exige que n soit divisible par 3. Rencontrer deux nouveaux partenaires par journée exige aussi que n − 1 soit pair. Ces conditions de comptage ne construisent pas, à elles seules, une solution.

La fiche Steiner Jacob situe le mathématicien associé à la généralisation en systèmes de triples mentionnée dans l’histoire du problème.