Énigme intéressante...

[invite21dfc132]

Bonjour à tous,

voici une jolie énigme assez sympa, la connaissez-vous ? Si oui, évitez de donner la réponse, et sinon, bon amusement...

Le Dr No a fait prisonnier 100 personnes. Ces personnes ont toutes un nom différent et il leur propose la chose suivante :

chaque nom est écrit sur un petit papier, et mis dans une boite différente. On a ainsi cent boites disposées dans une pièce. Chaque personne rentre alors à tour de rôle dans la pièce et ouvre 50 boites. La pièce est bien sûr remise en l'état entre chaque passage. Si l'une d'entre elles ne trouve pas son nom dans les boites qu'elle a ouvertes, toutes sont tuées. Par contre ils peuvent se concerter avant (sans que le Dr No écoute aux portes...).

Parmis eux, un mathématicien dit qu'il existe une méthode leur donnant environ 30% de chances de s'en sortir (ce qui est bien supérieur au (1/2)¹⁰⁰ du tirage aléatoire). Quelle est cette méthode ?

S'il y a un point pas clair, n'hésitez pas à poser des questions. À bientôt, cordialement,

Hibou
-----

[invite5c3ffe92]

ils remettent les boites dans le même ordre apres un passage?
la personne qui est passée peut en discuter avec les autres ? ou ne les revois qu'a la fin ?
en claire est ce que la premiere personne à passer peut dire à la deuxieme ou était son nom (le nom de la premiere)?

[invite21dfc132]

Les boites sont remises dans le même ordre. Par contre une fois passée, une personne ne peut plus voir ceux qui ne sont pas encore rentrés dans la salle.

[yat]

J'ai testé à la main une méthode qui me permet, avec 4 prisonniers et 2 boites, de gagner dans 10 cas sur 24 (ce qui est loin du 1/16 du tirage aléatoire). Je ne vois pas trop comment calculer ça sur 100 prisonniers, tu pourrais confirmer que tu obtiens comme moi avec 4 prisonniers et deux boites ?

[A voir en vidéo sur Futura]

[invite21dfc132]

Je te confirme qu'avec la bonne méthode (enfin celle qui donne un résultat d'environ 30% pour 100 personnes), les chances de gain dans le cas de 4 personnes et 2 boites ouvertes sont de 10 sur 24.

Explique ta méthode en LemonChiffon et on en discutera après .

En tout cas, c'est un bon début je pense, bravo

Hibou

[invite06fcc10b]

Je te confirme qu'avec la bonne méthode (enfin celle qui donne un résultat d'environ 30% pour 100 personnes), les chances de gain dans le cas de 4 personnes et 2 boites ouvertes sont de 10 sur 24.

Explique ta méthode en LemonChiffon et on en discutera après .

En tout cas, c'est un bon début je pense, bravo

Hibou

Here is my proposal:
Le 1er regarde les boites de numéro pair et les range par ordre alphabétique. Le 2ème prend les boites de numéro impair et les range aussi par ordre alphabétique. Ensuite, en fonction de son nom et en supposant qu'il y a une distribution à peu près homogène de la 1ère lettre des noms dans l'alphabet, chacun prend dans les 50 à gauche ou les 50 à droite. C'est ça ?

Quoique, à la réflexion, la proba est inférieure à 25% .... donc ça doit pas être ça.
Ou alors, on ne le fait qu'avec les boites paires ?

[yat]

Explique ta méthode en LemonChiffon et on en discutera après .

Allons-y alors.

Lors de la concertation les prisonniers s'attribuent des numéros et se mettent d'accord sur un protocole pour numéroter les boites. Chaque prisonnier va vers la boite qui porte son numéro, lit le nom qui est dedans et ouvre la boite qui porte le même numéro, ceci jusqu'à la 50ieme boite ou celle qui contient son nom. Du coup les seules situations d'échecs sont celles ou il y a un cycle de plus de 50 boites.

[invite06fcc10b]

Allons-y alors.

Lors de la concertation les prisonniers s'attribuent des numéros et se mettent d'accord sur un protocole pour numéroter les boites. Chaque prisonnier va vers la boite qui porte son numéro, lit le nom qui est dedans et ouvre la boite qui porte le même numéro, ceci jusqu'à la 50ieme boite ou celle qui contient son nom. Du coup les seules situations d'échecs sont celles ou il y a un cycle de plus de 50 boites.

