L'énigme la plus difficile au monde

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 :slight_smile:

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 :slight_smile:

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é :wink:

Et j’aime aussi pouvoir échanger autour de l’énigme et sa solution :slight_smile:

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.

Mon schéma étant la nuts @pierrolf :smiley:

1 « J'aime »

@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

C’est pourtant le cas, cf les explications déjà données.
A 2N joueurs il peut y avoir un seul cycle >N or le switch permet de le couper en 2.
Donc on fera toujours du 100% avec un switch.

1 « J'aime »

c’est bien ca dont je doute :slight_smile: je dis pas que c’est impossible mais ca m’étonne beaucoup, il faudra que je pose les math dessus quand j’aurais le temps. Le résultat de ce jeu est tellement contre intuitif qu’il peut encore me surprendre 10 ans après !

Nan mais il faut que tu regardes mon dessin…

J’ai pris une feuille exprès et tout…

Si t’as un doute imprime-le, amène-le partout où tu vas et tu vas tilter !

C’est juste pas possible de faire tenir 2 cycles > N avec 2 N élements.

C’est comme découper 2 morceaux de plus de 1 mètre de long dans une planche de 2 mètres de long… ^^

1 « J'aime »

tu coupes dans la longeur :smile:

2 « J'aime »

Pour ton problème c’est le nombre de cartes (52) qui compte, pas le nombre de joueurs (91000 et quelques…) mais on avait compris l’idée…

1 « J'aime »

@greg31150 ton schéma ne m’a pas convaincu (je suis pas très schéma)

pour moi il existe N! distributions

N-1! distributions circulaires

obligatoirement un cycle de taille N

Svp quelqu’un pour les abattre ces barbares, ils parlent une langue bizarre je les sens pas :smile: