Problème des 15 écolières
En mathématiques récréatives, le problème des 15 écolières est un problème formulé par Thomas Kirkman en 1850. Il s'énonce comme suit :
- « Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast. »
- « Quinze écolières se promènent sept jours de suite par groupes de trois ; on demande de les grouper jour par jour de telle sorte que deux écolières ne se promènent jamais deux fois ensemble. »
Historique
Le problème a été posé en 1850 par Kirkman dans le journal de mathématiques récréatives The Lady's and Gentleman's Diary[1] et des solutions ont été données par Arthur Cayley[2] et par Kirkman lui-même[3]. Il y a eu ultérieurement un différend entre Kirkman et le mathématicien James Joseph Sylvester, qui a affirmé avoir posé lui aussi le problème. La devinette est apparue dans divers livres de mathématiques récréatives au tournant du Modèle:S- par Lucas[4], Rouse Ball[5], Ahrens[6] et Dudeney[7].
Solution
Si on numérote les écolières de 0 à 14, une solution est donnée par l'arrangement suivant [8] :
Dim Lun Mar Mer Jeu Ven Sam 0, 5, 10 0, 1, 4 1, 2, 5 4, 5, 8 2, 4, 10 4, 6, 12 10, 12, 3 1, 6, 11 2, 3, 6 3, 4, 7 6, 7, 10 3, 5, 11 5, 7, 13 11, 13, 4 2, 7, 12 7, 8, 11 8, 9, 12 11, 12, 0 6, 8, 14 8, 10, 1 14, 1, 7 3, 8, 13 9, 10, 13 10, 11, 14 13, 14, 2 7, 9, 0 9, 11, 2 0, 2, 8 4, 9, 14 12, 14, 5 13, 0, 6 1, 3, 9 12, 13, 1 14, 0, 3 5, 6, 9
Ce problème est un cas particulier de système de Steiner S(t, k, n), un ensemble à Modèle:Mvar éléments muni d'une famille de sous-ensembles à Modèle:Mvar éléments (les blocs), de sorte que chaque sous-ensemble à Modèle:Mvar éléments est contenu dans exactement un bloc (un tel système est aussi appelé un plan en blocs de paramètre t(n, k, 1)). Dans le problème des écolières avec Modèle:Mvar écolières, on a un système triple de Steiner S(2, 3, Modèle:Mvar). Dans le cas Modèle:Mvar = 15, il existe en tout sept possibilités de répartir les écolières selon les conditions. Celles-ci ont été publiées en 1862/1863 par Wesley Woolhouse dans le même magazine où Kirkman avait posé le problème[9]Modèle:,[10]Modèle:,[11]. Deux de ces solutions peuvent être visualisées comme relations entre un tétraèdre et ses sommets, arêtes et faces[12].
Extensions
La solution générale de tels problèmes s'est avérée plus difficile qu'on pouvait le penser à l'origine. Des preuves de l'existence d'une solution dans le cas général ont été fournies par Richard M. Wilson et Dwijendra Kumar Ray-Chaudhuri en 1968 [13]; en 2018 une preuve encore plus générale de l'existence de plans en blocs admissibles a été donnée par Peter Keevash[14]. Il n'existe pas de solutions pour tout entier Modèle:Mvar et pour chaque combinaison de paramètres : certaines conditions naturelles de divisibilité doivent être remplies ; par exemple Modèle:Mvar doit être divisible par 3. Cependant, si ces conditions sont remplies, Wilson a prouvé l'existence d'une solution. Le nombre de solutions augmente exponentiellement avec Modèle:Mvar. Avec 19 écolières, il y a déjà plus de onze milliards de possibilités pour les diviser en groupes de trois de sorte que chacune se promène exactement une fois dans un groupe de trois en présence de toutes les autres.
Le problème des écolières de Kirkman a été le début du développement de la théorie des plans en blocs et des designs combinatoires.
Le problème d'Oberwolfach de décomposition d'un graphe complet en copies sans arêtes communes d'un graphe 2-régulier est aussi une généralisation du problème des écolières : le problème de Kirkman est le cas particulier de ce problème où les graphes 2-réguliers consistent en cinq triangles disjoints[15].
Notes et références
Bibliographie
- réimpression Modèle:Ouvrage
- Modèle:Ouvrage
- Modèle:Article
- Modèle:Ouvrage
- Modèle:Article
- Modèle:Article
- Modèle:Ouvrage
- Modèle:Article
- Modèle:Ouvrage
- réimpression Modèle:Ouvrage
Voir aussi
- Le problème des écolières de Kirkman dans l'article sur la géométrie finie.