Lycée Jules Michelet (Montauban) – Permutations et dénombrement

Le premier stage Hippocampe de l’année 2015-2016 a permis aux 1ère S du lycée Jules Michelet de découvrir la recherche pendant 3 jours – les 2, 3 et 4 novembre. Après de longs trajets en bus, ils ont été accueilli à l’institut de mathématiques où on leur a présenté leur thème de recherche : les permutations et le dénombrement.

Quelles sont ces permutations ?

Tout d’abord, qu’est-ce qu’une permutation ? C’est un mot qui exprime l’idée d’un réarrangement de plusieurs objets. La photo sur le côté montre une permutation des chiffres de 1 à 5 et une permutation des lettres de HIPPOCAMPE (il y a une petite ambiguité du fait que certaines lettres apparaissent plusieurs fois mais les flèches lèvent l’ambiguité). On est habitué à croiser des permutations : dans les carrés magiques, les carrés latins, les sudokus, au Scrabble, quand on change de place en classe ou dans le bus, … Sait-on cependant tout sur elles ?

Il est certain qu’après 3 jours de stages, les élèves du lycée Jules Michelet en savent plus qu’avant leur arrivée à l’université. Ils ont présenté aux membres de l’institut de mathématiques des posters sur les sujets suivants :

• les dérangements (des permutations qui bougent tous les éléments),
• un système générateur de toutes les permutations,
• un puzzle avec des billes,
• des liens entre permutations et arithmétique,
• le profil des permutations (les cycles qui apparaissent dans une permutation),
• le temps moyen de retour suite à l’itération d’une permutation et
• le temps maximal pour ranger les objets après l’itération d’une permutation.

Pour vous amuser, voilà pour finir un problème qui utilise les permutations. Le professeur de mathématiques de la classe de 1ère S du lycée Jules Michelet fait une proposition à ses élèves pour supprimer le cours de mathématiques juste avant les vacances. Là voici : les 34 élèves sont dans une salle, dans la salle d’à côté, il y a 34 casiers, contenant chacun le nom d’un élève de la classe (chaque nom revient exactement une fois bien sûr), à côté, il y a une troisième salle. À tour de rôle, les élèves vont aller dans la salle aux casiers et ouvrir un par un les 17 casiers. Si l’élève trouve son nom parmi les 17 casiers, il referme les casiers sans les modifier, il va dans la troisième salle. Sinon, le cours aura lieu. À la fin, si tous les élèves sont dans la troisième salle (c’est-à-dire qu’ils ont trouvé leur nom en ouvrant 17 casiers), le cours est supprimé ! En réfléchissant un petit peu, vous aurez l’impression qu’il y a une chance sur 2^34 de supprimer le cours (soit 0,000000006% environ), ce qui est très peu… Mais en utilisant les permutations et en réfléchissant encore plus, vous arriverez à plus de 30% de chance de faire annuler le cours. À vous de jouer !