Bien vu, mais je pense qu'il n'est pas besoin d'écrire sur les boîtes. Il suffit de ranger les boîtes dans le bon ordre, en laissant une place vide pour les noms qui n'ont pas été trouvés. Et les boîtes non encore vues sont mises à un autre endroit. Du coup, euh ... les chances sont de ... 50%, non ?
Car soit on va directement chercher sa boîte au bon endroit, soit on va dans le paquet de 50 qui reste et on est sûr de l'y trouver. Donc il n'y a que 1/2 de perdre pour le 1er qui rentre.
Non ?

Argyre

[yat]

Il suffit de ranger les boîtes dans le bon ordre, en laissant une place vide pour les noms qui n'ont pas été trouvés.

Enoncé : "La pièce est bien sûr remise en l'état entre chaque passage"

[invite21dfc132]

Bravo yat !

Ouais, Latex empêche l'utilisation de LemonChiffon, donc attention

 Cliquez pour afficher

Pour le calcul, je n'ai qu'une méthode pédestre. Mais allons-y :

Ce que nous devons savoir c'est que le fait de numéroter les boites et les gens implique que la relation boite/gens soit une permutation de n éléments. Yat parle de cycle. En effet, une permutation associe un numéro dans une liste de n numéro à un autre numéro dans une liste de n numéros, et ce de manière bijective. On peut représenter la permutation d'une autre manière : au lieux d'avoir deux listes de n numéros reliés, on n'en prend qu'une, de n numéros fléchés les uns aux autres : une et une seule flèche arrive à chaque numéro, et une et une seule en part. De cette manière, on peut dégager des circuits fermés, de taille plus ou moins grande.

Maintenant, soyons fous, prenons le cas de n personnes

Nombre total de permutations :



Parmis lesquelles (n-1)! permutations circulaires (un seul cycle de taille n).

Nombre de cas ou la permutation présente un cycle de grandeur p :



C'est à dire qu'on enlève n-p numéros au hasard (1e terme) qu'on permute n'importe comment (deuxième terme : toutes les permutations de n-p) et on fait un cycle avec les p numéros restant. Attention, cette expression n'est valables que si p est supérieur à n/2, dans ce cas il existe un et un seul cycle de taille p dans les permutations.

Maintenant faisons la somme pour p variant de n/2 à n, divisons par n!, le résultat est :



Où R est la probabilité que la permutation correspondant à la numérotation choisie par le mathématicien ne comporte pas de cycle plus grand que n/2. R tend vers ln(2) pour n grand puisque pour tout t réel strictement positif :

Voilà, encore bravo yat. Pour ceux qui ne voient pas, il faudra un dessin sans aucun doute, ce que je ne pourrai faire avant longtemps.

[invite06fcc10b]

Enoncé : "La pièce est bien sûr remise en l'état entre chaque passage"

Et il n'est pas question d'écrire sur les boîtes ... j'ai mal interprété tes propos.
Ok, fallait le trouver !
Le truc, c'est finalement de faire une hypothèse structurelle permettant de trouver à tous les coups la bonne boîte. Tout ça grâce aux permutations et à la bijection réalisée au préalable entre une boîte et un prisonnier.
Je retiens le problème, mais je pense qu'on peut simplifier à 4 personnes, sinon, ça va décourager les collègues.

A+,
Argyre

[invite21dfc132]

je pense qu'on peut simplifier à 4 personnes, sinon, ça va décourager les collègues

Bah non, justement, c'est ça qui est drôle, le côté complètement contre-intuitif du résultat : 30% contre un truc infinitésimal. Comme personne ne pense tout de suite à proposer un choix de boite qui dépend résultat sorti de la boite précédente, tout le monde en revient au calcul de la probabilité correspondant au hasard, ou à un crible méthodique qui donnera peut être (je dis bien peut-être, je n'ai pas fait le calcul) un résultat 100 fois meilleur, mais restera encore de l'ordre du pouillème (si vous me permettez cette approximation ).

Voilà, à bientôt donc, cordialement,

Hibou

[invite1a62f786]

Hein vous êtes bien bizarres dans votre manière de réfléchir.

S'il y a 100 boites, et que tu en ouvres 50, tu as une chance sur 2 de trouver ton nom.

Celui qui te suit a aussi une chance sur 2.

Celui d'après au aussi une chance sur 2.

C,est impossible, que sur les 100 personnes qui passent à tour de rôle, ayant chacun une chance sur 2, tombent tous sur la mauvaise.. lol

Donc tous sont libres, à coup sur

je ne reviens pas ici, donc :

###
pour ceux qui voudraient discuter de ce comcept bien simple avec moi lol

[SunnySky]

Freedom34: je crois que tu as mal compris la question: si une seule personne est malchanceuse et ne trouve pas son nom, toutes seront tuées...

