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.

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

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.

[postulat]

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 ?

Je crois avoir trouvé celle-ci aussi

###

Le premier prisonnier annonce "Blanc" si il voit un nombre pair de chapeau blanc, et "Noir" si il voit un nombre pair de chapeau noir. Vue que le premier prisonnier voit 41 chapeau, on en déduit que si il voit un nombre paire de chapeau blanc, il voit aussi un nombre impaire de chapeau noire, et vice versa. A cet instant, tout les prisonnier connaissent la parités du nombre de chapeau blanc et du nombre de chapeau noir devant le premier prisonnier.

A partir de la, le second n'a qu'a vérifier la parité du nombre de chapeau noir et blanc. si c'est la parité du nombre de chapeau noir qui a changé, alors son chapeau est noir, et vice versa. Il n'a plus qu'a annoncer la couleur de son chapeau pour être sauvé.

Tout les prisonnier savent qu'a partir du second prisonnier, la couleur annoncée est la couleur du chapeau porté par le prisonnier qui annonce. Ils peuvent donc mettre a jours dans leurs tête la parité du nombre de chapeau noir et du nombre de chapeau blanc, et quand vient leur tour, ils peuvent eux aussi avoir la vie sauve.

Ainsi, tout les prisonnier, du second a l'avant dernier, seront sauvé, soit 40.

Il reste le premier qui a une chance sur deux de s'en sortir, ainsi que le dernier qui ne voit rien qui doit aussi répondre au hasard. au final, il y aura statistiquement 41 prisonnier qui vont être sauvés


###

J'espère que j'ai été claire, le raisonnement est relativement simple (enfin, beaucoup plus que pour l'enigme d'avant en tout cas :p )

Bon, j'ai fini par resoudre l'enigme ! (enfin, je crois :p )

Voici ma solution :

###########


Le premier nombre premier superieur a 50 est 53.Pour Homer, si la somme était superieur a 55, il serait incapable d'affirmer que JP ne sait pas. en effet, le nombre pourrait s'ecrire de la forme 53 + i. Dans ce cas la, la decomposition en produit de facteur premier du produit contiendrait 53. JP sais immediatement que 53 est le premier des deux nombre mystère, car il est impossible de multiplier 53 par un nombre premier sans que le resultat ne depasse 100.

Pour preciser, si le produit vaut par exemple 1855 = 53*5*7, JP deduit immediatement que les deux nombre choisi sont 53 et 35  Je me sert du théorème fondamental de l'arithmétique ici, en considérant la decomposition des deux nombres choisis par Jessica. Si le produit admet 53 comme diviseur, alors au moins un des deux nombre de Jessica admet 53 comme diviseur, et donc ce nombre est 53.

On en deduit que la somme est inferieur a 55.

