J'ai récemment eu le plaisir d'assister à la projection du film The Imitation Game, consacré à Alan Turing. Ce génie considérait le décryptage du code des machines Enigma comme un immense puzzle logique. Passionné depuis toujours par ce type d'énigmes – celles qui suscitent les questions : « Manque-t-il une pièce ? » et « Par où commencer ? » –, je vous propose un exemple classique que je connais depuis longtemps.
L'énigme des moines
Dans un monastère où les moines ont fait vœu de silence, l'abbé annonce un jour qu'un certain nombre de moines ont contracté une maladie se manifestant par des taches sur le visage. Il leur demande de quitter le monastère pour se faire soigner. Sans miroirs ni communication autorisée, les moines ne peuvent pas savoir s'ils sont atteints. Ils se voient chaque matin lors des prières. Le lendemain de l'annonce, tous sont présents ; de même les jours suivants jusqu'au neuvième inclus. Le dixième jour, à la prière matinale, les moines infectés ont disparu. Combien étaient-ils ?
Ne cherchez pas la réponse ici tout de suite : réfléchissez-y ! Pour la résoudre, mettez-vous dans la peau d'un moine et supposez un raisonnement logique parfait de la part de tous.
Lors d'un cours de mathématiques de vacances organisé par la Plateforme Wiskunde Nederland en août dernier – une formation de deux jours pour enseignants du secondaire, vivement recommandée ! –, j'ai rencontré Hans van Ditmarsch. Ce logicien m'a fait découvrir son livre captivant : 100 prisonniers et une ampoule, rempli d'énigmes similaires, dont celle qui donne son titre à l'ouvrage.
Cent prisonniers et une ampoule
Cent détenus, réunis à la cafétéria de la prison, apprennent qu'ils seront isolés en cellule et interrogés un par un dans une pièce dotée d'une lampe à interrupteur. La lampe, éteinte initialement, est leur seul moyen de communication. L'ordre des interrogatoires est aléatoire, sans durée fixe, et un même prisonnier peut être rappelé plusieurs fois. Lors d'un interrogatoire, un détenu peut : ne rien faire, allumer/éteindre la lampe, ou déclarer que tous ont été interrogés au moins une fois. Si vrai, tous sont libérés ; sinon, exécutés. Peuvent-ils, avant l'isolement, élaborer un protocole garantissant leur libération ?
La réponse est oui. Connaissez-vous la stratégie ? Partagez-la en commentaire !
Hans van Ditmarsch et Barteld Kooi, Cent prisonniers et une ampoule, Éditions Epsilon, Utrecht (2013), 105 pages.
Ce livre propose neuf énigmes logiques, dont celles ci-dessus, divisées en sous-problèmes avec solutions détaillées. Le lecteur travaille activement, découvre variantes et origines – comme celle des 100 prisonniers, apparue en ligne en 2002. Les solutions partielles figurent au dos. Caractéristique commune : raisonner sur ce que les autres savent, ou « méta-connaissance ».
Une traduction anglaise paraîtra bientôt. Un ouvrage surprenant !
Densité de formules : Θ Ο Ο Ο Ο
Difficulté : Θ Θ Ο Ο
Note : Θ Θ Ο
La série Biographie Scientifique de Veen Media propose récemment des biographies incontournables pour tout mathématicien.
Le premier porte sur John von Neumann (1903-1957), géant des mathématiques du XXe siècle. Anecdote célèbre : le problème de la mouche et des trains.
Deux trains se croisent à 50 km/h, distants de 100 km. Une mouche décolle à 75 km/h du premier vers le second, fait demi-tour à chaque rencontre, jusqu'à la collision. Distance parcourue par la mouche ? Von Neumann répondit instantanément 75 km, en sommant la série infinie. Chemin élégant : temps jusqu'à collision (1 heure), vitesse × temps = 75 km. Von Neumann excella au projet Manhattan, en théorie des jeux et avec l'ENIAC. Citations mémorables :
« Jeune homme, en mathématiques, tu ne comprends rien. On s'y habitue juste. »
« Si les gens ne croient pas que les mathématiques sont simples, c'est parce qu'ils ne réalisent pas à quel point la vie est compliquée. »
« Il y a probablement un Dieu. Beaucoup de choses s'expliquent plus facilement avec qu sans. »
Giorgio Israel et Ana Millán Gasca, Von Neumann. La riche vie d'un mille-pattes mathématicien, Veen Media (2014), 160 pages.
Biographie approfondie d'un prodige clé du XXe siècle. Lecture exigeante, anecdotes limitées ; complétez par Le dilemme du prisonnier de William Poundstone (1992). Illustrations superbes.
Densité de formules : Ο Ο Ο Ο Ο
Difficulté : Ο Ο Ο Ο
Note : Θ Ο Ο
Jean Le Rond d'Alembert (1717-1783), encyclopédiste avec Diderot (Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers).
Connu des étudiants pour le critère de convergence d'Alembert et sa tentative (incomplète) de prouver le théorème fondamental de l'algèbre : tout polynôme non constant à coefficients complexes admet au moins un zéro complexe. En mécanique, le principe d'Alembert.
Pierre Crépel et al., D'Alembert. Mathématicien doué des Lumières, Veen Media (2014), 160 pages.
Époque riche avec Euler et Bernoulli. Ce livre éclaire ses facettes : équation des cordes vibrantes (première aux dérivées partielles), controverses... Illustrations magnifiques, frise chronologique.
Densité de formules : Θ Θ Ο Ο Ο
Difficulté : Θ Θ Ο Ο
Note : Θ Θ Ο
Nouveauté :
Julian Havil, John Napier. Vie, logarithmes et héritage, Princeton University Press (2014), 279 pages.
John Napier (1550-1617), inventeur du logarithme népérien. Polyvalent : analyse apocalyptique anti-catholique, puis Mirifici Logarithmorum Canonis Descriptio (1614) pour tables de logarithmes et Os de Napier (calculateur analogique). Ouvrage passionnant ; sautez le chapitre biblique. Julian Havil, habitué de ce blog.
Densité de formules : Θ Θ Θ Ο Ο
Difficulté : Θ Θ Ο Ο
Note : Θ Θ Ο
Solutions des énigmes
L'énigme des moines
[Énoncé répété pour rappel]
Jour 0 (annonce). Si 1 moine malade, il voit tous sains et part immédiatement. Il y en a donc plus.
Jour 1. Si 2 malades, chacun voit 1 autre et attend son départ. Il reste : donc 2, ils partent.
Jour 2. Si 3, chacun voit 2 et attend leur départ au jour 1. Ils restent : donc 3, partent.
Par induction, au jour 9, si 10 malades, chacun voit 9 autres. Ils attendent leur départ progressif ; absence au jour 10 confirme : 10 malades partent.
Réponse : 10 moines infectés.
[Énoncé répété]
Les prisonniers désignent un Compteur.
Pour les autres :
Pour le Compteur :
Chaque non-Compteur allume une fois (première éteinte). Le Compteur compte 99 allumages = 99 prisonniers + lui = 100. Note : avec 1 interrogatoire/jour, ~28,5 ans en moyenne !
[]