Le dénombrement 167
Le principe de l’analyse combinatoire est bien mis en évidence par un maître en la
matière, le Révérend Thomas Kirkman, dans la deuxième moitié du xix
e siècle, alors
qu’elle était surtout liée aux mathématiques récréatives. Ses contributions nombreuses et originales à la géométrie discrète, à la théorie des groupes et à l’analyse
combinatoire ne lui permirent cependant pas d’obtenir un poste à l’université. Le
casse-tête qui consolida sa réputation de mathématicien du non-sens est celui qui
lui valut la célébrité. En 1850, Kirkman présenta le « problème des 15 pensionnaires ». De jeunes pensionnaires se rendent à l’église en formant 5 rangs de 3
jeunes filles chaque jour de la semaine. Si vous êtes fatigué des Sudoku, essayez
ce problème. Il faut établir un planning journalier pour éviter que deux élèves ne
soient ensemble plus d’une fois par semaine. Utilisant minuscules et majuscules
à dessein, les prénoms des jeunes filles sont les suivants : armelle, béatrice, clémence, dorothée, emma, francine, grâce, Agnès, Bérénice, Charlotte, Danielle,
Edith, Florence, Gaëlle et Victoire. On les désigne respectivement par a, b, c, d, e,
f, g, A, B, C, D, E, F, G et V.
Il existe en réalité sept solutions différentes au problème de Kirkman, et celle que
nous donnerons est dite « cyclique » : elle est générée par « permutation » des jeunes
filles. C’est là que se justifie le choix de les désigner par des minuscules et des
majuscules.
Lundi
Mardi
Mercredi
Jeudi
Vendredi
Samedi Dimanche
a A V b B V c C V d D V e E V f F V g G V
b E D c F E d G F e A G f B A g C B a D C
c B G d C A e D B f E C g F D a G E b A F
d f g e g a f a b g b c a c d b d e c e f
e F C f G D g A E a B F b C G c D A d E B
La solution est cyclique car chaque jour, le calendrier des promenades est modifié
comme suit : a est remplacée par b, b par c, et ainsi de suite jusqu’à g remplacée par
a. De même pour les pensionnaires désignées par des majuscules : A est remplacée
par B, B est remplacée par C et ainsi de suite, mais Victoire n’est jamais remplacée.
La raison cachée du choix de cette notation est que les rangs correspondent aux lignes
dans le plan de Fano (voir p. 115). Le problème de Kirkman n’est pas un simple
divertissement ; il figure parmi les grands problèmes mathématiques classiques.
l’idée clé
Combien
de combinaisons ?
Le principe de l’analyse combinatoire est bien mis en évidence par un maître en la
matière, le Révérend Thomas Kirkman, dans la deuxième moitié du xix
e siècle, alors
qu’elle était surtout liée aux mathématiques récréatives. Ses contributions nombreuses et originales à la géométrie discrète, à la théorie des groupes et à l’analyse
combinatoire ne lui permirent cependant pas d’obtenir un poste à l’université. Le
casse-tête qui consolida sa réputation de mathématicien du non-sens est celui qui
lui valut la célébrité. En 1850, Kirkman présenta le « problème des 15 pensionnaires ». De jeunes pensionnaires se rendent à l’église en formant 5 rangs de 3
jeunes filles chaque jour de la semaine. Si vous êtes fatigué des Sudoku, essayez
ce problème. Il faut établir un planning journalier pour éviter que deux élèves ne
soient ensemble plus d’une fois par semaine. Utilisant minuscules et majuscules
à dessein, les prénoms des jeunes filles sont les suivants : armelle, béatrice, clémence, dorothée, emma, francine, grâce, Agnès, Bérénice, Charlotte, Danielle,
Edith, Florence, Gaëlle et Victoire. On les désigne respectivement par a, b, c, d, e,
f, g, A, B, C, D, E, F, G et V.
Il existe en réalité sept solutions différentes au problème de Kirkman, et celle que
nous donnerons est dite « cyclique » : elle est générée par « permutation » des jeunes
filles. C’est là que se justifie le choix de les désigner par des minuscules et des
majuscules.
Lundi
Mardi
Mercredi
Jeudi
Vendredi
Samedi Dimanche
a A V b B V c C V d D V e E V f F V g G V
b E D c F E d G F e A G f B A g C B a D C
c B G d C A e D B f E C g F D a G E b A F
d f g e g a f a b g b c a c d b d e c e f
e F C f G D g A E a B F b C G c D A d E B
La solution est cyclique car chaque jour, le calendrier des promenades est modifié
comme suit : a est remplacée par b, b par c, et ainsi de suite jusqu’à g remplacée par
a. De même pour les pensionnaires désignées par des majuscules : A est remplacée
par B, B est remplacée par C et ainsi de suite, mais Victoire n’est jamais remplacée.
La raison cachée du choix de cette notation est que les rangs correspondent aux lignes
dans le plan de Fano (voir p. 115). Le problème de Kirkman n’est pas un simple
divertissement ; il figure parmi les grands problèmes mathématiques classiques.
l’idée clé
Combien
de combinaisons ?