@petiteglise, @volor était toujours sur les threads d’énigme, c’est quelqu’un que tu connais ?
(Je crois me souvenir qu’il s’agit aussi d’un joueur d’échecs non ?)
Salut @petiteglise,
comme indiqué en MP et précédemment dans ce sujet, l’énoncé ne permet pas de se retrouver dans les conditions du problème des 100 prisonniers.
Pour cela, il faudrait 52 joueurs et 52 cartes uniques communiquées avant.
Or dans l’énoncé, chacun tire une carte avec remise.
Il ne s’agit donc plus de permutations et la solution ne peut pas se modéliser de la même manière.
Par ailleurs, tu peux augmenter le nombre de joueurs mais il faut que le nombre de cartes à retournées soit la moitié du nombre de joueurs pour que les chances de gagner restent les mêmes.
Explications en français : Enigme Cent prisonniers @ Prise2Tete
Salut @yvan161,
Augmenter le nombre de joueurs ne changent rien du tout.
Une fois que l’on est dans une stratégie “gagnante” (ou une configuration gagnante pour une stratégie donnée), qu’il y ait 26 joueurs qui jouent ou bien 91000 ou plus ne changent rien.
Si tu préfères, une fois que 26 joueurs ont gagnés en appliquant la même stratégie, tu peux faire passer autant de joueurs derrière avec cette stratégie, ça gagnera.
Pour tes autres remarques, j’ai pas eu le temps de regarder, @petiteglise te répondra ^^
Tu as regardé ma solution ?
Je l’ai écrite indépendamment du pbm des prisonniers…
Peux-tu me dire ce qui te chiffonne dans mes explications en oubliant totalement le lien avec le problème des prisonniers ?
OK j’ai mal formulé.
Oui que l’on soit 52 ou plus (mais pas 26+) ne change pas les chances de survie (s’il n’y avait pas remise) mais par contre la généralisation à 30,68% ne s’applique qu’avec 2n joueurs ouvrant n boites.
Je ne sais pas comment @petiteglise calcule 32% d’autant qu’à nouveau le point fondamental est que la carte à tirer par les joueurs est avec remise.
Oui j’ai regardé l’image de ta solution mais c’est difficile à lire surtout sur téléphone 
Pourrais-tu la mettre au format littéral que je regarde ça de plus près.
Là tout de suite non je peux pas.
Si je l’ai écrite comme ça c’est parce que c’était le plus simple pour faire les schémas etc.
Peut-être que tu peux télécharger l’image sur ton tel et ensuite la regarder en zoomant ou sinon attendre d’avoir un PC dispo sous la main.
Je n’ai pas vraiment regardé le pbm des prisonniers donc je ne sais pas ce que tu entends par “avec remise”.
Il ne s’agit pas d’un pbm de boule dans un urne etc.
En fait, oublie le problème des 32%.
Regarde la version 2 du pbm de petiteglise (à savoir qu’il suffit que joueur 1 switche 2 cartes pour que tout le monde win avec la même strat’)
C’est ce problème que je résous dans mon ‘image’.
Une fois que le problème 2 est résolu, bah le problème 1 en découle (même si je ne me suis pas penché sur le calcul des 32%).
Ce qui est certain en tout cas c’est qu’une fois que t’as une configuration OK (32% de chance initialement selon petite église et 100% si on switche cf. mes explications) bah tout le monde gagne en appliquant le même algo.
Et c’est ça qui est intéressant, le calcul des 32% osef (enfin jmef ^^ perso demande @petiteglise plus de détails)
Le problème est bien strictement équivalent à 52 joueurs qui doivent trouver chacun une des 52 cartes, vu que tous ceux qui vont avoir l’As de pique par exemple, vont retourner exactement les mêmes cartes, qu’ils soient 1 ou 1 million ne change rien.
La formule pour qu’il n’y ait pas de cycle de longueur >26 sur 52 est bien expliquée dans le lien wiki que j’ai donné plus haut : proba de win = 1 - (1/52 + 1/51 +… 1/27) soit environ 32%
1 « J'aime »
OK donc les permutations et l’analogie s’effectuent sur la numérotation des cartes et pas sur la carte tirée.
La « remise » est sur la carte tirée mais effectivement, ça ne change pas l’algorithme.
“By starting with his own number, the prisoner guarantees he is on a sequence of boxes eventually containing his number. The only question is whether this sequence is longer than 50 boxes.”
On s’intéresse quand même au calcul car il faut que notre pari soit gagnant (>25%) au-delà d’avoir une stratégie qui optimise nos chances de survie.
Est-ce que la probabilité est la même si chacun a sa carte ou si elle est retirée à chaque fois ?
Intuitivement j’aurais tendance à dire quelle est supérieure avec remise puisqu’un joueur a des chances de retomber sur la même carte à succès que son prédécesseur qui a survécu donc ok pour la solution
Effectivement, les problèmes ne sont pas théoriquement équivalent, mais en pratique avec un si grand nombre de joueurs, ça l’est.
On pourrait imaginer un cycle de 51 cartes par exemple, et une carte isolée et que chacun des 91k+ académiciens tombe sur la carte isolée, mais bon… ça change rien au “environ 32%”. donc le bet est Ev+
Oui bien sûr.
Ce que je voulais dire par “osef” c’est qu’une fois qu’on a résolu le problème 2 (à savoir pouvoir avoir 100% de win avec un configuration particulière, ou “une stratégie adaptée pour une configuration donnée” ce qui revient au même),
Le reste (le calcul de la proba d’avoir un config OK) c’est juste du calcul et pour cela je fais confiance @petiteglise… car en réalité c’est juste une énigme hein ^^
Il va pas faire des calculs faux pour nous own
Après ça dépend de ce que tu aimes dans les Maths, moi j’aime plus le côté “challenge théorique” que les calculs.
A plus
Disons que tout m’intéresse dans une énigme, aussi bien le raisonnement pour trouver la solution que la justesse du calcul s’il y en a un voire la précision de l’énoncé 
Et j’aime aussi pouvoir échanger autour de l’énigme et sa solution
1 « J'aime »
@petiteglise la proba de succès au jeux tel que lu le propose est beaucoup trop complexe le fait de remettre la carte dans le paquet a chaque fois change trop de chose. Pour simplifier
si le joueur 1 réussit et que joueur 2 tire la meme carte que 1 sa proba de réussite est de 1 mais joueur trois aura une proba de réussite plus faible que si joueur 1 et 2 réussisse avec des cycles différents, etc etc, chaque fois que des joueurs réussissent successivement avec des cycles différents, le suivant a de plus en plus de chance d’avoir une proba de réussite de 1
la version 2 de ton jeux (un switch donne une proba de 1) est impossible je pense. Un exmple simplifié a 3 joueur et six numéro
joueur 1 2 3 4 5 6
boite 3 4 5 1 6 2
il me semble qu’un switch ne peut pas garantir la réussite
la proba individuelle ne change jamais, elle reste 1/2 , en revanche avec la stratégie optimale il existe beaucoup plus de cycle ou tout le monde trouve sa carte
Si, si, la version est bien correcte.
Dans ton exemple il suffit d’inverser 1 et 6 :
joueur 1 2 3 4 5 6
boite 3 4 5 1 6 2
->
boite 3 4 5 6 1 2
Et hop tout le monde trouve en 3 coups.
Je t’invite à relire les explications données sur le thread et le lien wiki.
Pour les probas, elles ne sont pas de 1/2 sauf pour le premier, ensuite elles tendent vite vers 1.
@petiteglise je connais le problème je l’ai étudié y’a quelques années (et je me fie pas trop a wiki y’a souvent des erreurs)
dans le contre exemple que tu donnes tu changes quand meme une variable hyper importante, c’est que le joueur 1 ne respecte pas la stratégie et ne commence pas par piocher la carte 1 (ok ca serait absurde de le faire en ayant la solution, mais ca lui donne le droit de dévier de la stratégie et ca change bcp de chose) et il me semble (je peux me tromper) que dans ce cas le N participant change la proba de succès si je rajoute une série miroir a ma première et double les participant ton switch fonctionne évidement plus, possible qu’il en existe un qui permettent d’éviter un cycle perdant mais je vois pas comment le prouver ni comment le déterminé sur un N grand
1 2 3 4 5 6 7 8 9 10 11 12
3 4 5 1 6 2 9 10 11 7 12 8
En fait quand je dis que la proba reste de 1/2 et que toi tu considère qu’elle augmente, c’est parce que on ne devrait pas s’intéressé a savoir si le jeux continue ou pas (et c’est la la “magie du truc”) il faudrait plutot penser a ce qu’il se passe s’ils jouaient simultanément. Evidement si on considère que le jeux ne continue qu’a condition que le premier ait validé son flip (et que le cycle du suivant soit gagnant) la proba augmente et tends vers 1 pour les suivants. SI on rajoute a l’énoncé " quel que soit le résultat le prisonnier ayant joué passe dans une autre pièce et tous les autres jouent a leur tour, le résultat final leur ait communiqué quand tout le monde a joué" la proba individuelle de trouvé est de 1/2
voila un tableau exhaustif pour 4 joueur et donc 4! (4x3x2 = 24) combinaison de distribution possible
1 1/2/3/4 1/1/1/1 gagné
2 1/2/4/3 1/1/1/1 gagné
3 1/3/2/4 1/1/1/1 gagné
4 1/3/4/2 1/X/X/X
5 1/4/2/3 1/X/X/X
6 1/4/3/2 1/1/1/1 gagné
7 2/1/3/4 1/1/1/1 gagné
8 2/1/4/3 1/1/1/1 gagné
9 2/3/1/4 X/X/X/1
10 2/3/4/1 X/X/X/X
11 2/4/1/3 X/X/X/X
12 2/4/3/1 X/X/1/X
13 3/1/2/4 X/X/X/1
14 3/1/4/2 X/X/X/X
15 3/2/1/4 1/1/1/1 gagné
16 3/2/4/1 X/1/X/X
17 3/4/1/2 1/1/1/1 gagné
18 3/4/2/1 X/X/X/X
19 4/1/2/3 X/X/X/X
20 4/1/3/2 X/X/1/X
21 4/2/1/3 X/1/X/X
22 4/2/3/1 1/1/1/1 gagné
23 4/3/1/2 X/X/X/X
24 4/3/2/1 1/1/1/1 gagné
individuellement et indépandement des résultats précédent les joueurs trouvent 50% du temps, par contre le groupe gagne 10 fois sur 24. Et jusqu’a ce que la science nous démontre le contraire, il n’y a pas de meilleure stratégie. En tout cas merci a @petiteglise d’avoir partagé ca sur PA c’est très intéressant
A 4 joueurs, on a bien p de win = 1 - (1/4+1/3) = 24/24 - (6/24+8/24) = 10/24, tout va bien.
Je comprends pas ce que tu dis à propos du joueur 1 : il tire la boite 1 (3) puis la 3 (5) et enfin la 5 (1).
Si le jeu continue dans tous les cas, alors la proba de trouver de chacun est bien de 1/2 pour tous, on est d’accord, ce qui ne change pas le fait que la proba que tout le monde trouve est d’environ 30% car les événements ne sont pas indépendants.
Oui je pensais que tu considérais que joueur 1 prenait la boite qu’il voulait (en sachant ou est la sienne), dans mon exemple ca matche effectivement (javais meme pas vérifié), ca ne change pas mon opinion que même si ca fonctionne sur certains cycle de carte et certaines distributions, impossible de garantir succés = 1 avec un seul switch sur any distribution
sinon pour le cas numéro 1 (sans switch) oui oui a 4 joueur on est largement au dessus de 30% et on restera a 30%+ meme a 50 ou 100 000 joueurs