Dans la salle des coffres…

Impossible bet 2

« Je ne suis pas un numéro, je suis un homme libre! » dirait le Prisonnier

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…

Pour vous laisser le temps de réfléchir voici la version vidéo où j’ai découvert cette énigme rigolote:

La solution est juste derrière…

 

 

 

 

 

 

 

 
Vous ne voulez pas chercher encore un peu?

 

 

 

 

 

 

 

 
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 choisit.

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 »

D’autres énigmes dans ce blog:

Une é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)

Post navigation

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *