Enigmes logiques

[Nickocko]

Envoyé par ChemicalStöf

Non, le nombre d'atteints ne varie pas. C'est le même du début à la fin. J'ai peut-être mal énoncé le problème...

Oui, on n'apprends nul part comment se propage la malédiction, et l'on ne sais mm pas combien de moines sont atteints le 1er jiour (les moines apprennent qu'une malédiction a atteint au moins l'un d'entre eux).

[ChemicalStöf]

Justement, la malédiction ne se propage pas. Quant au nombre de maudits et le nombre total de moines, ils ne sont pas importants pour résoudre l'énigme.

Essayez de prendre des cas concrêts. Admettons qu'il y ait 1 maudit. Comment fait-il pour savoir qu'il est maudit?
Une fois avoir résolu ce cas là, essayez avec 2 maudits, puis 3, etc.

[tfoth]

Envoyé par ChemicalStöf

bien ouèj! Une autre, plus simple:

3 prisonniers sont alignés à la file indienne, et ne peuvent voir que devant eux.
Donc celui tout devant ne voit personne, celui au milieu ne voit que celui devant, et celui de derrière voit celui du milieu et celui de devant.
Chaque prisonnier a un bonnet sur la tête, mais ne peut pas le voir: celui du milieu a un bonnet noir tandis que les 2 autres ont un bonnet blanc. Il y a également un autre bonnet noir, mais les prisonniers ne peuvent pas le voir. Ils savent juste qu'au total, il y a 2 bonnets blancs et 2 bonnets noirs.
Les prisonniers seront libérés lorsque l'un d'entre eux dira la couleur de son bonnet, sans se tromper.

Qui donnera la réponse, et pourquoi?
Celle là est vraiment simple

En effet :

Spoiler: cliquez pour révéler le contenu

Celui du milieu. En effet, il voit un bonnet blanc alors qu'il sait qu'il n'y en a que deux. Si lui-même avait un bonnet blanc, le troisième se saurait possesseur d'un bonnet noir. Si le troisième est indécis, c'est qu'il voit deux bonnets différents, donc après un temps raisonnable pour que le troisième se décide, il peut donc déclarer avoir un bonnet noir.

Dans cette énigme, la couleur du bonnet du troisième n'a finalement aucune importance

Envoyé par Nickocko

Bin je ne comprends pas trop la logique, sur ce point.

Spoiler: cliquez pour révéler le contenu

Autant pour le 1er, vu qu'ils savent qu'il y a au moins 1 maudit, je comprends.
Mais là? Je ne vois pas comment le 2e moine peut déduire qu'il a un point sur le front si celui qu'il voit ne s'est pas suicider... Ou plutot, je ne comprend pas pourquoi tous les autres moines (sans point) ne font pas la mm déduction.

Pas logique, donc.

Tant qu'on se limite à 2, la logique est présente (la généralisation à n+1 est un poil foireuse à formaliser, mais y a une logique malgré tout)

Spoiler: cliquez pour révéler le contenu

L'idée, c'est que chaque moine étant d'une même intelligence, ils supposent le raisonnement que feraient les autres à leur place.
Quand n=2, tous les moines voient 2 maudits, sauf les maudits eux-même qui pensent que n=1. Au deuxième jour, le maudit A constate que B ne s'est pas suicidé, c'est donc que B voit un autre maudit. A ne voyant pas d'autre maudit que B, il sait qu'il est le deuxième maudit. B suit le même raisonnement.

Si n=3, chaque maudit en verra 2, et pensera qu'ils leur faudra deux jours pour se découvrir. Au 3° jour, ils sauront qu'il y a en fait trois maudits, les deux autres et eux-même.


Etc.

[ChemicalStöf]

ouaip c'est ça.
Allez une dernière.


Le mauvais coup du roi aux 50 prisonniers

Le roi, dégouté que les 50 prisonniers ont gagné le jeu, a finalement décidé de ne pas les libérer tout de suite (quel enculé ce roi!!)
Il leur propose donc un second "jeu":
les 50 prisonniers sont mis en file indienne, chacun avec un bonnet sur la tête. Les bonnets sont blancs ou noirs, il y a donc 50 bonnets au total (1 sur la tête de chaque prisonnier), et pas forcément autant de blancs que de noirs.
Chaque prisonnier ne peut voir que les bonnets des prisonniers devant lui, et ne peut pas voir la couleur de son propre bonnet.
Les prisonniers seront intérogés un par un sur la couleur de leur propre bonnet, en partant de celui qui est tout derrière. Ceux qui donnent la bonne couleur de bonnet seront libérés. Les autres seront exécutés.
Avant d'enfiler les bonnets, les prisonniers peuvent se réunir un instant afin de définir une stratégie pour sauver un maximum d'entre eux.
Comment font-ils? Combien peuvent être sauvés?


C'est celle qui m'a donné le plus de fil à retordre

[tfoth]

Vu la simplicité, pas sûr que ce soit la solution optimale :

Spoiler: cliquez pour révéler le contenu

On suppose que chaque prisonnier entend les autres donner leur réponse.

Les 25 premiers prisonniers à être interrogés donnent chacun la couleur de celui qui est 25 rangs devant. Ces 25 prisonniers ont une chance sur deux de correspondre, l'espérance est donc à 12.5. Les 25 prisonniers suivant connaîtront leur couleur à coup sûr, et seront donc sauvés.

On obtient ainsi une espérance à 37.5 (au pire 25, au mieux 50)

[ChemicalStöf]

on peut faire beaucoup mieux objectif: 49 ou 50 sauvés.

[tfoth]

Je reprends l'énoncé :

1)Tirage aléatoire, il peut très bien y avoir 50 bonnets blancs, 50 bonnets noirs ou n'importe quelle autre proportion.
2)Les prisonniers répondent dans un ordre déterminé, de celui le plus en arrière à celui le plus en avant.
3)Lorsqu'il répond, chaque prisonnier ne peut dire que "blanc" ou "noir", sur un ton neutre et sans interruption/silence (sinon l'énigme est beaucoup trop simple). Une seule réponse est possible, pas d'interaction entre les prisonniers une fois le bonnet enfilé.
4)Chaque prisonnier connaît les éléments suivants :
a)La réponse donnée par les prisonniers derrière lui.
b)La couleur des bonnets des prisonniers devant lui.
c)La stratégie commune.


