Gâterie a écrit :



Surtout quand on sait que juste avoir tout le monde qui dit le même nombre donne une très bonne chance d'être libéré

Gâterie a écrit :



Hic.
On imagine un monde où les 100 prisonniers ont tous le chiffre 1, le premier gars passe donc g(1) = 1 - 99 = -98, c'est ce qu'il doit annoncer ?



Il y a deux choses ici : tu as seulement prouvé que g(m) = f(m), ça reste un cas très particulier. De plus ce cas n'a plus aucun sens dès lors que tu as la m = sum(f(n)) > 100, c'est à dire à partir du moment où l'un des prisionniers a un numéro supérieur ou égal à deux. Ca n'a plus de sens car tu définis tes fonctions à partir de [[1,100]] et on peut avoir m > 100 dès, quelque soit n, f(n) > 2, donc f(m) n'est pas définie.

Une solution où 99% des prisonniers s'en sortent serait comme t'essaies de le mentionner, le premier prisonnier se sacrifie en annonçant la somme des 99 autres nombres qu'il voit, puis les 99 concernés excluent celui qui s'est sacrifié et font nombre annoncé moins les 98 autres nombres que je vois.
Une solution où 100% des prisionniers s'en sortent serait le cas précédent + s'ils ont le droit d'ajouter une seconde information du type "mon numéro est xxx, et la somme des prisonnier est yyy"

Emile Loir a écrit :



Pas sur, vu que "(on peut donner le même à plusieurs personnes)", dans la mesure qu'on ne sait pas à quel point un même nombre peut être donné plusieurs fois, il y a toujours des risques incalculables que le numéro choisit ne soit juste jamais cité...

Emile Loir a écrit :

> Gâterie a écrit :
>
>
>
> Surtout quand on sait que juste avoir tout le monde qui dit le même nombre donne une très bonne
> chance d'être libéré

A peu près 2 chance sur 3.




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" ?


O. a écrit :

> On imagine un monde où les 100 prisonniers ont tous le chiffre 1, le premier gars passe donc
> g(1) = 1 - 99 = -98, c'est ce qu'il doit annoncer ?

2.

Un calcul modulo 100 signifie, pour simplifier, que l'on peut ajouter ou retirer 100 au résultat (avec pour but d'obtenir un résultat entre 1 et 100) (en vrai le but est d'obtenir un résultat entre 0 et 99, mais j'ai précisé qu'un "0" devait se lire comme un "100"). Pour faire encore plus simple (et partiellement faux), à chaque opération on ne garde que les deux derniers chiffres du résultat.

> Il y a deux choses ici : tu as seulement prouvé que g(m) = f(m), ça reste un cas très particulier.

J'ai montré plus précisément que pour tout f : [1,100] -> [1,100], il existe m tel que g(m) = f(m). Ce qui est le résultat attendu. (J'aurais pu écrire g_f(n) ou g(f, n) à la place de g pour mettre en valeur la dépendance de g par rapport à f pour plus de clarté). Et il est vrai, ma démonstration présuppose pas mal de choses sur les calculs modulo 100 (en gros, toutes les petites propriétés qui garantissent qu'opérer modulo 100 a du sens), mais je voulais éviter de faire un cours sur Z/nZ pour éviter de faire un post imbitable.

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.

Draziel a écrit :



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.
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%?)

Gâterie a écrit :



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").

O. a écrit :



Ben c'est pas possible. C'est soit tout le monde, soit personne.
Cela-dit, je suis curieux de connaître la "vraie" solution, si ce que dit Gâterie n'est pas la solution recherchée.

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.



___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.

Ok, je vois.
Tu peux effectivement avoir une méthode suboptimale qui tournera aux alentours de 40% de réussite, en copiant ce que tu as fait avec deux joueurs.

Tu groupes les participants deux par deux et ils doivent dire le numéro de l'autre. Vu que la seule possibilité pour que l'un des deux gagne est que les deux aient le même numéro, ça réduit la possibilité de gagner. Si les participants sont en nombre impair, y en a un qui dit un nombre aléatoire. Ca doit augmenter un peu le taux de réussite, mais sûrement pas significativement.
Je suis pas certain qu'il soit possible de faire "mieux". Je ne vois pas comment forcer plus de 2 joueurs à partager le même nombre.


Je comprends pas ce que tu veux dire.
Tu veux dire que si tout le monde a le même numéro, alors la stratégie la plus efficace est de tous donner un numéro différent?

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.

On est bien d'accord qu'il s'agit d'un cas particulier et que c'est pas une stratégie viable toute seule. Par exemple s'il y a 6 cinq et 6 sept et que le reste est faible, je suis pas certain que ce soit viable (les "cinq" verront plus de sept et les "sept" verront plus de cinq). Il s'agit réellement d'une stratégie alternative quand un nombre est très nettement en supériorité numérique (sans que ce soit nécessairement tout le monde. Même 20%, s'il n'y a pas d'autres nombre en concurrence, c'est valable).


Ah bon? Pourquoi?
Même dans ta stratégie à 100%, je ne suis pas convaincu que la solution soit unique.

Gâterie a écrit :

D'ac, j'avais zappé ta petite phrase sur le modulo 100.

Tu peux aussi écrire directement g(n) = n - sum(nombres qu'il voit sur les autres prisonniers) % (ou mod) 100, ça irait plus vite et ça permettrait d'éviter ce genre de confusion.

Gâterie a écrit :

> J'ai trouvé une solution

Bravo ! Et c'est cool de voir du monde sur ce topic.

Je précise à tout hasard qu'il n'y avait aucune considération de probabilité dans l'énoncé, entre autres parce que la distribution des valeurs sur les chapeaux n'est pas connue. On aurait pu d'ailleurs supposer que les numéros sont attribués en fonction de la stratégie choisie de manière à piéger les prisonniers. La notion de proba reste un outil intéressant quand même (par exemple, si on pouvait montrer que la probabilité de se planter est strictement positive quand la distribution des nombres est uniforme, alors on aurait répondu). Il y a des démonstrations vraiment cools qui utilisent des raisonnements de ce genre.

Cette histoire de "dé-indépendantiser" les probabilités s'applique dans d'autres énigmes, par exemple :
« 100 personnes ont le droit de se concerter puis vont être isolées dans des cellules. Chacune à tour de rôle sera emmenée dans une pièce contenant 100 tiroirs. Chaque tiroir contient le nom d'une personne différente, et chaque personne peut ouvrir 50 tiroirs et doit trouver son nom. Si une personne ne trouve pas son nom, tout le monde meurt. Comment maximiser la probabilité de survivre, peut-on avoir mieux que 1/(2^100) ? »

Ici, la notion de proba est pertinente si on considère que l'univers est la permutation initiale des tiroirs. Et il devient très facile d'avoir une stratégie qui fait moins bien que le hasard.

Il reste aussi celle-ci pour laquelle personne n'a proposé de réponse.

O. a écrit :

> Tu peux aussi écrire directement g(n) = n - sum(nombres qu'il voit sur les autres prisonniers)
> % (ou mod) 100, ça irait plus vite et ça permettrait d'éviter ce genre de confusion.

Je ne suis pas d'accord. Tu as supposé que les nombres manipulés étaient des entiers. La phrase de Gâterie précisait qu'il ne manipulait plus des entiers mais des éléments de ℤ/100ℤ, et avec les opérations usuelles, ses égalités sont du coup correctes sans besoin d'alourdir les notations.

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.

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.