De plus, on peut utiliser la conjecture de golbach (ouais, je vais chercher loin, mais bon, elle a été verifié pour les "petits" entiers, donc j'ai le droit :p ) pour deviner que si le resultat étais pair, il pourrait s'ecrire comme la somme de deux premiers, et donc il est possible que les deux nombres choisi soient premier, ce qui fait que JP pourra deviner immediatement les deux nombres en voyant le produit.

On en deduit que la somme est inferieur a 55 et impaire.

On peut tres vite trouver a la mano la liste des entier impaire inferieur a 55 qui ne s'ecrivent pas comme la somme de deux premier, c'est 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53

On en déduit que la somme appartient a cette liste.

A partir de la, j'ai cherché pour chacune de ces sommes les valeurs possibles du produit. Par exemple, pour 11 :

Code:

11 [2, 3, 3]
11 [2, 2, 2, 3]
11 [2, 3, 5]
11 [2, 2, 7]

le produit est décomposer en facteur premier, mais je sais que pour 11, les valeur possible du produit sont 2*3*3, 2*2*2*3, 2*3*5 et 2*2*7.
J'ai fais de même avec l'ensemble des nombre de la liste ci dessus, et j'ai isolée les produits qui ne sont associé qu'a une seul somme. Par exemple, J'ai enlevé de ma liste [2, 3, 17] car 3*17 + 2 = 53 et 2*3 + 17 = 23

La liste final des produits associée a une seul somme est la suivante :

Code:

[11, [2, 3, 3]]
[11, [2, 2, 2, 3]]
[11, [2, 2, 7]]
[17, [2, 2, 13]]
[23, [2, 2, 19]]
[23, [2, 2, 2, 2, 7]]
[23, [2, 5, 13]]
[27, [2, 5, 5]]
[27, [2, 2, 23]]
[27, [2, 5, 11]]
[27, [2, 2, 5, 7]]
[27, [2, 2, 2, 19]]
[27, [2, 3, 3, 3, 3]]
[27, [2, 5, 17]]
[27, [2, 2, 2, 2, 11]]
[27, [2, 7, 13]]
[29, [2, 3, 3, 3]]
[29, [2, 2, 5, 5]]
[29, [2, 3, 23]]
[29, [2, 7, 11]]
[29, [2, 2, 2, 3, 7]]
[29, [2, 5, 19]]
[29, [2, 3, 3, 11]]
[29, [2, 2, 3, 17]]
[29, [2, 2, 2, 2, 13]]
[35, [2, 2, 2, 2, 2, 3]]
[35, [2, 2, 31]]
[35, [2, 3, 29]]
[35, [2, 2, 2, 3, 3, 3]]
[35, [2, 3, 3, 13]]
[35, [2, 5, 5, 5]]
[35, [2, 2, 3, 23]]
[35, [2, 3, 7, 7]]
[35, [2, 2, 2, 2, 19]]
[35, [2, 3, 3, 17]]
[37, [2, 2, 2, 2, 2, 5]]
[37, [2, 3, 31]]
[37, [2, 2, 2, 29]]
[37, [2, 2, 3, 3, 7]]
[37, [2, 2, 2, 2, 3, 7]]
[37, [2, 2, 5, 17]]
[41, [2, 3, 19]]
[41, [2, 2, 37]]
[41, [2, 7, 17]]
[41, [2, 2, 2, 2, 2, 3, 3]]
[41, [2, 5, 31]]
[41, [2, 2, 3, 29]]
[41, [2, 2, 7, 13]]
[41, [2, 3, 5, 13]]
[41, [2, 2, 2, 2, 5, 5]]
[41, [2, 2, 2, 3, 17]]
[41, [2, 3, 3, 23]]
[41, [2, 11, 19]]
[47, [2, 2, 43]]
[47, [2, 3, 41]]
[47, [2, 2, 2, 5, 7]]
[47, [2, 5, 37]]
[47, [2, 13, 17]]
[47, [2, 2, 2, 2, 2, 3, 5]]
[47, [2, 2, 2, 2, 31]]
[47, [2, 3, 5, 17]]
[47, [2, 3, 3, 29]]
[47, [2, 2, 7, 19]]
[47, [2, 5, 5, 11]]
[47, [2, 2, 2, 3, 23]]
[51, [2, 7, 7]]
[51, [2, 2, 2, 2, 3, 3]]
[51, [2, 2, 47]]
[51, [2, 5, 23]]
[51, [2, 2, 7, 11]]
[51, [2, 2, 2, 43]]
[51, [2, 5, 41]]
[51, [2, 2, 2, 5, 11]]
[51, [2, 2, 3, 3, 13]]
[51, [2, 13, 19]]
[51, [2, 7, 37]]
[51, [2, 2, 2, 2, 5, 7]]
[51, [2, 17, 17]]
[51, [2, 3, 3, 3, 11]]
[51, [2, 2, 2, 2, 2, 19]]
[51, [2, 2, 5, 31]]
[51, [2, 11, 29]]
[51, [2, 2, 7, 23]]
[51, [2, 2, 2, 3, 3, 3, 3]]
[51, [2, 5, 5, 13]]
[53, [2, 2, 2, 2, 3, 5]]
[53, [2, 3, 47]]
[53, [2, 2, 2, 3, 3, 5]]
[53, [2, 5, 43]]
[53, [2, 2, 3, 41]]
[53, [2, 2, 2, 5, 13]]
[53, [2, 3, 5, 19]]
[53, [2, 2, 2, 2, 37]]
[53, [2, 2, 3, 3, 17]]
[53, [2, 17, 19]]
[53, [2, 2, 3, 5, 11]]
[53, [2, 2, 2, 2, 2, 3, 7]]
[53, [2, 11, 31]]
[53, [2, 3, 5, 23]]
[53, [2, 2, 2, 3, 29]]
[53, [2, 2, 5, 5, 7]]
[53, [2, 3, 3, 3, 13]]

On remarque que seul 17 n'admet qu'une seul produit associé pour 4 et 13. 4+13 = 17 et 4*13 = 2*2*13 = 52


Parlons raisonnement : comme Homer avait devinée que JP ne saurait pas, JP sais que la somme des deux nombre appartient a la liste 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53 (ce sont les seuls sommes qui assurent que JP ne peut pas savoir).
De cela, JP deduit la valeurs des deux nombres. Cela veut-dire que le produit est associée a une seul somme. en effet, si le produits est associé a une seule somme, alors JP peut connaitre la somme associé a son produits, et de fait, deux équation deux inconnue, il résout le problème. Au contraire, si le produits peut être associé a plusieurs somme (comme le produit 2*3*17), il n'est pas capable de resoudre le problème et ne peut pas affirmer connaitre les deux entier (Cette reciproque est pas très rigoureuse, j'avoue :p)
Homer peut deviner que le produits appartient a cette liste, et affirme connaitre la reponse. Puisqu'il connait la somme, on en deduit que cette somme est 17. En effet, si la somme étais differentes de 17, il aurait toujours le choix entre plusieurs produits differents et ne pourrait pas resoudre le systeme. Donc la somme vaut 17, le produit vaut 52, et les deux nombres mystères sont 4 et 13 !


