Petites enigmes > Réponse Sciences sujet

Emile Loir a écrit :

> > il ne faut jamais que deux prisonniers gagnent en même temps pour assurer une victoire
> > globale automatique
> >
> Ah bon? Pourquoi?
> Même dans ta stratégie à 100%, je ne suis pas convaincu que la solution soit unique.

C'est une intuition que j'avais quand j'ai essayé de résoudre, c'est lié à une question de cardinalité mais je n'arrivais pas à le montrer ; lorsqu'on résout le cas à 3 prisonnier en force brute, c'est un truc qu'on voit apparaître, qui semble évident (on ne peut pas faire autrement) mais difficile à montrer. Avec la vision probabiliste, ça devient très simple à montrer.

@So Alive : parler de proba ici, c'est juste une façon alternative de parler de cardinaux ; il s'agit simplement de compter le nombre de configuration gagnante, et de diviser par le nombre de configuration. Il ne s'agit peut être pas de la probabilité réelle de gagner (si les interrogateurs adaptent les nombres à la stratégie etc), ça n'en reste pas moins une mesure de probabilité valable qui suit tous les théorèmes de proba.

Bref, avec une approche probabiliste, chaque prisonnier a 1% de chance de gagner ; pour la bête raison qu'il a toujours une configuration gagnante sur 100 (quoi que réponde le prisonnier 1 quand il ne voit que des 1, il y a 1 configuration où il gagne et 99 où il perd).

Maintenant, ce qui nous intéresse, c'est pas la chance de gagner de chaque prisonnier, mais la chance qu'au moins un prisonnier gagne :

P(prisonnier 1 gagne ou prisonnier 2 gagne ou ...) <= sum_i P(prisonnier i gagne) = sum_i (1%) = 1
(c'est pas une flèche mais un "inférieur ou égal")

Avec égalité si et seulement si les événements sont deux à deux disjoints, ie si et seulement si :
pour tout i et j, P(prisonnier i gagne et prisonnier j gagne) = 0
ie, une stratégie gagne à tous les coup si et seulement si elle ne fait jamais gagner deux prisonniers en même temps, qed.

@So alive : tout ça pour dire que les probas sont "juste" un outil dans ma trousse à outil, éclairant le problème sous un autre jour. J'ai "senti" qu'il fallait un unique gagnant par configuration, j'ai "senti" que c'était lié à un problème de cardinal, j'arrivais pas à le montrer (du moins, sans y passer des heures et au moins une dizaine de page). En prenant une approche probabiliste, ça m'est apparu comme une évidence de 5 lignes - parce que même si les proba discrètes ne sont qu'une reformulation des cardinaux et du dénombrement, on n'y raisonne pas exactement de la même façon, on n'y a pas la même façon d'appréhender le problème etc.


> Moi, je vois 99 personnes ayant le numéro 5, je me dis pas "Ok, je garde ma stratégie,
> et je dis un nombre fixé à l'avance". Direct, je dis 5. Si je suis le seul à pas avoir
> 5, c'est pas grave, logiquement les autres auront la présence d'esprit de dire 5 en voyant
> 98 numéros 5.

Justement, tu devrais garder ton nombre - et faire confiance aux autres prisonniers pour suivre la stratégie, ce qui va garantir que l'un des prisonnier va dire "5" dans le cas où le nombre que tu dois annoncer n'est pas celui que tu as.

Mais ta méthode peut peut-être se développer en une méthode qui a une bonne chance de succès et est simple à mettre en oeuvre - mais elle ne peut pas être développer en une stratégie qui gagne à tous les coups.

Le problème, à peu de prisonnier :

* à 4 prisonnier : si tu vois (2, 1, 1), alors il faut que tu réponde ton nombre ; parce que, si tu as toi aussi un "2" sur le front et que tout le monde répond le nombre qu'il voit le plus, alors tout le monde perd (ceux qui ont un 1 répondent "2", ceux qui ont un 2 répondent "1".

Si tu vois (1, 1, 1) et que tu est sensé répondre "2" : supposons que tu aies effectivement un 2 sur le front, alors les autres voient (2, 1, 1) - ils sont dans la situation juste au-dessus avant où ils ne faut surtout pas qu'ils répondent autre chose que leur nombre. Et dans ce cas ils perdent tous (puisque dans cette configuration c'est toi le seul gagnant). Il faut que tu répondes "2" pour garantir la victoire si tu as un 2 sur le front - et tu dois faire confiance aux autres pour appliquer la stratégie et gagner si tu as un 1 ou autre chose.

* A 5 prisonnier : si tu vois (1, 1, 2, 2), tu réponds quoi ? Mettons que tu vois (1, 1, 2, 3) ; si tu as un "2" sur le front, tu perds en répondant le nombre que tu vois le plus (ainsi que tous ceux qui le font), le dernier joueur voit (2, 1, 1, 2) et se plante qu'il réponde 1 ou 2. Il te faut donc suivre la stratégie.

Si tu vois (1, 1, 1, 2), que tu es sensé répondre "3" ; mettons que tu aies effectivement un 3, alors les autres sont dans la situation précédente où ils voient (1, 1, 2, 3) (et (1, 1, 1, 3)), en gros la même config que toi), situation où ils doivent suivre la stratégie, stratégie qui les fait perdre - puisque dans cette configuration c'est toi le seul gagnant.

Si tu vois (1, 1, 1, 1) et que tu es sensé répondre "2" ; mettons que tu aies effectivement un 2, les autres voient (1, 1, 1, 2) et sont dans la situation précédente où ils doivent répondre leur nombre, ce qui les fait perdre.


... Enfin je pense que tu vois le problème et comment ça se généralise en augmentant le nombre de prisonniers : il n'y a aucun moment où tu peut switcher de la stratégie gagnante à la stratégie "annoncer un nombre très présent" tout en préservant un 100 % de victoire.

En fait, quand j'y réfléchi, je me dis que partir de "si on ne voit que des X, alors on répond X" est la base pour concevoir une stratégie qui minimise les chance de victoire - parce que pour minimiser les chances de victoire il faut faire en sorte qu'un maximum de personne gagnent en même temps.