Comments on Le Docteur No continue ses méfaits

@jeanas : je reviens seulement tardivement ici, pensant que mon commentaire avait peu de chance d'avoir suscité une réaction, donc c'est sans doute trop tard pour que vous réagissiez à ce nouveau commentaire…

Pour clarifier mon propos (autant que possible, car ce n’est pas mon domaine donc je ne prétends pas que tout est parfaitement clair dans ma tête), l’indépendance de l’axiome du choix par rapport à ZF, signifie (en supposant la cohérence de ZF) que ZFC est tout autant cohérent que ZF-(non C), et l’existence d’un objet pourrait être prouvable dans ZFC mais réfutable dans ZF-(non C) ou ZF-(un autre axiome indépendant), c’est dans ce sens que je qualifie l’existence de l’objet de « ni vraie ni fausse » : cela dépend du système axiomatique choisi. Quant à la cohérence de ZFC il me semble que le théorème de Gödel nous indique seulement qu’on ne peut pas démontrer qu’elle est vraie, mais pas qu’on ne peut pas démontrer qu’elle est fausse (la cohérence est justement vraie dès lors qu’on ne peut pas démontrer qu’elle est fausse !).

Le terme de « monstre » que j’ai utilisé est évidemment hautement subjectif (d’où les guillemets), mais je n’y assimilerais pas des objets qui s’ils paraissent surprenants voire paradoxaux au premier abord, ont une démonstration constructive de l’existence qui permet (plus ou moins) à notre intuition d’en appréhender la nature.

Le point essentiel de mon commentaire restait cependant le fait que dans l’énoncé de l’énigme les mathématiciens doivent faire une prédiction, mais s’ils ne disposent pas d’une méthode constructive ils ne peuvent rien prédire donc Dr No ne les libérera pas !
(j’espère ne pas passer pour un constructiviste pur et dur en insistant sur ce point, c’est peut-être juste une déformation professionnelle : quand mon employeur (que je soupçonne parfois d’être Dr No utilisant un pseudonyme) me promet une rémunération contre la solution optimale à un problème, il ne lui suffit pas que je lui affirme que cette solution existe…)

Les conclusions semblent complètement absurdes… quoique le raisonnement paraisse inattaquable. Je pense toutefois avoir trouvé un contre-argument, qui n'implique pas l’axiome de choix.

Imaginons que nous construisions pas à pas une suite en ajoutant 1 en début et 0 en fin :
Étape1 : 1, 0
Étape2 : 1, 1, 0, 0
Étape3 : 1, 1, 1, 0, 0, 0
…
Après une infinité dénombrable d’étapes, on obtient la suite suivante :
1, 1, 1, … 1, 1, 1, 0, 0, 0, …
c’est-à-dire une infinité de 1… « suivie » d’une infinité de 0. Appelons Z cette suite un peu pathologique.

Pour son épreuve, le docteur No pourrait choisir de construire cette suite Z et la placer dans les boites, ceci en une infinité dénombrable d’étapes – il serait absurde de le priver des « pouvoirs infinis » dont disposent ses prisonniers ! Sa méthode pourrait être la suivante, par exemple : à chaque étape k,
il place un 0 dans la boite #2k,
il place un 0 dans la boite #2k–1,
il place un 1 dans la boite #k (remplaçant définitivement le 0 qui s’y trouve).

Une fois toutes les boites remplies, les 100 mathématiciens commencent leur travail… Notons d’abord que la suite Z échantillonnée par 100 revient à Z elle-même (ceci n’a rien d’exceptionnel et peut se produire pour des suites plus classiques). Ils n’auront aucun problème à identifier que toutes les suites se terminent par une infinité de 0, et leur associer la « suite représentante » choisie au préalable, par exemple 0, 0, 0, 0, …. Le vrai problème survient quand ils devront déterminer la boite à partir de laquelle n’apparaissent plus que des 0 : son indice est infini et, donc, la méthode ne fonctionne plus ! La raison est que Z n’est en définitive PAS équivalente à 0, 0, 0, 0, …., puisque qu’elle en diffère par une infinité d’éléments (tous les 1).

La suite Z est donc insoluble avec la méthode proposée. Et on peut facilement imaginer toute une catégorie de suites tout aussi insolubles : il suffit d’ajouter des éléments deux par deux, à chacun des deux bouts, en gardant l’indice #1 sur l’élément le plus à gauche. Le nombre de telles suites ne me parait pas négligeable a priori… Il se pourrait même qu'elles apparaissent…. "presque partout" (dans le sens mathématique de ce terme) !

