Comments on Le Docteur No continue ses méfaits

Merci pour la réponse, du coup je vais faire une brève vidéo où je poserai l’énigme, sans donner de référence pour que les gens cherchent, puis je donnerai la référence à cette page dans une seconde vidéo contenant la solution.

En tout cas cette énigme a toujours du succès quand je la pose aux amis !

Est-ce que tu peux nous dire d'où vient cette énigme ? Est-ce que tu l'as inventée, ou entendue/lue ailleurs ? J'aimerais l'utiliser pour un article ou une vidéo et je voudrais attribuer correctement la référence. Merci !

En fait, on peut aussi sauver tous sauf un s'il y a une quantité dénombrable de matheux ! ;)

Revenant récemment sur ce problème, je constate qu'il a été remarqué entre temps qu'on peut adopter une version probabiliste donnant de bonnes chances de succès çà un mathématicien isolé. Mais en fait, il
existe une stratégie presque certaine, c'est-à-dire de probabilité de succès 1 : il suffit de réserver une infinité de boites qu'on n'ouvre pas, d'appliquer la stratégie aux autres et de tester le contenu d'une des boites au delà du n_j maximal : s'il est correct, avec probabilité 1, on sait que les autres boites non ouvertes sont correctes aussi, sinon, on recommence la manoeuvre dans l'infinité de boites non ouvertes reservées…

Je passe en français pour éviter les complications inutiles, désolé pour les anglophones…

Je ne suis pas sûr de comprendre de quelle mesure tu parles… L'écueil à éviter dans une formulation probabiliste serait de parler de mesure de proba sur les suites… L'énoncé ne doit pas être "en moyenne sur toutes les suites", mais bien "pour toute suite fixée". Du coup effectivement, quand on voit l'énoncé sans connaitre la réponse, on ne voit pas bien de quelle proba on parle, mais cette proba est en fait uniquement dûe au fait que la stratégie est probabiliste, de maniere clairement définie, et non les données du problème

Ici la seule mesure de proba est discrète : on coupe la suite en un certain nombre N de suites (100 dans l'exemple), et on tire uniformément une suite parmi celles-ci, ce qui nous donne une proba 1/N de nous tromper.

One other way to ask the question, maybe even more paradoxal, is with only one mathematician, who have to guess the content of one box after opening as much as he wants. he can do this with probability arbitrary close to 1.

/!\ spoiler /!\

Bon j'allais proposer une idée de solution, qui ne me semblait pas très convaincante, mais finalement j'ai lu les commentaires avant d'écrire et cette idée était quasiment celle du premier com (le mathématicien M prédit le contenu de la boîte u_M_max{n_i (i!=M)} comme l'élément de même rang de l'unique (v_M) de C —qu'ils ont préalablement défini ensemble— équivalent à sa suite (u_M) ). Solution "pas très convaincante", en raison de l'aspect non-constructif de la définition de C, qui rend problématique l'existence d'un C univoque identique pour tous les mathématiciens après concertation.

Ouvrir une infinité de boites ne paraît pas trop difficile en soi ; si le mathématicien met 1/2^i nanoseconde pour ouvrir la boite i d'une suite il s'en sort très vite !

Cela dit, c'est une des plus belles énigmes mathématiques qu'il m'ait été donné de voir. Ceux qui ont regardé les suppléments des DVD de Harry Potter ont ainsi pu assister à une interview de Jason Isaacs (qui joue Lucius Malefoy) au cours de laquelle il attribuait à l'acteur incarnant son fils Draco une "annoying beauty" ; expression assez adéquate pour qualifier ce problème.

Toujours dans la thématique filmique, une suggestion pour le club nanar : Blades of Glory.

Je suis bien d'accord, et il s'y cache deux thèmes quasiment philosophiques : d'abord, le rôle étrange joué par l'axiome du choix (et dans des cas de ce genre, on tient là une bonne raison "intuitive" de le refuser ; je ne sais plus qui faisait remarquer que l'axiome du choix (sous la forme "un produit d'ensembles non vide est non vide") est évidemment vrai, que l'axiome d'existence d'un bon ordre sur R est évidemment faux, et que le lemme de Zorn laisse indécis), et d'autre part le fait tout aussi étrange que le problème n'est soluble que *parce que* il y a un nombre infini de boîtes ; et d'ailleurs elles pourraient contenir n'importe quelle sorte d'objets mathématiques (appartenant tous à un ensemble, tout de même, par exemple des fonctions quelconques de C dans C), sans que la solution en soit changée, ce qui là aussi est vraiment peu intuitif…

J'ai craqué et regardé les indications (et je ne le regrette pas, je n'y serais jamais arrivé). Je confirme mon enthousiasme au vu de la solution, c'est vraiment un problème éblouissant.

Ben étant donné que le nombre de classes d'équivalence a (au moins) la puissance du continu (bon, vu qu'on suppose AC, exactement ce cardinal), je vois mal comment l'axiome du choix dénombrable pourrait être utilisé…

En me forçant à ne pas lire les autres commentaires pour l'instant, et sans avoir regardé les indications, je ne résiste pas à poster ce commentaire inutile pour manifester mon enthousiasme devant le problème, où je ne démarre pas mais suis fasciné - une des meilleures entrées du blog (enfin en espérant que la solution n'est pas décevante, ne la connaissant pas encore).

