Et comme ça ?

Draziel a écrit :

> Et c'est là que je réalise que la question est "les 3 meilleurs" et pas "les
> 3 meilleurs dans l'ordre" :p (si c'est ça, je n'ai pas de solution)

Mais si, en y réfléchissant 2 min de plus, tu verras que tu connais l'ordre ! Bravo !

So Alive a écrit :

> Mais si, en y réfléchissant 2 min de plus, tu verras que tu connais l'ordre ! Bravo !

Effectivement, A est premier, j'étais fatigué au moment où j'ai écris tout ça c'est évident pourtant :D merci !

Jeu à deux prisonniers : on leur donne une grille avec n cases, et une pièce sur chaque case. Chaque pièce peut être sur le côté pile ou le côté face sans distinction.

Sous la grille, une des cases contient une clé. Le prisonnier A sait quelle est cette case, le prisonnier B doit le deviner. Pour l'aide, le prisonnier A doit retourner exactement une pièce, puis le prisonnier B, en voyant le plateau doit deviner où est la clé. Question 1 : est-ce possible ? Question 2 : si oui, comment ?

Uncurieux a écrit :



Le prisonnier B ne voit pas quelle pièce le prisonnier A a retourné? Il voit juste le plateau changé?
Il y a une concertation préalable?

J'ai du mal à voir l'enjeu de l'énigme, parce que je ne vois pas à quel moment un plan peut être établi.

Par exemple s'il y a concertation préalable et que le prisonnier B voit la pièce retournée, il suffit de dire avant "je retourne la pièce où se trouve la clé". Ou "Je retourne la pièce à droite de la clé" s'il est interdit de retourne la pièce avec la clé. C'est en tous cas complètement trivial.
S'il n'y a pas de concertation préalable, c'est du pifomètre.
S'il y a concertation préalable et que le prisonnier B ne voit pas la pièce retournée, il y a peut-être une astuce, mais je ne perçois pas comment le prisonnier B peut savoir quelle pièce a été retournée (puisqu'a priori le plateau est aléatoire).

Liz Euse a écrit :

> 1/ Le prisonnier B ne voit pas quelle pièce le prisonnier A a retourné? 2/ Il voit juste le plateau changé? 3/ Il y a une concertation préalable?

1 Non
2 Oui
3 Oui

> S'il y a concertation préalable et que le prisonnier B ne voit pas la pièce retournée, il y
> a peut-être une astuce, mais je ne perçois pas comment le prisonnier B peut savoir quelle pièce
> a été retournée (puisqu'a priori le plateau est aléatoire).

Tu peux essayer d'y réfléchir avec deux cases, pour commencer. Malheureusement, ça ne se généralise pas facilement ensuite, mais tu devrais assez facilement établir que c'est faisable avec deux cases.

Avec deux cases c'est évident, mais c'est dû au fait que tu changes n-1 cases.
Si tu pouvais changer deux cases sur trois (ou 99 sur 100) par exemple, tu aurais la même facilité, à mon avis.

Je suis pas certain que ce soit possible pour 3 cases. Il est impossible d'avoir un mappage unique.

Supposons que tu aies un plateau avec toutes les pièces côté pile :
P P P
Tu peux obtenir trois plateaux différents :

P P F
P F P
F P P

Tu vas les attribuer à une issue différente.

P P F veut dire que c'est la case 1 qui a la clé
P F P veut dire que c'est la case 2 qui a la clé
F P P veut dire que c'est la case 3 qui a la clé

Notons que c'est complètement arbitraire.

Si le plateau est originellement :
F P F
On peut obtenir trois plateaux différents :
F P P (= case 3 a la clé)
F F F
P P F (= case 1 a la clé)

On en déduit que F F F doit représenter "Case 2 a la clé".

Si le plateau est originellement :
F F P

On peut obtenir trois plateaux différents :
F P P (= case 3 a la clé)
P F P (= case 2 a la clé)
F F F

On en déduit que F F F doit représenter "Case 1 a la clé".


Du coup, on note que F F F est ambigu et peut représenter deux choses différentes.

Il est donc nécessaire de pouvoir déterminer quelle pièce a été retournée pour savoir de quel "F F F" il s'agit.
Or, si on est capable de déterminer quelle pièce a été retournée, on en revient au fait qu'il suffit de retourner la pièce sous laquelle la clé se cache.


Toutefois, il est impossible de savoir, en regardant un plateau donné, quelle pièce a été retournée. Il s'agit donc d'une énigme où il y a une astuce rigolotte, mais tordue et pas très intéressante (du genre "Toutes les autres pièces sont parfaitement centrées sauf celle que tu retournes que tu mets tout à droite de la case, HA!").
Ou alors, le n doit être >3. Mais je suis convaincu qu'un argument similaire à celui que j'ai établi peut être construit pour d'autres n. Il y a probablement une histoire de dénombrement astucieux qui montre qu'il y a toujours par nécessité des ambiguités.

Liz Euse a écrit :

Ton analyse pour 2 et 3 cases est tout à fait correcte, bravo ! Effectivement c'est impossible avec 3 cases, et tu le démontres bien !

> Toutefois, il est impossible de savoir, en regardant un plateau donné, quelle pièce a été retournée.

Non, mais ce n'est pas l'objectif ! L'objectif n'est pas de trouver quelle pièce a été retournée, mais quelle case contient la clé. Tu notes qu'avec 2 cases non plus, on ne sait pas quelle pièce a été retournée, et ce n'est pas un problème.

> Il s'agit donc d'une énigme où il y a une astuce rigolotte, mais tordue et pas très intéressante
> (du genre "Toutes les autres pièces sont parfaitement centrées sauf celle que tu retournes
> que tu mets tout à droite de la case, HA!").

Oh, ce serait grossier de ma part. Si tu cherches dans mes enigmes précédentes (que j'ai postées sous le pseudo So Alive), tu verras que je n'utilise jamais ce genre d'astuces.

> Ou alors, le n doit être >3. Mais je suis convaincu qu'un argument similaire à celui que
> j'ai établi peut être construit pour d'autres n. Il y a probablement une histoire de dénombrement
> astucieux qui montre qu'il y a toujours par nécessité des ambiguités.

En fait, il y a des 'n' pour lesquels ça marche, et des 'n' pour lesquels ça ne marche pas (jusque là, je ne t'apprends rien, tu sais que 2 et 3 sont des exemples). Sans donner la solution, je rajoute qu'il existe une infinité de n dans les deux catégories, et il y a un critère simple pour savoir si un n est dans l'une ou l'autre. On peut dériver de ta démonstration une démonstration pour tous les cas impossibles, mais je préfère te laisser chercher encore un peu si tu veux bien, tu as déjà beaucoup avancé ! Si tu bloques, dis-le moi et je rédigerai un bout de piste (et sinon, au plaisir de te lire !).

Petite indication : imaginons qu'il y a 4 cases qu'on va astucieusement baptiser 00, 01, 10 et 11. On peut faire des remarques intéressantes sur le XOR des cases pour lesquelles la pièce est sur le côté pile.

Je suis curieux de voir la résolution de cette énigme si quelqu'un y parvient, ça m'apprendra des choses, car là même avec l'indice je ne sais même pas comment commencer !