Pour moi, il manque un truc.

Spoiler: cliquez pour révéler le contenu

4)c) est invalidé par 2) et 3), les prisonniers ne pouvant fournir aucune indication autre que la réponse pour leur propre bonnet au moment où on leur demande.

Si on zappe 3) qui n'est pas dans l'énoncé de base, le prisonnier répond avec l'accent africain (ou chinois ou autre) si le bonnet devant est noir, normalement s'il est blanc par ex, c'est alors trivial, ce n'est plus de la logique mais de l'astuce.

4)a) et 4)b) sont inutiles si on considère 1)

[ChemicalStöf]

Ta compréhension de l'énoncé est la bonne.
Et non, il ne manque rien.
Une stratégie permet d'en sauver entre 49 et 50.

[tfoth]

Ça m'a énervé de ne pas trouver, du coup j'ai cherché sur le net, et il manquait en effet un détail capital dans ma compréhension de l'énoncé, qui le rendait insoluble tel que je l'avais formalisé (ton énoncé en revanche ne comporte aucune erreur), une formalisation corrigée étant :



0)Il y a un certain nombre de prisonniers, ici 50.
1)Tirage aléatoire, il peut très bien y avoir que des bonnets blancs, que des bonnets noirs ou n'importe quelle autre proportion.
2)Les prisonniers répondent dans un ordre déterminé, de celui le plus en arrière à celui le plus en avant.
3)Lorsqu'il répond, chaque prisonnier ne peut dire que "blanc" ou "noir", sur un ton neutre et sans interruption/silence (sinon l'énigme est beaucoup trop simple). Une seule réponse est possible, pas d'interaction entre les prisonniers une fois le bonnet enfilé.
4)Chaque prisonnier connaît les éléments suivants :
a)La réponse donnée par les prisonniers derrière lui.
b)La couleur des bonnets des prisonniers devant lui.
c)La stratégie commune.

[JFM]

Ce topic m'intéresse, mais les passages en spoilers ne s'affichent pas chez moi. Pourrait-on avoir les solutions d'une autre façon, en les écrivant en blanc par exemple ?

[ChemicalStöf]

OK, mais seulement quand tu bloqueras. Faut chercher un peu, être persévérant!

tfoth> Alala, je te pensais plus fier que ça! Tu aurais du persévérer C'est dommage d'abandonner si vite!

[tfoth]

La raison de mon abandon est très simple :

Spoiler: cliquez pour révéler le contenu

J'ai une forte tendance à penser de façon "récursive", ce qui ici était complètement à côté de la plaque. Il aurait fallu que je prenne en compte la condition 0), à savoir qu'on sait combien il y a de prisonniers au total, bref que le calcul se faisait en fonction. Voulant absolument résoudre ceci de façon récursive, avec une information qui se propage à un nombre potentiellement infini de prisonniers, je ne pouvais simplement pas trouver.

C'est d'autant plus rageant que je connaissais finalement déjà cette énigme, en plus compliqué, et que je l'avais alors résolue =_=

[ChemicalStöf]

ah bah s'il suffisait d'appliquer la même logique à toutes les énigmes ça serait pas drôle
Moi aussi j'ai un peu la même tendance que toi, mais j'ai pas voulu abandonner et j'ai fini par trouver
D'ailleurs celle avec l'interrupteur a dû te poser le même problème