Qu’en pensez-vous ? N’hésitez pas à réagir…

Quelle est la réponse pour la deuxième indication ?

@davdc : Je poste peut-être trop tard pour que vous lisiez ce commentaire, mais permettez-moi de faire quelques remarques concernant l'axiome du choix.

1. Ce n'est pas parce que l'axiome du choix est indépendant de ZFC qu'il n'est ni vrai ni faux. À titre de comparaison, la cohérence de ZFC est aussi indépendante de ZFC (par le théorème d'incomplétude de Gödel), pourtant il est difficile de soutenir, sauf à être un constructiviste pur et dur, qu'elle n'est ni vraie ni fausse : autant je veux bien qu'il soit compliqué de savoir ce qu'est exactement un ensemble, autant une démonstration dans ZFC est un objet fini hautement manipulable et parfaitement défini, on peut écrire un programme qui recherche une démonstration de ⊥ dans ZFC, et dire que la cohérence de ZFC n'est ni vraie ni fausse, c'est dire que ce programme ni ne termine ni ne termine pas, ce qui est quand même un peu fort de café. En fait, on a toutes les raisons de croire que la cohérence de ZFC est vraie (et heureusement), personne ne fait de maths avec des axiomes qui impliquent « ZFC est incohérente ».

2. Sur les « monstres » : je pense qu'il faut relativiser parce qu'on connaît aussi un bon nombre d'objets hautement paradoxaux dont on peut prouver l'existence sans l'axiome du choix, par exemple :

- À un niveau élémentaire, une bijection entre une droite et un plan (en général, quand on découvre ça, on est quand même un peu surpris),
- Une fonction ℝ → ℝ telle que l'image de n'importe quel intervalle ouvert est ℝ tout entier (chercher « fonction 13 de Conway »),
- Une fonction continue [0, 1] → [0, 1]² qui est surjective (chercher « courbe de Peano »),
- Un retournement de la sphère.

3. Sur l'existence d'un bon ordre sur ℝ : le premier ordinal non-dénombrable, ω₁, peut être construit sans l'axiome du choix, donc si vous voulez rejeter l'existence d'un bon ordre sur ℝ, vous devez aussi rejeter l'hypothèse du continu, ce qui n'est pas du tout anodin.

J'ai découvert avec intérêt récemment la série de supplices auxquels le Dr No se complait à soumettre les mathématiciens, et je dois dire que cette énigme-ci m'a particulièrement retourné le cerveau…

Après y être revenu plusieurs fois pour me faire une opinion, je vais faire 2 remarques liées à l'utilisation de l'axiome du choix :

- ce genre de résultats qui démontre l'existence de "monstres" milite clairement pour moi contre l'acceptation de l'axiome du choix total. Si AC peut paraitre naturel au premier abord, ce n'est que parce que l'intuition qu'on peut s'en faire concerne les ensembles dénombrables. Le théorème de Banach-Tarski, l'existence d'un bon ordre sur R, ou bien ici un ensemble permettant de faire des divinations ne s'apparentent à rien de "naturel" que l'on puisse observer. C'est purement un exercice de pensée, qui n'est ni vrai ni faux (puisque AC est indépendant et n'apporte pas de contradiction à ZF), mais je pense qu'un autre axiome permettrait de construire une théorie dont les résultats seraient plus en accord avec notre expérience du monde : peut-être l'axiome de détermination ou qqc du genre… Bref, je ne suis pas un expert du domaine donc cette remarque relève juste de philosophie mathématique de comptoir…

- cependant même en admettant l'axiome du choix, on n'a aucune indication sur la façon dont on peut construire l'ensembles des représentants des classes d'équivalence (contrairement à la question du schéma d'ouverture des boîtes, qui s'il n'est pas réalisable en pratique est quand même définissable explicitement).
J'estime donc qu'on n'a pas répondu à la question "Comment les mathématiciens font-ils pour être certains d'être tous libérés ?"
Dr No se contentera-t-il de l'affirmation des mathématiciens qu'une stratégie existe ? N'attend-il pas d'eux qu'ils disposent d'une solution dans le cadre du constructivisme ?

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 :( )