[pixis]

Tu as tout à fait raison
Je suis en voiture mais j'y réfléchis !

[ferbos]

Du coup, “je peux faire mieux que toi“, en les groupant par 4 .

Dans le même esprit "pratique", j'aimerais savoir ce que chacun dit pour déterminer la proportion de chapeaux noirs ou chapeaux blancs qu'il a devant lui. Rouge? Abracadabra? Saperlipopette? Il tape du pied? Cela doit être assez fun au final. Pour rester dans la règle fixée au départ, on ne peut pas dépasser trois. Sinon, les gardiens, s'apercevant de la supercherie, vont s'en prendre aux pauvres prisonniers.

ferbos

[MioMilo]

Bonsoir !

Il n'y a pas eu d'activité depuis un moment sur ce sujet, j'en profite pour énoncer un petit "puzzle" pas forcement très compliquer mais que j'ai trouvé bien sympa !

Je l'ai trouvé dans un livre qui parle du théorème d’incomplétude de Gödel (Un théorème de logique mathématique qui affirme, pour simplifier, quand dans tout système d'axiome il y aura toujours des énoncés vrai mais impossible a prouver)

Ce "Puzzle Gödelien" peut-être vue comme une introduction au raisonnement derrière ce théorème. je n'ai pas le livre sous les yeux, je vous restitue donc cette énigme de tête. Les connaisseur m'excuserons si je presente la chose de façon inexacte sur la forme et dans les termes utilisés.

Soit une machine qui imprime indéfiniment des textes de longueur fini que l'on nommera postulat. 
Cette machine ne peut utiliser que cinq caractère : P N ( ) !
Les postulat ne sont composée que de ces cinq caractères, cependant, rien ne permet (a priori) de savoir quel postulat la machine est capable d'imprimer et quel postulat elle n'est pas capable d'imprimer, mais on sait que tout postulat imprimable par la machine sera imprimé.

Cependant, il existe certain postulat d'une forme particuliere que l'on nommera  énoncé. Ce sont les postulats de la forme suivante :

• P(X)
• PN(X)
• !P(X)
• !PN(X)

avec X une chaine de caractère quelconque (mais bien sûr toujours composée des cinq caractère utilisable par la machine)

l'énoncé P(X) signifie que la chaîne de caractère X est imprimable par la machine
l'énoncé PN(X) signifie que X(X) est imprimable par la machine ( X(X) est appelé la norme de X)
l'énoncé !P(X) signifie que la chaîne de caractère X n'est pas imprimable par la machine
l'énoncé !PN(X) signifie que X(X) n'est pas imprimable par la machine
On supposera que tout énoncé imprimable est vrai.

Existe-t-il des énoncés vrai mais non imprimable ?

[pixis]

Hello.
Alors je viens de lire cette énigme qui semble rigolote. Cependant, j'avoue que j'ai un petit soucis de compréhension :
Qu'appelle-t-on un énoncé "vrai" ?

[MioMilo]

Effectivement, j'ai manqué de précision alors que c'est un point crucial. Voici plus de détails :

Un postulat X est dit imprimable si la machine peut l'imprimer. On suppose la machine programmée de telle sorte que tout postulat qu'elle peut imprimer sera imprimé tôt ou tard.

De façon informelle, P signifie "imprimable", N signifie "norme" et ! signifie "non"
 P(X) est vrai si et seulement si X est imprimable
