Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 23-05-2016 20:27:25

Yassine
Membre
Inscription : 09-04-2013
Messages : 973

L'adultère tue : suite

Bonjour à tous,
Je repost après une longue période d'absence.

J'ai eu une une discussion récente avec un collègue sur une vielle énigme postée dans la rubrique "Enigmes" par Barbichu (lien). La discussion portait sur une variante de ce problème : on suppose maintenant que le chef n'annonce pas qu'il existe au moins un cocu. Alors, même après 22 jours, il ne se passera rien (la récurrence ne peut pas démarrer). Après 100 jours (ou 103 si on veut ;-) ), le tyran dit à tous "ah au fait, on m'a rapporté qu'il y a au moins un cocu parmi vous". 22 jours plus tard, les premiers assassinats sont publiés.
Le "paradoxe" est que le deuxième discours ne semble apporter aucune information (chacun des villageois savait qu'il y  avait au moins 21 cocus) !
Mon collègue m'a expliqué que le prof qui a écrit le livre où ce sujet était traité, donnait comme explication que le deuxième discours apportait, un savoir "mutuellement récursif" : je sais, je sais que tu sais, tu sais que je sais, je sais que tu sais que je sais, ...

Je ne suis pas entièrement convaincu par cette explication. Mais comme le gars qui l'a donné est prof de math à l'X, je pense que je me trompe. Mon argument est le suivant : Ce truc du savoir "mutuellement récursif" était déjà présent avant le deuxième discours. Chacun savait qu'il y avait soit 21, soit 22 cocus. Il savait également que les autres devaient connaitre soit 21 soit 22 cocus et que donc il savaient qu'il y en avait au moins 1, et ainsi de suite.
J'ai essayé sans succès d'adopter une approche avec la théorie des modèles (je suis débutant sur ce sujet). Mon idée est la suivante : formaliser le problème avec des prédicats du premier ordre. Montrer qu'avec ce langage et un set d'axiomes bien choisis, on peut construire une théorie qui puisse montrer : "s'il existe au moins un cocu et que la première publication a lieu le jour j, alors il y a j cocus". La "connaissance commune" des villageois seraient donc matérialisée par les théorèmes démontrables dans cette théorie. Le deuxième discours permet donc juste de dire que les villageois sont dans un modèle (au sens de la théorie des modèles) dans lequel il peuvent utiliser le théorème dont j'ai parlé.
Pour les spécialiste, ça peut paraître confus, je m'en excuse d'avance.

Voila ce que j'ai tenté :

Dans mon langage, je définis les prédicats suivants :
[tex]C(x)[/tex] : [tex]x[/tex] est cocu
[tex]S(x,y)[/tex] : [tex]x[/tex] voit que [tex]y[/tex] est cocu
[tex]D(t,x)[/tex] : à l'instant [tex]t[/tex], [tex]x[/tex] "découvre" qu'il est cocu
[tex]P(t,x)[/tex] : à l'instant [tex]t[/tex], il est publié dans le journal que [tex]x[/tex] a tué sa femme.

Je définie également les expressions suivantes :
    [tex]|e|[/tex] cardinal de l'ensemble [tex]e[/tex]
    [tex]\alpha:=|{\{z | C(z)\}}|[/tex] cardinal de l'ensemble des cocus
    [tex]v(x) := \{z | S(x,z)\}[/tex] ensemble des cocus que voit [tex]x[/tex]
    [tex]\tau := \inf\{n\ |\ \exists x \ P(n,x)\}[/tex]  instant de la première publication

Par convention, [tex]\tau = +\infty[/tex] s'il n'y a aucune publication.


Je définis ensuite les axiomes de ma théorie :
[tex]\begin{align}
& \exists x\ \neg C(x) & \textrm{ Il y en a au moins un non cocu} \\
& \forall x\ \neg S(x,x) & \textrm{ Aucun cocu ne voit qu'il l'est} \\
& \forall x\ C(x) \implies \left(\forall y \ S(y,x) \vee x=y\right) & \textrm{ ça se voit} \\
& \forall x\ \forall y\ \ S(x,y) \implies C(y) & \textrm{ pas cocu, pas vu}  \\
& \forall x\ \forall n D(n,x) \implies C(x) & \textrm{ on ne découvre pas le faux}  \\
& \forall x\ \forall n  D(n,x) \Leftrightarrow P(n+1,x) & \textrm{ la découverte entraîne le meurtre et la publication}  \\
& \forall x\ \neg P(0,x) & \textrm{ Rien n'est publié le premier jour}  \\
& \forall x\ \forall n \left(\exists y\ C(y) \wedge \tau > n \wedge |v(x)|=n\right) \implies D(n,x) & \textrm{Canard boiteux}
\end{align}[/tex]

Mon dernier axiome est un peu boiteux. J'ai essayé de le limiter au seul cas zéro (si je ne voit aucun cocu et que je sais qu'il y en a au moins un, alors c'est moi), mais ça ne m'a pas permis de montrer la récurrence. Du coup, il est trop fort est ne fait pas vraiment partie des données du problème. Je ne fais que cacher le problème sous le tapis.

Est-ce que quelqu'un a un avis éclairé sur mes tentatives ?
Est-ce voué à l'échec  (nécessite les prédicats du deuxième ordre) ?

En tout cas, tout conseil est le bienvenu. A vous lire.

Cordialement

Dernière modification par Yassine (25-05-2016 18:59:17)


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#2 24-05-2016 06:57:23

Yassine
Membre
Inscription : 09-04-2013
Messages : 973

Re : L'adultère tue : suite

Pour appuyer mon propos initial concernant mon incompréhension de l'explication sur le savoir mutuel récursif, je donne une interprétation différente du problème :

Je considère une zone contaminée et je suppose qu'on a des robots qui nettoient la zone. Chacun des robot dispose de plusieurs capteurs. Un premier capteur lui permettant de connaitre le nombre total de robots, et les autres lui permettent de savoir si les autres robots fonctionnent correctement. Pour des raisons de fiabilité, on ne dote pas le robot d'un capteur lui permettant un auto-diagnostic (la panne pourrait toucher le capteur lui même). On dote également le robot d'une commande lui donnant l'ordre de quitter la zone (cette opération prend un certain temps, qu'on appellera par la suite 'jour'). Le robot peut héberger un programme Python avec les verbes suivants : NombreTotalRobots(t), MarcheAutreRobot(numRobot), SeRetirer(t).
La question est : Peut-on concevoir un programme qui fera se retirer les robots défectueux, et uniquement eux ?

Pour moi, la réponse est 'non' en toute généralité et 'oui' si on sait qu'il y a au moins un robot défectueux. Dans ce cas, c'est le programme qui exécute l'axiome que j'ai appelé 'Canard boiteux' : "Si au bout de n jours, je vois toujours tous les robots et que je n'en compte que n défectueux, je me retire".

Avec cette interprétation, on se débarrasse de l’ambiguïté qui plaçait les villageois à la fois dans la position de robots et dans la position du concepteur du programme.

Pour revenir à ma tentative d'explication, la théorie, ce sont l'ensemble des programme que je peux écrire pour les robots, et le modèle est une zone contaminée particulière.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#3 25-05-2016 18:55:01

Yassine
Membre
Inscription : 09-04-2013
Messages : 973

Re : L'adultère tue : suite

Bon, ça n'a pas l'air d'inspirer grand monde !
Sniff...


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le troisième mot de cette phrase?

Pied de page des forums