###########

Je me répète, mais bon, vraiment sympa comme enigme pixis !

J'aimerais bien savoir comment faire pour resoudre ça a la main, car ma methode ne s'y prête absolument pas :p

l'enoncé dit bien que chacun des termes doit être inferieur a 100. si le produit vaut par exemple 1855 = 53*5*7, JP deduit immediatement que les deux nombre choisi sont 53 et 35 Je me sert du théorème fondamental de l'arithmétique ici, en considerant la decomposition des deux nombres choisis par Jessica. Si le produit admet 53 comme diviseur, alors au moins un des deux nombre de Jessica admet 53 comme diviseur, et donc ce nombre est 53.

Pour ta seconde remarque, elle est legitime, je m'en suis rendue compte il y a une petite heure, mais les resultat en incluant les nombres premier sont peu concluant, je me retrouve dans le cas ou il est toujours possible qu'un produit de facteur corresponde a plusieurs sommes. je vais continuer de réfléchir un  peu, je pense que j'ai manqué quelque-chose

Salut !

Ton enigme Pixis est vraiment sympa, ça m'a pris la tête toute la soirée d'hier. J'étais partis dans la mauvaise direction, mais en y repensant aujourd'hui, je crois avoir une (semi) solution. Ceux qui réfléchissent encore, je vous invite a ne pas lire la suite :


###########


Le premier nombre premier superieur a 50 est 53.Pour Homer, si la somme est superieur a 55, il sera incapable d'affirmer que JP ne saurait pas. en effet, le nombre pourrait s'ecrire de la forme 53 + i. Dans ce cas la, la decomposition en produit de facteur premier du produit contiendrais 53. JP sais immediatement que 53 est le premier des deux nombre mystère, car il est impossible de multiplier 53 par un nombre premier sans que le resultat ne depasse 100.

On en deduit que la somme est inferieur a 55.

De plus, on peut utiliser la conjecture de golbach (ouais, je vais chercher loins, mais bon, elle a été verifié pour les "petits" entiers, donc j'ai le droit :p ) pour deviner que si le resultat étais pair, il pourrait s'ecrire comme la somme de deux premiers, et donc il est possible que les deux nombres choisi soient premier, ce qui fait que JP pourra deviner immediatement les deux nombres en voyant le produit.

On en deduit que la somme est inferieur a 55 et impaire.

On peut tres vite verifier a la mano parmi les entier impaire inferieur a 55, il n'y a que 27, 35 et 51 qui ne sont pas premier et qui ne peuvent pas s'ecrire comme la somme de deux premier.

On en déduit que la somme est soit 27, Soit 35, soit 51.

J'ai vérifié avec un script python (en fait j'ai réutilisé celui que j'avais codé hier en cherchant sur une fausse piste) qu'il n'étais pas possible de trouver un ensemble de nombre premier telle que, organisé d'une façon sur deux element, la somme fasse l'une de ces valeurs, et organisé d'une autre, la somme fasse une autre de ces valeurs.

Ensuite, j'ai trouvé les liste suivantes :

Si la somme fait 27, les differentes valeurs possible du produit possible sont :
[72, 92, 110, 126, 140, 152, 162, 170, 176, 180, 182]

Si la somme fait 35 :
[96, 124, 150, 174, 196, 216, 234, 250, 264, 276, 286, 294, 300, 304, 306]

Et 51 :
[144, 188, 230, 270, 308, 344, 378, 410, 440, 468, 494, 518, 540, 560, 578, 594, 608, 620, 630, 638, 644, 648, 650]

Aucune valeur en commun, d'ou en connaissant le produit, JP peut deviner la somme, il connait la somme et le produit, deux equation deux inconnue, il connait les deux nombres.

cependant, mon raisonnement s'arrête la. Homer n'a aucun moyen de savoir lequel des éléments des liste ci-dessus est le bon, donc je ne sais pas comment il peut deviner la valeur des deux éléments.
Je suppose que je dois être capable de restreindre encore mes valeurs possible, mais je n'ai rien trouvé de concluant. Je ne pense pas que mon algorithme soit faux, mais ce n'est pas a exclure :p


###########

Je vais probablement continuer d'y penser, mais je pense que je n'irait pas plus loins de cette façon.

Je voudrais juste rajouter que "les deux protagoniste ne sont pas cons" est un doux euphemisme, j'aimerais bien être aussi vif