PN(X) est vrai si et seulement si la norme de X est imprimable ( c'est à dire si et seulement si X(X) est imprimabe)
!P(X) est vrai si et seulement si X n'est  pas imprimable
!PN(X) est vrai si et seulement si la norme de X n'est pas imprimable

On suppose que tout énoncé imprimé par la machine est vrai.

Voilà, j'espère que le problème est plus clair.

J'ai fais une petite recherche google, et impossible de trouver cette énigme sur le web, elle pourrait potentiellement faire une épreuve de logique pour NC.

[ferbos]

Bonjour MioMilo,

Que donne P(), PN(), !P(), !PN()?
Autrement dit, ces 4 séquences sont-elles des énoncés? Et le caractère vide est-il imprimable?

ferbos

[MioMilo]

La seul contrainte est que les postulats sont de longueur fini, donc à priori il n'y a pas de problème à considérer le postulat vide comme "valide".
Cependant, on ne peut pas savoir à priori si il s'agit d'un postulat imprimable

[ferbos]

Salut,

au départ je pensais à P(P()) mais maintenant je me dis que pas sûr.

ferbos

[MioMilo]

effectivement, P(P()) n'a aucune raison d'être vrais ou faux, ou d'être imprimable ou non imprimable, il n'y a donc pas grand chose a en tirer tel quel.

[harvey]

Voici un joli problème pas tout neuf, mais que peut-être certains ne connaissent pas.

La société Necropost organise un jeu télévisé auquel participent 32 personnes.
Selon la règle, les joueurs passent tour à tour dans une pièce qui contient une machine avec 32 boutons. Chaque bouton affiche le nom d'un joueur différent (on ne sait pas a priori lequel), et chaque joueur peut appuyer sur 16 boutons. Si chaque joueur parvient à afficher son nom, alors ils gagnent tous le dernier esclave bionique i-slave 18. Si l'un d'eux échoue, le jeu s'arrête et ils repartent les mains vides.
 
Les joueurs ont quelques heures pour se préparer et discuter de leur stratégie. En revanche, il ne peuvent plus communiquer dès que le jeu commence.
La salle où se trouve la machine est insonorisée, entourée d'une cage de Faraday, et toute tentative de triche les condamne à 30 ans de travaux forcés dans les mines de Necropost sur la ceinture d'astéroides.

Quelle est la stratégie optimale, et quelle est leur probabilité de gagner ?
(on cherche une probabilité non-négligeable, disons supérieure à 1/10)

[BAAL]

Je ne suis pas sûr d’avoir compris la question...
1) Les boutons peuvent-ils être différenciés d’une manière ou d’une autre (par nombre, ordre, couleur, ou autre...)?
2) Qui peut voir les noms affichés? tous les joueurs, incluant celui qui pousse les boutons?
3) Voit-on les noms à mesure qu’ils d’affichent? ou alors tous ensemble à la fin?
4) Un joueur s’arrête-t-il une fois qu’il a réussi à afficher son nom, ou a-t-il le droit de continuer?

[harvey]

1: Oui, les boutons sont différenciés. On peut supposer qu'ils sont numérotés de 1 à 32 (et un bouton affiche toujours le même nom).
2: Seul celui ou celle qui presse les boutons peut voir l'affichage. Les autres sont en attente dans une autre pièce.
3: On voit les noms à mesure qu'ils s'affichent.
4: Il peut continuer, mais ça ne sert à rien.

Ceux qui attendent ne reçoivent aucune information sur le déroulement du jeu. Ils ne connaissent que les règles et le résultat de leur concertation.

[BAAL]

Pas facile ton énigme... je crois avoir compris mais c’est bien plus dur que ça n’en a l’air.
Juste pour vérifier, il y’a bien une solution mathématique avec papier/crayon?

[harvey]

La solution est assez simple, calculer la probabilité qui en résulte est plus complexe. Mais ça reste faisable avec papier et crayon.
Avec les notions mathématiques qui vont bien, on peut en trouver une bonne approximation, qui révèle une propriété intéressante (et contre-intuitive).

[Darkkuk]

Alors, le premier joueur n'ayant aucune information sur les tiroirs en prend 16 au hasard, soit par exemple les 16 premiers. Il a donc une chance sur deux de trouver son nom.

Pour le second c'est plus compliqué, il doit supposer que le premier a trouvé son nom sinon ils ont perdu tous les deux. Donc la probabilité que son nom soit dans les 16 que son collègue a pris est de 15/31 alors qu'il est de 16/31 dans les 16 autres.
Il a donc plus de chances de trouver son nom dans un des 16 tiroirs qui n'ont pas été choisis, les 16 derniers donc, que dans ceux déjà tirés.
La probabilité que les deux gagnent est donc de (1/2)*(16/31) = 8/31.

Est-ce vraiment la meilleure stratégie ? J'ai l'impression que oui mais cela ne m'a pas semblé très dur à trouver...  J'ai marché à l'intuition..