Énigme n°4
Par Celui le mardi 19 juin 2007, 11:11 - Énigmes - Lien permanent
Une fois n'est pas coutume, je commence par m'excuser : je n'ai absolument pas le temps d'écrire la solution du problème n°3 et de regarder la réponse de Joun car je croule sous le boulot, pleinement. Promis, je m'en occupe ce week-end.
Voici un problème bien plus difficile
Le Dr. No s'est dit que son problème précédent était trop facile, et qu'il fallait rehausser un peu le niveau, son statut de futur Maître du Monde en dépendait. Il fait d'une pierre deux coups en capturant 100 mathématiciens de la N.S.A. Comme lors de sa précédente tentative qui fut déjouée, il les emprisonne dans des cellules qui les privent de tout moyen de communication.
Dans la pièce secrète, il y a maintenant 100 tiroirs. Sur le fond de chaque tiroir est gravé le nom d'un mathématicien. Les mathématiciens sont appelés les uns après les autres et rentrent dans la pièce. Chaque mathématicien a le droit d'ouvrir au plus 50 tiroirs. Si dans l'un d'eux il y a son nom, alors il retourne sagement dans sa cellule. Si les 100 mathématiciens y arrivent, alors ils seront libérés. Si en revanche il y a un mathématicien qui n'a pas trouvé son nom, alors ils seront tous tués.
Aucune communication n'est permise entre les mathématiciens, par exemple en laissant ouverts certains tiroirs. Tous les tiroirs sont parfaitement refermés et nettoyé entre les passages des mathématiciens.
Ils ont deux semaines pour se concerter et mettre au point une stratégie.
Ils sont dépités car ils se disent qu'ils ont (1/2)^100 (environ 8.10^(-31)) chances de réussir, jusqu'à ce que Monsieur XY[1] propose une stratégie avec un fort taux de probabilité de réussir.
Alors ?
Notes
[1] Le premier qui trouve la réponse sera immortalisé en ayant son nom ici !
Commentaires
Est-ce que 1.53426E-07 est considere comme un "fort" taux de probabilite ?
En fait... j'ai une strategie qui donne (a vue de pif) presque 1/4. Pfiouu ca fatigue tout ca.
Plus exactement presque 1/2... moi, les maths...
Je passe mon tour, j'ai vu la solution de ce problème il n'y a pas très longtemps. Je ne me souviens plus avec précision de la probabilité, mais si Gros Pignouf a affectivement 1/2, il bat la solution que j'avais vue.
J'ai pu me tromper...
La solution que je connais a un taux entre 1/4 et 1/2, mais c'est plus proche 1/3. De toute manière, ça ne tombe pas juste, c'est un nombre à la con. 1/2 est trivialement un borne supérieure puisque le premier qui passe a une chance sur 2...
Je suis assez au clair avec ma strategie mais beaucoup moins sur le calcul des probabilites...
Ma strategie commence par les mathematiciens apprenant tous les noms de leurs confreres.
Je sais pas si je peux continuer a poster la suite sur les commentaires (c'est pas forcement la bonne reponse...)
Oui, oui, tu peux poster, si c'est juste ou presque, je rajouterais une en tête signalant qu'il y a la réponse.
Attention, ce commentaire contient certainement l'idée de la preuve, mais il reste du travail...
Ok alors allons-y.
Nos chers mathematiciens savent bien qu'un tiroir s'ouvre, se referme, mais peut aussi se deboiter... et s'echanger avec d'autres.
La strategie consiste a "classer" les tiroirs.
Les mathematiciens conviennent de la strategie suivante : chacun connait tous les noms et leurs positions dans l'ordre alphabetique. Abel -> 1 d'Alembert ->2 Boole -> 3 et ainsi de suite...
Le premier mathematicien - qui ne sait pas qu'il est le premier a passer - (Boole pour fixer les idees) va donc ouvrir le tiroir dont le numero correspond a sa position dans l'ordre alphabetique (3). Si son nom n'apparait pas (c'est Abel au fond du tiroir), alors il enleve le tiroir et ouvre celui dans la case au numero correspondant (1 pour Abel). Il regarde si le tiroir de la case 1 (Abel) contient son nom. Si non il continue a substituer les tiroirs jusqu'a trouver son nom, et continue meme apres.
A pres le passage du 1er mathematicien (qui a 1/2 chances de trouver son nom) il y aura (s'il survit) exactement 50 tiroirs a la "bonne place", ce qui reduit fortement les chances du suivant de ne pas trouver son nom.
Le suivant, de la meme maniere (qui ne sait pas qu'il est le suivant) ouvre "son tiroir". Si son nom apparait, alors il n'a plus qu'a trier d'autres tiroirs. Sa probailite de trouver un tiroir qui n'est pas a la bonne place est 1/2 (car exactement 50 sont a la bonne place).
C'est la ou j'ai des doutes dans ma theorie de proba... J'ai envie de dire que statistiquement s'il ouvre 2 tiroirs, il y en aura un mal classe. Lequel il continuera a substituer de proche en proche avec celui se trouvant a la place du nom figurant au fond du tiroir mal classe. La beaute du truc c'est que a partir du moment ou le mathematicien trouve un tiroir mal classe, en substituant de proche en proche, il ne peut pas retomber sur un deja bien classe, et donc a moins de references circulaires (case X tiroir Y, case Y tiroir Z, case Z tiroir X) il peut classer beaucoup de tiroirs... ce qui intuitivement me fait pencher vers proche de 1/2.
Car si le mathematicien ne trouve pas son nom au fond du tiroir de "sa case", alors on retombe dans le cas juste avant ou il substitue de proche en proche et tombe avec une tres forte proba (que je ne quantifie pas) sur son nom...
Et ainsi de suite sachant que plus on avance, plus les chances de trouver son nom augmentent. Il me manque surement un peu de rigueur theorique mais je compte sur vous pour m'aider.
Bon, et bien non, les tiroirs ne se permutent pas, désolé : chacun des mathématiciens trouve la pièce dans le même état, exactement le même. Je n'ai pas pris assez de temps pour en être sûr, mais je sens que l'idée de base y est. (et donc, je ne suis pas trop chaud pour faire une formalisation poussée qui serait alors un indice trop fort) (et puis je n'en ai pas le temps cette semaine)
C'est dommage j'aimais bien cette solution consistant a trier les tiroirs.
@Celui
Tu précises que les mathématiciens ne peuvent pas communiquer. Par contre la solution est supérieur a 1/3.
Donc le deuxième doit avoir une probabilité supérieur a 1/2 de trouver son nom.
Il y a donc quelque chose qui change entre le premier Mathematicien et le second sachant qu'il ne connaisse pas leur ordre de passage...
Si l'on considere que les choix de chacun sont independants de ceux des autres, si mes souvenirs en proba sont exacts, ils doivent avoir chacun une probabilité d'au moins (1/3)^1/100 de trouver leur nom.
C'est a dire plus de 98% de chance.
La clef de l'enigme est donc de trouver un moyen qui permet de rendre les choix de chacun dépendant de ceux des précédents...
Désole j'ai pas vraiment fait avance les choses...
Sinon, la réponse est inférieure à 1/3, elle vaut environ 31,18%.
Il faut donc que la stratégie du ième mathématicien (qui ne sait d'ailleurs pas qu'il est le ième à passer) ne soit pas indépendante des autres. La seule chose qu'il peut supposer, c'est que les autres mathématiciens ont trouvés leurs noms. (sinon, il serait déjà mort)
Par exemple, s'il y avait 100 tiroirs pour 2 mathématiciens. Ils se mettent d'accord pour ouvrir chacun 50 tiroirs différents. Le second suppose que le premier à trouvé son nom dans les 50 première tiroirs, alors il ouvre les 50 suivants. Avec une telle stratégie, la probabilité de réussir n'est pas de 25,00% mais de (50/100)*(50/99)=25,2525%, ce qui est un tout petit mieux. On peut faire beaucoup mieux !
Avec le deuxième exemple je vois une procédure efficace, mais je n'arrive pas du tout à l'étendre à plus de 2 :
Les rôles se répartissent ainsi :
Mr. A commence à tirer les tiroirs en partant du haut. S'il rencontre le nom de l'autre au N-ième tirage, il passe en bas, jusqu'à qu'il trouve le sien. Mr. B fait la même chose en partant du bas.
A la réflexion, je ne suis pas du tout sur que cela améliore tellement les choses, même pour N=2. Etant nul en proba (calculer p(b trouve si A a trouvé), etc.), je n'arrive pas à m'en convaincre.
Comme il faut que les matheux aient une stratégie "en aveugle" et qu'ils se transmettent de l'information (rester en vie), il n'y a pas trente six solutions, il faut que tous les matheux sachent exactement ce que les autres ont fait, et que le fait d'être vivant leur permette de tirer de l'information.
Donc chaque matheux doit avoir une suite bien définie de tiroirs. Je suppose que les matheux se mettent d'accord sur une permutation : chaque matheux choisit un nombre j parmi les 100. Le premier
matheux commence donc par ouvrir le tiroir portant ce nombre. il trouve un numéro k, ouvre alors le tiroir k, et ainsi de suite. En fait, c'est perdu uniquement si dans la permutation définie par les tiroirs il y a un cycle d'ordre au moins 51. C'est en fait assez peu probable : la proportion de permutations avec des cycles d'ordre n avec n>50 est 1/n. C'est facile à voir car si tu as un cycle d'ordre n avec n>50, tu ne peux pas en avoir d'autres d'ordre >50 (car tu n'as que 100 tiroirs). Ensuite, pour choisir ton grand cycle tu as 100*99*...*(100-n+1) possibilités pour le cycle, divisé par n car si tu commence par n'importe quel nombre dans le cycle tu tombes sur le cycle. Ensuite, pour le reste de la décomposition de la permutation, tu as (100-n) ! (on s'en fout de la nature exacte puisqu'on n'a pas de cycles). Au final, la proportion de cycles d'ordre 1/n (avec n >50) est donc 100!/n/100!, soit 1/n.
Donc, tes matheux gagnent s'ils n'y a pas de cycles d'ordre n avec n >50. Il y a 1/51ième des permutations ayant un cycle d'ordre 51, 1/52ième des permutations ayant un cycle d'ordre 52, ... 1/100ième des permutations ayant un cycle d'ordre 1/100, toutes ces permutations étant distinctes. DOnc au final, la proportion des permutations qui tuent nos matheux est 1/51+1/52+...1/100, soit si tu fais le calcul 68.82% de chances d'y passer, et donc 31.18% de chances de survivre (je trouve le résultat annoncé, donc ça doit être ça !)
Bravo à Tom Roud. La solution est juste. Le choix de la permutation doit avoir lieu au hasard, il ne faut surtout pas choisir l'ordre lexicographique, le Dr No ayant pu prévoir le coup et faire alors une permutation qui contient un cycle de longueur > 50.
On peut ensuite se poser la question de savoir s'il s'agit là de la solution optimale. La réponse est oui, mais je n'ai aucune idée de la preuve.
@ Celui :
en fait le 31.18% est une borne inférieure, du coup. S'il y a un cycle d'ordre 51, les matheux ont quand même une petite chance de s'en sortir (ils échouent si l'un au moins des matheux choisit son premier chiffre juste après son propre chiffre dans la permutation; autrement dit il y a un chiffre "interdit" par matheux)