Un paradoxe

rosab
rosab
dans Fondements et Logique
Bonjour,

Dans le corps d'une démonstration mathématique, peut-on réutiliser un résultat démontré quelques lignes plus haut ?

Pour vous permettre d'en douter, examinons un jeu à deux joueurs (ou joueuses), ou plutôt un défi, posé à un mathématicien A, qui sera le codeur, face à un mathématicien B, qui sera le décodeur.
Ajoutons un médiateur M muni d'une pièce de monnaie, qui assurera secrètement un unique tirage à pile ou face.

Voici le protocole, bien entendu connu de tous les protagonistes :
A choisit un nombre entier strictement positif, le communique au seul médiateur. Celui-ci lance secrètement sa pièce, et, uniquement si le tirage donne "pile", ajoute une unité au nombre donné par A. Puis le médiateur communique à B le nombre résultant, qui peut donc être le nombre donné par A, ou ce nombre augmenté de 1 suivant le tirage au sort.

Le défi soumis à A est le suivant :
"Pouvez-vous choisir votre nombre de façon à ce que, quel que soit le tirage de la pièce de monnaie, B soit incapable, à la seule connaissance du nombre qu'il aura reçu, de deviner votre nombre initial, et surtout de fournir une démonstration mathématique de sa déduction ?"

A ne peut pas choisir le nombre 1. En effet, si le médiateur tire "face", B recevra ce nombre 1 inchangé, et les conditions du protocole impliquent que le choix de A ne pouvait être que 1. B n'aura aucun mal a le prouver.

A ne peut pas choisir le nombre 2. En effet, si le médiateur tire "face", B recevra ce nombre 2 inchangé. B ne connaît pas le tirage de la pièce, mais démontre alors que A a choisi soit 1, soit 2. Or B peut réutiliser la démonstration ci-dessus prouvant que A ne peut pas choisir 1. Cela prouve que le choix de A était 2.

A ne peut pas choisir le nombre 3. Sinon B risque de recevoir ce nombre inchangé, et démontrer que le choix de A était soit 2, soit 3. Il peut alors réutiliser la démonstration du paragraphe précédent de façon analogue, laquelle prouve que A ne peut pas choisir 2. Cela prouve que le choix de A était 3.

Et ainsi de suite ... Il semble que le défi soit impossible à réaliser ? Quel que soit le nombre choisi par A, il y a toujours le risque que B puisse fournir une démonstration !

Bon, vous êtes en B. Le médiateur vous dit : 16. Si le raisonnement ci-dessus est correct, vous pouvez démontrer que A n'a pu choisir ni 15, ni 16. Mais en quoi le fait de ne pas pouvoir choisir 1 ou même 2 peut-il intervenir dans le choix de 15 ou 16 ?

