Canalblog
Editer l'article Suivre ce blog Administration + Créer mon blog
Publicité
La Vache En Liberté
Publicité
Visiteurs
Depuis la création 26 379
Newsletter
Archives
9 septembre 2022

Dans la salle des coffres…

Voir ma propre explication à la fin Luc Fricot

Félicitations! Vous faites parti des 100 chanceux qui vont participer à un nouveau jeu. Voici le principe: on remet à chacun d’entre vous un ticket portant un numéro unique -de 1 à 100- et une contremarque portant le même numéro que vous remettez au maître du jeu. Celui-ci s’éclipse et va dans la pièce d’à côté cacher ces 100 contremarques dans 100 coffres numérotés eux aussi de 1 à 100 (une seule contremarque par coffre) de façon aléatoire. Le défi est le suivant: chaque participant à tour de rôle va passer dans la salle des coffres et peut ouvrir 50 coffres pour y chercher sa contremarque (sans changer les contremarques ou les coffres de place).

impossible bet 1     

Dans l’histoire originale ce ne sont pas 100 joueurs, mais 100 prisonniers qui doivent retrouver leur contremarque-

S’il l’a trouve, il la montre au maître du jeu, puis sort par une porte dérobée en laissant la salle des coffres exactement dans le même état qu’à son arrivée. Et sans rien dire aux autres participants évidemment. C’est au joueur suivant d’entrer dans la salle des coffres pour y chercher à son tour sa contremarque parmi 50 coffres.
Si tous les participants trouvent leur contremarque, ils remportent tous un million d’euros. Mais si un seul échoue, personne ne gagne rien. Comment allez-vous vous y prendre pour maximiser vos chances de gagner?

Votre première réaction est sans doute de vous demander ce qui se passerait si chacun ouvrait 50 coffres au hasard, sans aucune stratégie concertée. Chaque joueur aurait alors une chance sur deux de trouver sa contremarque. La probabilité que deux joueurs trouvent tous deux leur contremarque est de ½*½=¼; pour trois joueurs elle est de 1/8 etc. Pour 100 joueurs elle n’est plus que de (½)100, c’est à dire moins d’une chance sur 1030 (1 000 000 000 000 000 000 000 000 000 000)! Le Loto, à côté, ressemble à un placement de bon père de famille! Il vous faut trouver une stratégie un peu plus rusée…

Bon OK, alors voici la solution:

La bonne stratégie consiste pour chacun des participants à ouvrir le coffre ayant le même numéro que sa contremarque. Par exemple si vous avez le numéro 63, vous allez ouvrir le coffre 63. Si vous y trouvez la contremarque 63 c’est gagné pour vous. Si vous trouvez un autre numéro, par exemple la contremarque n°27, vous allez ouvrir le coffre n°27 et ainsi de suite 50 fois au maximum:

impossible bet 4

Si avant d’avoir ouvert 50 coffres vous êtes renvoyé sur un coffre que vous avez déjà ouvert c’est gagné! En effet le dernier coffre qui vous renvoie sur vos pas contient la contremarque cherchée (la 63 dans notre exemple) car une même contremarque ne se répète jamais dans deux coffres différents:

 

+impossible bet 5

Combinaison avec 2 boucles de longueur 3 et une boucle de longueur 2.

En suivant cette méthode, un joueur gagne si et seulement si le premier coffre qu’il ouvre correspond à une boucle de moins de 50 coffres. Vous suivez toujours? Si les contremarques sont rangées dans les coffres de sorte qu’il n’existe aucune boucle de plus de 50 coffres, alors tout le monde trouve sa contremarque à coup sûr et le pari est gagné. La probabilité que ce soit le cas est de 31%: la stratégie est donc payante dans un peu moins d’un cas sur trois! C’est quand même bien mieux qu’une chance sur 1030, non?

La solution en vidéo (toujours sur la chaine de Minutes physics):

 

 

Pour les dingues que le détail du calcul intéresse, le voici:

La méthode consiste à calculer la probabilité pour qu’il y en ait exactement une boucle de longueur k supérieure à 50 (comme toutes les boucles sont disjointes, il ne peut y en avoir deux): c’est la probabilité que tous les participants perdent en suivant la stratégie proposée.
Il y a façons de choisir les k coffres parmi 100 qui formeront la grande boucle. Peu importe l’ordre dans lequel on les choisikKKt.

Une fois ces coffres choisis, il faut y placer les contremarques associées de sorte qu’elles forment une boucle de longueur exactement égale à k: il y a (k-1)! façons de procéder et un schéma vaut mieux qu’une longue explication:

Impossible bet dénombrement

Pour ranger k contremarques dans n coffres selon une permutation circulaire,
– on commence par le coffre 1: on a k-1 choix de contremarques (de la n°2 à la n°k)
– si on a mis la contremarque p dans le coffre 1, on n’a plus que k-2 choix de contremarques à mettre dans le coffret p (toutes sauf la n°1 et la n°k),
– On continue ainsi de suite jusqu’au dernier coffre où l’on n’a plus le choix de la contremarque.
– A la fin on a (k-1)(k-2)…3*2=(k-1)! combinaisons possibles.

 

Reste à arranger les 100-k contremarques restantes dans les 100-k coffres restant. Il y a (100-k)! façons de procéder (l’ordre des rangements compte).

Au total on a donc arrangements possibles pour une boucle de longueur k.

Récapitulons: il y a façons d’obtenir une boucle de longueur k parmi les 100! combinaisons possibles, soit une probabilité de 1/k. Regardez comme c’est étonnant: cette probabilité ne dépend que de la longueur de la boucle mais pas du nombre total de coffres! Bon ok, vous n’êtes pas extatique devant ce résultat, passons…

La stratégie proposée est gagnante s’il n’y a ni boucle de 51 coffres, ni boucle de 52 coffres etc. ni boucle de 100 coffres. La probabilité de gagner vaut donc . Environ 31% de chances de gagner…

 Sources: 
L’énigme originale: « 100 prisoners problem »

 Bon, pour expliquer tout ça, le plus simplement et concrètement possible, je vais minimiser les variables : 4 joueurs, 4 coffres, choix de 2 coffres pour chaque joueur, soit 4 fois une chance sur deux.
 Sans stratégie, il y a donc une chance sur seize (2 puissance 4) de tout gagner.
 Avec la stratègie decrite précèdemment, tout se passe comme si l''énoncé du jeu n'etait plus le mème (plus de tirage au sort), et se réduit à la répartition des étiquettes (1 à 4) dans les 4 coffres.
 Il y a 24 ( = factorielle 4 = 4! = 4*3*2*1 ) combinaisons possibles, dont 10 gagnantes. Soit 1/2.4 chances de gagner.
 Evidemment, si celui qui met les etiquettes, choisit  sciemment une des 14 combinaisons perdantes, aucune stratégie ne fera mieux que 1/16 chances de gagner. (Luc  Fricot)

 

D’autres énigmes

U-ne énigme gourmande: comment couper en deux parties égales un gâteau rectangulaire dont un gourmand aurait déjà --mangé une part rectangulaire elle-aussi:

-Petite énigme: vous avez les yeux bandés et devant vous un plateau d’Otello dont on vous indique qu’il contient 54 pions tournés face blanche et 10 pions tournés face noire. Votre mission: en faire deux tas contenant le même nombre de pions tournés face noire… sans retirer votre bandeau bien sûr.

 

La boucle impossible (en vidéo)

Publicité
Publicité
Commentaires
Publicité