Il y a donc une chance sur 2 que la première trouve son nom, une chance sur 4 que la première et la deuxième trouvent leurs noms...

Donc se fier au hasard, c'est courir au suicide presque assuré. D'où l'intérêt de l'énigme.

[invite528b0bef]

Bonjour, je viens écrire ici se que j'ai écris sur :
http://forums.futura-sciences.com/sh...d=1#post922351

Car je pense que c'est ici la vrai discution

Tu dit:

Une fois votre matricule découvert, ou la limite des 50 coffres atteinte, vous sortirez de la salle, et vous ne pourrez, par aucun moyen, communiquer avec les autres prisonniers.

Donc vola ma solution le premier prisonier va entrer et va ouvrir les coffre un apres l'autre dans l'ordre

Quand il ouvre le premier si c'est pas son N° il va crier Coffre N°1 porte le chiffre N°12 (car il n'a pas encore trouver sont N° et n'a pas atteint 50 coffres ) par exemple est continu juque a trouver sont N° ou atteindre les 50 coffres.

Le Prisonier N°2 va venir adméton que le Prisonier N°1 avais trouver le N°2 dans le coffre 30 il ne va pas ouvrir le coffre N°30 il va continuer la ou le prisonier N°1 a trouver sont N° et une fois qu'il arrive a 49 coffre il ouvre le coffre N°20 car il sais que c'est le bon puisque le Prisonier N°1 l'avais crier fort.

Et ainci de suite juque a la fin.

[invite21dfc132]

Bonjour,

Ceci :

vous ne pourrez, par aucun moyen, communiquer avec les autres prisonniers

invalide tout moyen de communication que pourraient inventer les prisonniers pour se donner des information, y compris celui-là :

Quand il ouvre le premier si c'est pas son N° il va crier Coffre N°1 porte le chiffre N°12 (car il n'a pas encore trouver sont N° et n'a pas atteint 50 coffres ) par exemple est continu juque a trouver sont N° ou atteindre les 50 coffres.

Désolé Olivier_34, mais ta solution n'est pas valable. D'autant que si c'était vraiment ça la solution, les chances de survie seraient de 50% exactement.

Bonne journée à tous, cordialement,

Hibou

[danyvio]

Pour avoir le provilège d'avoir lu une explication pédagogique de CoucouHibou en courrier privé, je confirme qu'il n'y a pas besoin (et d'ailleurs c'est exclu dans l'énoncé) de faire communiquer les prisonniers entrés dans la salle des coffres avec ceux restant en attente.
Mais : ils utilisent l'information des coffres qu'ils ouvrent !!!!! à savoir le n° lu dans chacun d'eux ..... c'est là le secret. Et c'est intellectuellement fabuleux !

[invited19460d1]

Bijour,
a-t-on le droit de changer les petits papiers de boites??
Si oui, je l'ai...

[danyvio]

Bijour,
a-t-on le droit de changer les petits papiers de boites??
Si oui, je l'ai...

Non : chaque fois qu'un prisonnier a "passé son test" tout est remis à l'état initial (voir énoncé). Tous les prisonniers introduits en salle des coffres sont confrontés à strictement la même configuration.

[invite44c43cc5]

depuis le temps j'aimerais bien une solution moi

[invite35452583]

depuis le temps j'aimerais bien une solution moi

cf posts #7 et #10.

[invite1439ebd6]

Bonjour,
J'aimerais savoir ce que doit faire le prisonnier s'il tombe sur un cycle de moins de 50 ne contenant pas son nom.
Merci beaucoup.

[invite3e46caf7]

Bonjour à tou(te)s,

Je suis tombé un peu par hasard sur cette énigme, et je dois avouer qu'elle m'a incité à m'inscrire sur ce forum pour tenter d'apporter des propositions.

1) Schématiquement, le problème consiste en l'existence de 100 éléments (E) dissociables (par leur nom) et pouvant décider d'établir un tri dans la file allant de E₁ à E₁₀₀. Ce tri pourrait être réalisé en fonction de leur nom, c'est-à-dire ce qui les différencie tous. Ainsi la file {E₁;E₁₀₀} pourrait-elle être établie dans l'ordre alphabétique (modèle A-Z), par "paire" (A-Z-B-Y...) etc.