Deux remarques sur des ambiguïtés (voulues ou non ?) de l'énoncé, qui ne m'ont quand même pas trop gêné… à moins que je n'aie fait un contre-sens depuis le début.

* "faire une prédiction sur le contenu d'une boîte qu'il n'aura pas ouverte" ne s'éclaire qu'en lisant la suite (le "donné exactement le bon nombre"). Si je ne me suis pas totalement mépris, j'ai compris que la prédiction doit avoir la forme "la boîte n contient le nombre x" et qu'on n'admet pas des prévisions du genre "la boîte 5 contient un nombre transcendant" ou "la boîte 7 ne contient pas pi". C'est en fait forcément ça se dit-on a posteriori parce que sinon, on pourrait oser "la boîte 1 contient un nombre" et hop 100 % de prédictions correctes… Peut-être une petite révision de l'énoncé le clarifiant dès la première utilisation de "prédiction" serait-elle tranquillisante pour le lecteur (écrire "choisir une boîte encore fermée et déclarer quel nombre elle contient" plutôt que "faire une prédiction sur le contenu d'une boîte qu'il n'aura pas ouverte", par exemple) ;

* je vois bien que l'énoncé n'interdit pas explicitement des méthodes d'ouverture de boîtes pas bien réalistes physiquement (mais bon dès lors qu'on peut en ouvrir une infinité…) du genre "ouvrir une boîte à chaque instant rationnel" voire "ouvrir une boîte à chaque instant rationnel non nul" (ce qui voudrait notamment dire qu'il n'y a pas de "première boîte ouverte", que toute décision d'ouverture est prise en fonction de boîtes déjà ouvertes, ce qui est un peu déstabilisant). J'ai renoncé à chercher à imaginer des stratégies aussi tordues - je suppose plus ou moins implicitement que l'ensemble des instants où un mathématicien donné ouvre une boîte est bien ordonné et notamment qu'il y a un commencement à ses investigations ; j'espère que ça ne me ferme pas la porte de la solution. Mais bon sur ce point, le petit mystère que laisse planer l'énoncé ajoute plutôt au charme du jeu, sauf à supposer que ce soit gênant au vu de la solution c'est sans doute très bien comme ça.

Bon je monologue je monologue, mais faut bien avouer que je sèche lamentablement.

Question : est-ce que l'axiome du choix dénombrable (ou sinon le principe des choix dépendants) suffit, ou est-ce qu'il est vraiment nécessaire d'avoir l'axiome du choix "total" ?

Pour W : l'idée d'une solution constructive à un problème de ce genre n'est pas totalement absurde, mais je crains bien que l'axiome de choix ne soit ici nécessaire. En revanche, je peux te rassurer tout de suite au cas où tu tomberais dans les mans du méchant docteur : le temps que tu aies fini d'ouvrir une infinité de boîtes (et de consulter leur contenu), tu seras sûrement mort de vieillesse…

Pourquoi l'enseignement des mathématiques se fait-il sur le mode du sadisme candide?

Jusqu'ici, d'une part il existe un C (si je comprends bien, il en existe même plein), et d'autre part si les mathématiciens connaissent C, il peuvent réussir à être libérés.
La pièce manquante est-elle évidente ? C est-il facile à construire/calculer/choisir ? La solution théorique de l'énigme ne me dit pas comment je ferais si j'étais devant la suite de boîtes du Docteur No.

After reading the hints, it turns out that your hint 1 gives the solution to the puzzle in my previous comment.

I had heard a puzzle from a friend that gives the clue to solving this one.

SPOILER SPOILER

The cruel Doctor No has captured countably infinite mathematicians. He assigns each of the mathematicians a natural number to uniquely identify them, and tells this number to them in advance. After explaining the exact nature of the test and letting them discuss a tactic, the mathematicians are separated from each other. Doctor No has also prepared a room with countably infinite boxes, clearly numbered with the natural numbers on the outside. In each of the boxes there is a real number Doctor No has chosen at whim. One at a time, he brings each mathematician to the room, where the mathematician opens all boxes except for the one whose number matches their identifier number, they then have to guess the number in that one closed box. (The boxes are closed before each mathematician enters, and they are not allowed to communicate with each other in any way during the test.) As long as only a finite number of mathematicians make an error, Doctor No releases them all; but if an infinite number of mathematicians guesses the number in their closed box wrong, “le Docteur No tuera tous les mathématiciens avec ses tortures particulièrement raffinées.” What should the mathematicians do?

SPOILER

Prenant le mode opératoire de l'indication 3. Le mathématicien a déterminé pour chacune des 99 suites le rang n_i (i=1..99) à partir duquel elle coïncide avec son représentant dans C.

Il fait l'hypothèse que n_100 est plus petit que le max { n_i (i=1..99)}
Il examine un segment final de la 100eme suite. et il en déduit le contenu de la boite numéro n_100+1 par exemple.

Seul le mathématicien à qui a été assigné la suite qui réalise le n_j maximal peut se tromper.

(bon, j'ai utilisé les trois indications :( )