Petites enigmes > Réponse Sciences sujet

Emile Loir a écrit :

> S'ils sont répartis aléatoirement pour de vrai, comme Gâterie a dit, c'est de l'ordre de 2/3
> (je crois que j'avais calculé 61%?)

Note bien que mon "2/3" est une estimation rapide quand on a pas envie (ou le temps) de faire le calcul, et bien assez efficace dans le contexte d'un jeu de rôle (peut-être pas tout à fait assez efficace dans le cadre d'un jeu compétitif - je sais pas, je suis pas joueur pro, c'est eux qui savent avec quelle incertitude ils doivent évaluer les probas). Ton 61% est sans doute plus juste (j'ai toujours la flemme de faire le calcul).


> Gâterie a écrit :
>
> > Question subsidiaire : est-il possible de créer une stratégie qui a moins de chance
> > de réussir que "chacun dit un nombre au hasard" ?
>
> Si les nombre sont répartis de manière suffisamment aléatoire (et particulièrement, si chaque
> numéro est indépendant des autres) je ne pense pas.
>
> T'as toujours au moins une chance sur 100 de tomber sur le bon nombre. (Sauf si on suppose
> que tu peux répondre autre chose qu'un nombre entier entre 1 et 100. Genre "bleu"
> ou "pi").

Justement, tu raisonnes comme je raisonnais au début sur la question (quand je pensais que c'était pas possible) : chacun a une chance sur 100 de répondre le bon nombre, la connaissance des autres nombres ne fournit aucune information sur le nombre qu'un prisonnier a.

Or, pour résoudre, on met en commun les infos de façon détourné. Au final on fait en sorte qu'exactement un prisonnier ait le bon résultat : chaque prisonnier a donc toujours 1% de chance d'avoir le bon résultat, mais on a cassé l'indépendance entre leur chance de succès grâce à la stratégie globale : P(tout le monde échoue) n'est plus égal à Prod_i (P(le prisonnier i échoue)) mais à 0.

La question est donc : est-il possible de déformer ces probabilités dans l'autre sens ? De faire en sorte que P(tout le monde échoue) soit cette fois plus grand que Prod_i (P(le prisonnier i échoue)) ?


... La réponse est oui, quand on raisonne à 2 prisonniers :

En répondant au hasard, chacun a 1 chance sur 2 de se planter, et donc au total 1/4 que tout le monde se plante. Considérons la stratégie suivante : chaque prisonnier donne le numéro qu'il voit sur l'autre prisonnier. Résultats :
* [1, 1] : la première personne répond 1, la seconde 1, gagné !
* [1, 2] : la première personne répond 2, la seconde 1, perdu :/
* [2, 1] : la première personne répond 1, la seconde 2, perdu :/
* [2, 2] : la première personne répond 2, la seconde 2, gagné !
Soit une chance sur deux de perdre, plus qu'en répondant au hasard.

... Comme on le voit, ici le pricipe est inverse de la stratégie gagnante : au lieu de faire en sorte qu'un unique prisonnier gagne, on fait en sorte qu'ils gagnent tous ensemble.

Du coup, quelle est la stratégie la moins efficace, et sa probabilité de gagner quand même ? (Il me semble qu'on peut minorer ce nombre par 1/(nombre de prisonnier) pour des raisons de probabilité : P(le prisonnier i gagne) doit rester égal à 1/n. Je subodore qu'il est possible d'atteindre ce 1/n : il s'agit de faire en sorte que P(le prisonnier i gagne) = P(tous les prisonniers gagnent)).



> Oui, ça présuppose que les numéros sont répartis aléatoirement. Cela-dit, c'est pas absurde
> comme notion. Si t'as 20 fois le numéro 5, c'est pas aberrant de se dire "y a ptêt une
> chance que moi aussi j'ai le numéro 5", et d'adapter la stratégie en conséquence.

Intuition : tu te trompes.

Une des intuition que j'ai eu pour trouver ma solution en force brute (avec 3 prisonniers), c'est "si tous les nombres sont égaux, alors tous les prisonniers doivent donner un nombre différent". Je suis absolument incapable de démontrer cette intuition - elle m'est venue pour des raisons de symétrie (la situation "tout le monde a le même nombre" est la situation la plus symétrique possible en entrée, la réponse "tout le monde donne un nombre différent" est la réponse la plus symétrique possible - sachant que, comme expliqué plus haut, il ne faut jamais que deux prisonniers gagnent en même temps pour assurer une victoire globale automatique). Cf aussi le cas à deux prisonniers (en répondant le truc qu'ils voient, il minimisent leur chance de victoire).

Mais je répète, c'est juste une intuition que tu te trompes. Une intuition éclairée, mais une intuition, rien de plus.