Considérons à présent les boîtes (B). Ces prisonniers savent qu'elles doivent être dans un certain ordre qui est immuable. De fait, ceux-ci se font une représentation spaciale de leur agencement (B₁ à B₁₀₀) et peuvent déterminer à l'avance un critère commun pour déterminer à quel "point" commence cette chaîne (exemple : commencer par la boîte la plus proche de l'entrée).

Nous avons donc affaire avec deux "chaînes" ; le problème est que l'une d'elle ne se confronte qu'à l'autre que par "maillons" individuels et sur la moitié de celle-ci.

2) Il y a une information qui me semble essentielle : une fois que le premier prisonnier est passé dans la pièce, les autres prisonniers sont conscients qu'il a réussi (puisque l'expérience continue) ; il y a là un élément à prendre en considération (ainsi, le nom du premier prisonnier est apparu dans l'ensemble S qu'il a prédéterminé). Ainsi, si la probabilité pour le premier prisonnier de tomber sur son nom est de 1/2 (je ne vois pas comment on pourrait réduire ce taux), alors les probabilités subséquentes devraient s'atténuer par cette considération.

Voici mes seules propositions pour le moment.

[yat]

J'aimerais savoir ce que doit faire le prisonnier s'il tombe sur un cycle de moins de 50 ne contenant pas son nom.

En commencant par choisir la boite qui porte le numéro correspondant à son nom, le prisonnier se place nécessairement dans un cycle qui contient la boite contenant son nom : c'est la seule qui pointe vers la première boite qu'il a ouverte. Il ne peut donc pas boucler sans passer par elle.

[danyvio]

Bonjour ! J'aimerais relancer le débat sur cette énigme fabuleuse. J'ai étudié (de loin) la solution de CoucouHibou et je lui pose la question suivante: quelle est la probabilité de survie du groupe si, au lieu de suivre un chaînage comme indiqué, chaque prisonnier ouvre en premier la case qui porte son propre numéro, puis les 49 suivantes si nécessaire (en repartant à la case n° 1 une fois la case 100 traitée). En d'autres termes, pourquoi ne pas envisager une stratégie indépendante du classement effectué (aléatoirement ou non) par le geôlier, mais créer d'avance son propre chaînage ?

[yat]

quelle est la probabilité de survie du groupe si, au lieu de suivre un chaînage comme indiqué, chaque prisonnier ouvre en premier la case qui porte son propre numéro, puis les 49 suivantes si nécessaire (en repartant à la case n° 1 une fois la case 100 traitée).

Ben... chaque nom de prisonnier a une chance sur deux de se trouver dans une des 50 boites qui se trouvent avant la boite qui porte son numéro.

Donc...

1/126765060022822940149670320537 6

Déçu ?

[danyvio]

Déçu ?

Oh VOUI ! Il va falloir que je me cogne plus sérieusement la démo

[invite0efcf870]

Moi j'ai une autre solution. Si les personnes passent en ordre il suffit qu'avant d'entrer dans la salle les personnes s'arrange. En fait le premier va parler avec le second et lui demander son numéro ( admettant le numéro 9 par exemple ) et il vont aussi mettre en place une sorte d'indice qui va mettre le second sur la bonne piste. Alors ensuite la première personne va dans la salle ouvre ses 50 boites. Si il voit le numéro 9 ba il ne laisse par exemple aucun signe pour que la seconde personne prenne les 50 premières boites. Et sil il voit pas le 9 il met en place le signe qui indiquera au second qu'il faut qu'il ouvre les 50 dernières.
Le signe doit être discret mais facilement détectable pour a personne qui doit le voir.
C'est pas trop mathématiques mais j'ai pas encore votre niveau^^

[danyvio]

çA y est ! je me suis polarisé sur la démo de CoucouHibou. C'est tout simplement merveilleux, et m'a obligé à réviser toutes les formules de combinatoire . Question subsidiaire lancée ici : combien faut-il ouvrir de boîtes pour que la proba de s'en sortir vivant atteigne 50 % ? 75 % ? (pour 100 % la réponse est simplissime )

[danyvio]

Moi j'ai une autre solution. Si les personnes passent en ordre il suffit qu'avant d'entrer dans la salle les personnes s'arrange. En fait le premier va parler avec le second et lui demander son numéro ( admettant le numéro 9 par exemple ) et il vont aussi mettre en place une sorte d'indice qui va mettre le second sur la bonne piste. Alors ensuite la première personne va dans la salle ouvre ses 50 boites. Si il voit le numéro 9 ba il ne laisse par exemple aucun signe pour que la seconde personne prenne les 50 premières boites. Et sil il voit pas le 9 il met en place le signe qui indiquera au second qu'il faut qu'il ouvre les 50 dernières.
Le signe doit être discret mais facilement détectable pour a personne qui doit le voir.
C'est pas trop mathématiques mais j'ai pas encore votre niveau^^

Ils n'ont AUCUN moyen de communiquer entre eux APRES avoir défini leur stratégie. Signé : Dr NO