Par ailleurs (mais c'est une autre discussion), si tout est interdit, tout devient possible ?

Réponses

  • Martial
    Martial
    Je pense que ton problème est mal posé. Il faut dire : le raisonnement ci-dessus peut être prolongé par récurrence jusqu'à démontrer que pour tout $n \geq 1$, A ne peut pas choisir $n$ sans risque que B devine le nombre avac preuve à l'appui.

    Et pourtant, s'il choisit 15, et que Pile, ou s'il choisit 16, et que Face, B est dans la merde...

    En voici une variante : le juge, qui ne se trompe jamais, dit au condamné "vous serez exécuté un matin de la semaine prochaine. Le bourreau viendra vous chercher à 6 heures tapantes, et vous n'aurez aucun moyen de savoir à l'avance la date de votre exécution".
    Une fois le condamné revenu dans sa cellule, son avocat lui remonte le moral : "ne vous inquiétez pas, ce juge est un fieffé menteur. Regardez bien : compte tenu de ce que le juge a dit le bourreau ne peut pas venir dimanche, car sinon le samedi à 6h05 vous sauriez que vous allez être exécuté le lendemain et pourriez le prouver au juge. OK ? Ceci étant acté, il ne peut pas non plus venir le samedi, pour la même raison. Et ainsi de suite par récurrence. Donc vous ne serez pas exécuté la semaine prochaine".

    Convaincu, le condamné dort sur ses deux oreilles. Le mercredi à 6 heures le bourreau vient le chercher, et là le condamné tombe sur le Q. Effectivement, il ne s'y attendait pas.
  • rosab
    rosab
    Merci pour les commentaires.
    On peut effectivement voir ce problème comme une variante de ce (très) fameux paradoxe.
  • Martial
    Martial
    Je n'ai jamais été vraiment capable d'expliquer de façon rigoureuse le paradoxe du pendu. (C'est exactement la même chose que ton problème, sauf qu'il n'y a que 7 jours dans la semaine, donc pas d'allusion à l'infini, donc plus facile à raconter à un non-matheux).

    Pour moi l'embrouille vient du fait que l'énoncé du problème mélange mathématiques et psychologie. En fait tout dépend du niveau d'intelligence que le juge attribue au condamné (ou à son avocat).
    1) S'il les juge bêtes comme leurs pieds il peut envoyer le bourreau n'importe quel jour.
    2) S'il les juge un peu intelligents il peut se dire qu'ils vont se tenir le début du raisonnement (ce que ferait toute personne sensée, même non logicienne) et va éviter le dimanche.
    3) S'il les juge un peu plus intelligents il va aussi éviter le samedi, etc.
    4) S'il les juge aussi intelligents que dans l'énoncé ci-dessus le bourreau peut débarquer n'importe quel jour (même le dimanche), il surprendra toujours le condamné.
    5) Enfin, s'il les juge super-intelligents il est dans la merde. Parce que si le bourreau se pointe le mercredi, le condamné peut toujours lui raconter l'histoire jusqu'au jeudi. Conclusion : "Vous voyez bien, m'sieur le bourreau, je le savais que vous alliez venir aujourd'hui !"
  • Foys
    Foys
    Soit $M\in \N \cup \{+\infty\}$ (une possible borne pour faire des simulations concrètes).
    On considère un jeu entre Alice et Bob où Alice tire un entier $n$ inférieur à $M$ et Bob reçoit $\sup\{M, n+U\}$ où $U$ est un nombre aléatoire dans $\{0,1\}$ inconnu de Bob et Alice. Bob gagne s'il donne la bonne valeur de $n$.

    Quelles sont les stratégies optimales (elles vont être mixtes probablement) pour les deux joueurs? (Et non, Bob ne gagne pas 100% de ses parties; Alice peut tirer $n$ au pif).

    Le paradoxe provient en partie de la difficulté à formaliser ce jeu dans sa version originale (ça va être un énoncé de logique modale/doxastique où il faut exprimer proprement ce qui se passe dans la tête de l'autre).
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • christophe c
    christophe c
    Il y a un fil dans shtam où j'ai tout expliqué récemment et un autre qui date de quelques années où idem.

    Il n'y a pas vraiment de paradoxe. Enfin je veux dire qu'une théorie avec des axiomes faux peut prouver des trucs faux et ce n'est pas paradoxal.

    Dans le cas présent, il existe des preuves qu'un truc a lieu à partir d'axiomes faux très visibles. Et à la fin on dit "ah, c'est marrant, on a prouvé un truc faux"... Mouais, le label paradoxe a des représentants plus brillants disons :-D

    J'ai envie de dire que c'est plus drôle quand c'est dur de trouver l'axiome faux, ce qui est pas le cas ici.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Georges Abitbol
    Georges Abitbol
    C'est lequel ? J'ai pas trouvé ton fil, christophe. C'était initié par toi, ou par quelqu'un d'autre ?
  • christophe c
    christophe c
    Je redonne (flemme de chercher) le principe. Je prends la version "examen surprise".

    1/ Précision de la règle du jeu: il n'y a pas de limite au nombre de fois où on peut aller voir le dirlo le matin pour argumenter. On peut par exemple y aller tous les matins.

    2/ La règle du jeu promise par le dirlo est que si l'étudiant lui amène une preuve, le matin du jour X que l'exam aura lieu l'après midi du jour X, alors il annule l'exam

    3/ Selon les critères ou les axiomes si tu préfères que l'on choisit d'accepter, il se produit la chose suivante:

    4/ pour chaque jour X, il existe une preuve produisable le matin du jour X que l'exam a lieu l'après midi du jour X

    5/ Selon la règle (1), cela permet d'annuler l'exam chaque jour.

    6/ Pour dire qu'il y a un paradoxe "de bonne facture", il faudrait établir que ces preuves sont crédibles. Ce qui n'est pas le cas du tout, puisqu'en les modifiant un peu on a une preuve assez courte de $0=1$, et la recherche des axiomes faux ne pose pas de problème.

    7/ Par contre, psychologiquement, "on a prouvé ça, et pourtant c'est faux" crée un effet, basé sur l'utilisation du mot preuve même quand elle contient des axiomes "libres".

    8/ Pour finir, si tu as besoin d'expliquer ça à des gens, prends une semain de UN jour (ou éventuellement de DEUX jours), ça éviter les atermoiements.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Georges Abitbol
    Georges Abitbol
    Les règles du directeur sont donc les suivantes ?

    1) Il existe un jour $X$ tel que l'exam a lieu l'après-midi du jour $X$.
    2) Pour tout jour $X$, si, au matin de $X$, on lui présente une démonstration dont il accepte les hypothèses, du fait que l'examen ne peut pas avoir lieu l'après-midi du jour $X$, alors l'examen n'a pas lieu le jour $X$, sachant qu'il accepte comme hypothèses les règles de la logique classique ainsi que les règles que j'écris en ce moment.

    Alors le lundi, le mardi, le mercredi, le jeudi et le vendredi, l'élève apporte la démonstration "ça ne peut pas être vendredi parce que sinon c'est pas surprise donc c'est pas jeudi, etc." et l'exam n'a donc lieu aucun jour, et donc le directeur a violé sa règle 1).

    C'est ça ?
  • christophe c
    christophe c
    Oui c'est ça sauf que c'est "preuve que ça a lieu" et non pas "preuve que ça n'a pas lieu".
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Martial
    Martial
    @Georges : l'élève se pointe le lundi matin et raconte au dirlo l'histoire ci-dessus en s'arrêtant à l'impossibilité du mardi. "Vous voyez bien, m'sieur, l'examen ne peut avoir lieu qu'aujourd'hui". Donc le dirlo annule l'examen.

    Le lendemain le gus se repointe et raconte le même baratin au dirlo, en prenant bien soin de s'arrêter à l'impossibilité du mercredi. Nouvelle annulation, et ainsi de suite. L'examen n'aura jamais lieu.

    Ce truc est encore plus débile que l'histoire du pendu ou que le problème initial de ce fil.

    @Christophe : je pense que l'axiome faux est une sorte de psychologisation de la logique. Je n'arrive pas à le formuler correctement, mais je pense que le discours confond volontairement plusieurs niveaux de conscience, genre "l'exam aura lieu cet aprem" avec "je sais que l'exam aura lieu cet aprem" etc.
  • christophe c
    christophe c
    Comme je suis sur PC, je précise ce qu'il se passe (je prends l'histoire et la respecte telle quelle) de manière plus formelle. Par contre (flemme), semaine de 3 jours, dans l'ordre temporelle, $A,B,C$

    De nonA et nonB on peut déduire C, par une preuve $X_1$.

    De l'existence de $X_1$, on peut déduire non C par une preuve $X_2$

    De non A et nonC, on peut déduire B par une preuve $X_3$

    De l'existence de $X_3,X_2$, on peut déduire $nonB$, par une preuve $X_4$

    De nonC et nonB on peut déduire A, par une preuve $X_5$.

    De l'existence de $X_5$, on peut déduire non A par une preuve $X_6$

    Mais comme je l'ai souvent dit sur ce problème, dès le départ on a une théorie qui s'annonce contradictoire assez vite. Pour ça, il suffit de prendre une semaine de .. UN jour. Ca donne:

    Le matin de l'unique jour, je viens et annonce le DS pour l'après-midi. Vues les promesses, il n'aura alors pas lieu l'après-midi. On a donc une preuve qu'il aura lieu l'après midi et une preuve qu'il n'aura pas lieu l'après-midi. Ca porte un nom: les axiomes sont contradictoires :-D

    A noter (je commente les échanges passés sur ce forum) que l'effet de surprise n'a ici rien à voir avec la choucroute.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 8

AmadouFoysLirone93 +5 Invités