On m'a posé aujourd'hui l'énigme suivante :
Le cruel Docteur No a capturé 100 mathématiciens pour les soumettre à une épreuve démoniaque. Il a placé (dans un ordre connu de lui seul) le nom de chacun des 100 mathématiciens dans autant de boîtes numérotées de 1 à 100. Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : il empêchera toute communication entre eux et les emmènera, dans un certain ordre, dans la pièce où se trouvent les 100 boîtes. Lorsqu'un mathématicien est dans la pièce, il pourra ouvrir une boîte de son choix pour lire le nom qui y figure, puis, s'il le souhaite, en ouvrir une autre, puis éventuellement une autre, et ainsi de suite jusqu'à 50 boîtes au maximum. (Les boîtes sont, bien entendu, refermées avant le passage du prochain mathématicien, puisque toute communication est interdite après la concertation initiale.) Le but de chaque mathématicien, lorsqu'il passe dans la pièce contenant les boîtes, est d'ouvrir la boîte contenant son nom (parmi les ≤50 boîtes qu'il peut ouvrir). Si chaque mathématicien a réussi à ouvrir la boîte contenant son nom, alors le Docteur No les libérera tous. Si ne serait-ce qu'un seul n'a pas réussi, alors le Docteur No tuera tous les mathématiciens avec ses tortures particulièrement raffinées.
Si chaque mathématicien ouvrait bêtement 50 boîtes au hasard, il aurait une chance sur deux de voir son nom dans l'une d'elles, et la probabilité que tous les mathématiciens réussissent le test (donc soient libérés) serait d'une chance sur 2 puissance 100 (en gros une chance sur un quintillion, ce qui ne pèse pas très lourd). Mais comme ce sont des mathématiciens, ils vont trouver une solution bien plus intelligente.
En fait, ils élaborent une stratégie qui leur permet d'avoir plus de 30% de chances de s'en sortir. Comment font-ils ?
[Ajout () : voir ici.]
Mon propos n'est pas de donner la réponse à cette énigme (qui m'a demandé un bon moment de réflexion, d'ailleurs), je le ferai éventuellement plus tard (mais sans doute quelqu'un se dévouera-t-il dans les commentaires), mais de faire le parallèle avec d'autres. Il y a en effet toutes sortes d'énigmes bien connues dans ce genre, et qui font souvent appel au Docteur No et à nombre variable de mathématiciens.
En voici une autre :
Le cruel Docteur No a capturé 50 mathématiciens pour les soumettre à une épreuve diabolique. Il a créé sur son île une pièce vide à l'exception d'une lampe et d'un interrupteur qui sert à l'allumer ou l'éteindre. Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : il empêchera toute communication entre eux (autre que celle qui va être décrite) et emmènera chaque jour un mathématicien tiré au hasard dans la pièce où se trouve l'interrupteur. La lumière est initialement éteinte. Chaque fois qu'un mathématicien passe dans la pièce, il constate si le précédent avait laissé la lumière allumée ou éteinte (c'est la seule forme de communication possible), et peut lui-même choisir de la laisser dans son état précédent ou de l'allumer ou de l'éteindre. Le but des mathématiciens est de savoir à quel moment tous les mathématiciens sont passés par la pièce : si un mathématicien en acquiert la certitude, il peut l'annoncer au Docteur No. Il est hors de question de se tromper, bien sûr, car cela serait puni de la mort avec des tortures particulièrement raffinées pour tous les mathématiciens ; en revanche, si l'affirmation est juste, tous les mathématiciens sont libérés. Quelle stratégie les mathématiciens peuvent-il élaborer pour être (« presque ») certains, un jour, d'être tous libérés ?
Les chapeaux sont aussi une source populaire d'énigmes de ce style : les deux suivantes peuvent paraître particulièrement surprenantes à première vue, mais sont sans doute plus simples que celles qui précèdent.
Le cruel Docteur No a capturé 20 mathématiciens pour les soumettre à une épreuve pernicieuse. Il a créé des chapeaux de plusieurs couleurs différentes. Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : il empêchera toute communication entre eux (sauf comme on va le dire), puis rangera les mathématiciens en file indienne dans un certain ordre, et mettra sur la tête de chacun un chapeau d'une certaine couleur (les couleurs possibles sont connues à l'avance), de sorte que chaque mathématicien puisse voir les couleurs des chapeaux de tous ceux situés devant lui, mais pas de ceux situés derrière lui ni du sien propre. Dans l'ordre qui leur plaira, les mathématiciens devront annoncer la couleur de leur propre chapeau (c'est la seule forme de communication permise entre eux) ; le Docteur No tolérera un échec (car il faut bien admettre que personne ne peut voir la couleur du chapeau du mathématicien situé tout derrière), mais pas plus : si plus d'un mathématicien s'est trompé en annonçant la couleur de son chapeau, tous seront tués avec des tortures particulièrement raffinées — à l'inverse, si tous ou tous sauf un avaient raison, ils seront libérés. Comment les mathématiciens se tirent-ils de ce mauvais pas (de façon certaine) ?
et
Le cruel Docteur No a capturé trois mathématiciens (il n'est pas en forme, aujourd'hui) pour les soumettre à une épreuve maléfique. Il a créé des chapeaux de deux couleurs différentes (là non plus, il n'est pas en forme). Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : il empêchera toute communication entre eux, puis mettra sur la tête de chacun un chapeau d'une certaine couleur, tirée au hasard parmi les deux couleurs possibles (les deux couleurs possibles sont connues à l'avance), de sorte que chaque mathématicien puisse voir les couleurs des chapeaux des deux autres, mais pas du sien propre. Chaque mathématicien sera ensuite amené devant le Docteur No où il pourra annoncer (sans que les autres l'entendent) quelle était la couleur de son propre chapeau. Si un mathématicien a fait une annonce erronée, le Docteur No les tuera tous avec des tortures particulièrement raffinées ; de même si aucun ne fait d'annonce ; en revanche, si au moins un mathématicien fait une annonce correcte et qu'aucun ne fait d'annonce incorrecte, le Docteur No les libérerera. Comment les mathématiciens font-ils pour avoir trois chances sur quatre d'être libérés ?
La réaction commune, par exemple pour ce dernier problème, est
quelque chose comme c'est impossible : si on ne peut pas voir son
chapeau, on ne peut déduire aucune information en voyant celui des
autres, et comme on ne peut pas communiquer, on ne peut rien
faire
. Pourtant, ces problèmes admettent bien des solutions, pas
spécialement difficiles (et ne nécessitant essentiellement pas de
connaissances mathématiques, comme quoi le Docteur No aurait aussi
bien pu capturer des agents secrets). On pourrait aussi chercher à
généraliser ces problèmes de toutes sortes de façons (que se
passe-t-il, pour le dernier, si on prend plus de trois
mathématiciens ? et pour le deuxième, celui avec l'interrupteur,
quelles stratégies permettent de s'en sortir relativement
rapidement ?).
Le problème suivant a plus d'intérêt théorique que les précédents, mais il est aussi assez pénible à formuler :
Problème des généraux byzantins : Le Docteur No a capturé une dizaine de mathématiciens pour les soumettre à une épreuve byzantine. Il a créé des cellules dans lesquelles la lumière peut être allumée ou éteinte. Après avoir permis aux mathématiciens de se concerter, il va les soumettre à son épreuve dont il leur communique les termes : chacun va être placé dans une cellule, et ils pourront communiquer par des lignes téléphoniques reliant deux cellules quelconques (mais les conversations ne sont que d'une personne à une autre, jamais plus). Le Docteur No va envoyer à chaque mathématicien un message qui peut être soit
les lumières doivent être alluméessoitles lumières doivent être éteintes. Il n'envoie pas forcément le même message à tous les mathématiciens : néanmoins, tous devront faire la même action (tous doivent allumer leur lumière ou tous doivent l'éteindre) ; il n'y a que si tous ont reçu le même message que l'état de la lumière est impératif (autrement dit, si le Docteur No demande à tout le monde d'éteindre sa lumière, alors tout le monde doit l'éteindre ; s'il demande à tout le monde de l'allumer, alors tout le monde doit l'allumer ; s'il envoie des messages différents à des mathématiciens différents, alors les lumières peuvent être allumées ou éteintes, mais toutes doivent etre dans le même état). Jusque là, il n'y a aucune difficulté, il suffit que chacun communique à tous les autres le message qu'il a reçu du Docteur No et qu'on suive une stratégie décidée à l'avance. Le problème, c'est qu'un petit nombre de mathématiciens (un ou deux, peut-être trois, mais certainement pas plus) sont vendus au Docteur No : ce qu'ils feront (allumer ou éteindre les lumières) n'est évidemment d'aucune importance, mais on ne sait pas qui sont les traîtres et ils peuvent mentir effrontément au téléphone (ils peuvent dire à un mathématicien qu'ils ont reçu tel message et à un autre qu'ils ont reçu tel autre, par exemple). Le Docteur No exige, sous peine de tuer tous les mathématiciens loyaux avec des tortures particulièrement raffinées, que tous ces mathématiciens (loyaux) fassent la même chose (allumer ou éteindre la lumière) et que, s'ils ont tous reçu le même message, ils le suivent. Comment les mathématiciens loyaux peuvent-ils s'en sortir, malgré la présence des traîtres ?
Bon, je crois que ça suffit comme ça. Je préfère ne pas poser l'archi-classique problème des amazones qui tuent leurs maris quand elles savent qu'ils sont infidèles, parce qu'il est vraiment trop délicat à énoncer correctement, et son intérêt mathématique ou logique est assez douteux (et je ne vois pas comment le formuler à la manière d'une épreuve infligée par le cruel Docteur No ; ajout () : finalement c'est là).
Le fait est, en tout cas, que ces problèmes ont quelque chose en
commun (pas juste ma façon de les raconter 
) : mais je
ne saurais pas dire exactement quoi. Ils sont plus ou moins
mathématiques ou, en tout cas, mathématiquement formulables, mais je
serais incapable de dire à quelle branche des mathématiques il
faudrait les rattacher. Or je voudrais bien pouvoir mettre un nom sur
cette discipline et, surtout, en savoir plus, avoir une vraie théorie
sous-jacente et pas juste des exemples épars de situations
anecdotiques : je suis vraiment curieux de ce à quoi ça pourrait
ressembler (en fait, avoir une théorie unificatrice me semble
impossible mais, finalement, les problèmes eux-mêmes ont pu me
paraître impossible et ça ne les empêche pas d'avoir une solution ;
par ailleurs).
J'ai envie d'appeler ça la combinatoire cybernétique
, car je
range ça dans la combinatoire mais que, plutôt que d'énumérations ou
d'étude de structures, il s'agit de problèmes de communication entre
agents selon des stratégies pré-établies, ce qui peut se regrouper
dans la cybernétique (si tant est que j'aie compris ce que ce mot veut
dire).
Ajout () : D'autres énigmes dans le même registre ici et là. On peut aussi y rattacher ça et ça.
Nouvel ajout () : Encore une énigme de ce genre.