Petite énigme combinatoire
Par Allam le mardi 24 novembre 2009, 00:09 - Notes - Lien permanent
Allez, comme les maths me manquent (non, vraiment), je vous pose une petite énigme (enfin grande par l'énoncé, mais c'est parce que j'essaie d'être très compréhensible), pour illustrer l'immense puissance des mathématiques. Je ne vous demande pas de la résoudre, quoique ça serait intéressant si vous essayiez, mais vous avez peut-être mieux à faire ; je vous demande juste, au moins, de lire l'énoncé, en taisant tant que ce n'est pas fini la petite voix qui vous murmure dans votre tête "non mais c'est complètement tordu ton truc, mec" ; puis éventuellement, à la fin, de vous extasier d'un beau "haaa, que c'est grandiose les maths !", ou sinon de vous en foutre d'un désinvolte "On est content d'être heureux...".
Voici l'énoncé :
Vous faites partie d'un groupe de 500 personnes, rassemblé dans une grande pièce. On donne à chacune de ces 500 personnes un numéro différent entre 1 et 500 (donc il n'y a pas deux personnes ayant le même numéro), mettons que vous recevez le numéro 37, vous êtes le seul à l'avoir, jusqu'ici tout va bien. Dans une autre pièce attenante à celle où votre groupe est rassemblé, il y a 500 casiers. À l'intérieur (donc invisible de l'extérieur, tant que le casier n'est pas ouvert) de chacun de ces 500 casiers est disposé un numéro entre 1 et 500, marqué sur un bout de papier, avec encore une fois aucun doublon : il n'y a pas deux casiers avec le même numéro à l'intérieur. L'on a donc 500 personnes avec toutes un numéro différent d'un côté, et 500 casiers avec tous un numéro différent de l'autre. Tour à tour, chacune des 500 personnes de votre groupe va se rendre dans la pièce aux casiers, et ouvrir puis refermer jusqu'à 250 casiers, pour voir le numéro qui se cache à l'intérieur. S'il voit dans l'un de ces 250 casiers le numéro qui correspond au sien, il gagne, sinon il perd. Dans tous les cas, il retourne dans l'autre pièce, et n'a pas le droit, en aucune manière que ce soit, de communiquer avec les autres personnes du groupe (de sorte qu'en entrant dans la salle des casiers, personne n'ait déjà une idée de quel casier renferme quel numéro). Par exemple, supposons que ce soit votre tour d'y aller : vous ouvrez un premier casier, vous y trouvez, disons, le numéro 412. Ce n'est pas le votre (je vous rappelle que vous avez le numéro 37), vous refermez le casier, vous en ouvrez un second, vous y trouvez le numéro 125. Toujours pas bon, vous refermez, vous en ouvrez un troisième, etc, et ce 250 fois. Si à un moment vous avez trouvé le numéro 37 dans un casier, vous avez gagné, sinon vous avez perdu.
On suppose que dans une journée, tout le monde a eu le temps d'aller ouvrir ses 250 casiers. Votre but, à vous les 500 personnes, est que tout le monde ait gagné dans la même journée : il faut que chacune des 500 personnes ait ouvert au moins une fois le casier contenant son numéro, parmi les 250 qu'elle a ouverts. Si ce but est atteint, vous gagnez tous un grand voyage en Australie et le jeu est fini ; sinon, on considère que tout le monde a perdu, et on retente la chance le lendemain, en mélangeant les numéros dans les casiers pendant la nuit (comme ça, encore une fois, personne n'a déjà une idée de quel casier renferme quel numéro en entrant le lendemain dans la salle, même ceux qui ont très bonne mémoire).
Vous pensez vous laisser aller au désespoir devant l'impossibilité de la tâche, lorsque l'une des personnes de votre groupe (sûrement un normalien...) s'exclame : "si on suit ma méthode, au bout d'une semaine, on aura plus de 9 chances sur 10 d'avoir gagné un voyage en Australie !" Comment fait-il ?
Fin de l'énoncé
Hé oui, comment fait-il ? C'est cela qui est intéressant. Mais voyons au moins pourquoi la tâche peut sembler impossible de prime abord : si chacun choisit ses 250 casiers au hasard - comme il n'y a aucune information préalable sur quel casier renferme quel numéro, cette méthode peut paraître aussi bonne qu'une autre - il a en somme une chance sur deux de trouver, parmi les 250 numéros, le sien (en effet, c'est comme si on tirait un numéro au hasard entre 1 et 500 : il a une chance sur deux d'être dans les 250 premiers, et une chance sur deux d'être dans les autres, les 250 derniers). Donc chacun a une chance sur deux de gagner. Donc deux personnes ont une chance sur quatre de gagner toutes les deux (à ceux qui comprennent : les événements sont indépendants, donc multiplication des probabilités). Continuons le calcul : 500 personnes ont 
de chances de toutes gagner la même journée, soit, en valeur approchée :
Autrement dit rien, mais rien, rien ! À ce rythme là, il vous faudrait environ 10150 jours pour avoir ne serait-ce que 50% de chances de partir en Australie, soit quelque chose comme un milliard de milliards de milliards de [...] de milliards d'années, en alignant comme ça 49 fois le mot milliards. Il y a des milliards de fois moins d'atomes dans l'univers que d'années nécessaires. Les kangourous vont vous attendre, hein... alors qu'avec la méthode de l'autre normalien, là, avec sa bonne tête de génie et ses cheveux en bataille, vous avez 90% de chances de siroter un cocktail à Sydney à peine sept jours plus tard. Ça paraît délirant, non ?
Il y a deux parties dans l'énigme, en fait : la première, trouver la méthode géniale ; la seconde, voir pourquoi ça marche. Sachant que si le calcul prouve effectivement que ça marche, il n'est pas évident, en voyant juste la méthode, qu'elle soit vraiment plus efficace que notre méthode naïve qui consiste à choisir au hasard (on aurait même l'impression qu'elle l'est moins, car elle n'exclut pas qu'une personne ouvre plusieurs fois le même casier) - alors que le résultat est là, sans appel et conforme à ce qu'annonce le normalien.
C'est puissant, les maths, non ? Non ?... Vous êtes contents d'être heureux vous aussi ? Allez, je vous donnerai la solution dans quelques jours, dans un autre billet ou en commentaire, promis. Peut-être que ça intéressera quelqu'un ! Un indice : on peut donner des numéros aux casiers aussi.
Édition : voici la solution, dans un document qui reprend initialement l'énoncé. Si la démonstration mathématique ne vous intéresse pas, à la limite, oubliez ce document et allez plutôt voir l'explication que je donne en commentaire, j'y explique les choses un peu plus simplement.
Commentaires
Non mais non mais nooooooon !!
Je me suis appliquée à tout lire, et y'a même pas la réponse ? :'(
*désespoir*
Bon, et bien j'attendrai patiemment, étant donné qu'il est exclu que je trouve par moi-même :p
J'y ai du mal à croire mais d'une, j'ai réussi à lire et de deux, j'ai réussi a comprendre le but.
Maintenant tu m'excuseras mais ça fait 9 ans que j'ai pas fait de proba/stat XD et puis la chose la plus difficile à faire comprendre à mes élèves à mon niveau c'est les divisions. XD... Mais je suis quand même curieuse de connaitre le procédé en espérant qu'il soit à ma portée
Bon l'énoncé était bien expliqué finalement donc pas de problème pour le comprendre, par contre tu comprendras que je n'ai pas la moindre intention de réfléchir au problème et donc qu'il serait utile que tu balances la réponses ... rapidement :D .
Oulà, attendez un peu là, je ne pensais pas susciter un intérêt si rapide... j'ai même pas encore tapé la réponse :D . Si je savais, je vous parlerais de maths plus souvent =D .
T'inquiète pas, Gaby, comprendre le procédé génial, c'est à la portée de tout le monde. Comprendre pourquoi il marche, en revanche, je sais pas trop ; et prouver qu'il marche, enfin, c'est du niveau de première/deuxième année de licence de maths.
Je séparerai ces trois aspects dans la solution... :D
Oui, donc, la réponse, un peu longue mais j'ai essayé encore une fois de faire un effort d'explication (... me demandez pas qui a pu trouver ça, ce n'est pas moi ; moi je n'ai fait que la preuve mathématique à la fin et la constatation que c'est génial) :
La stratégie proposée par notre petit génie de normalien est la suivante, qu'il expose en s'ébouriffant les cheveux : les 500 personnes se mettent d'accord pour numéroter toutes de la même façon les 500 casiers, de 1 à 500 encore une fois. Donc on attribue à chaque casier un numéro unique entre 1 et 500, indépendant du numéro écrit sur les papiers qui se trouvent à l'intérieur des casiers. On a donc trois séries de numéros de 1 à 500: ceux attribués aux gens, ceux attribués aux casiers, et ceux qui sont dans les casiers. Ensuite, chaque personne, lorsqu'elle ira dans la pièce aux casiers pour ouvrir ses 250 casiers, commencera par se diriger vers le casier qui porte son numéro : si vous avez le numéro 37, vous irez ouvrir en premier le casier numéro 37. Ensuite, vous regardez le numéro qui est à l'intérieur de ce premier casier, et vous irez ouvrir le casier qui porte ce numéro. Et ainsi de suite. Par exemple, si vous trouvez le numéro 412 dans le premier casier, vous allez ouvrir en second le casier numéro 412. Puis, supposons que le papier à l'intérieur de ce casier 412 porte le numéro 125, alors vous irez ouvrir ensuite le casier numéro 125, etc. Ainsi, le papier que vous trouvez à l'intérieur d'un casier détermine le numéro du casier que vous irez ouvrir ensuite. Vous pouvez ouvrir deux fois le même casier par ce système, cela ne pose aucun problème (si par exemple le casier numéro 125 recèle le numéro 37 dans son intérieur, vous retourneriez ensuite ouvrir le casier numéro 37, celui que vous aviez ouvert en premier. Notons que si c'est le cas, comme vous avez vu le numéro 37, vous avez gagné...). Lorsque vous avez ouvert 250 casiers (donc pas forcément différents), vous arrêtez ; si, lors de ces ouvertures, vous avez trouvé votre numéro, vous gagnez pour la journée, et sinon, vous perdez, comme toujours. Et comme toujours, vous et vos camarades de groupe partez en Australie si vous gagnez tous la même journée.
Et il se trouve que cette méthode, a priori toute bête, marche très bien ! Grandiose, non !? Ce qu'il faut voir, ce qui est fort dans cette méthode, c'est que si vous deviez rouvrir un casier que vous avez déjà ouvert, c'est que vous avez vu votre numéro. En effet, continuons l'exemple pour vous faire comprendre : supposons que vous êtes amenés à rouvrir une seconde fois le casier numéro 412. Pour ce faire, il faut que vous ayez vu le papier numéro 412 dans un casier ; or, ce papier-là se trouve dans le casier numéro 37, vous le savez, vous l'y avez déjà vu, puisque vous l'avez déjà ouvert au tout début. Donc si vous êtes amenés à ouvrir une seconde fois le casier numéro 412, c'est que vous avez ouvert juste avant le casier numéro 37, une seconde fois lui aussi. Et si vous êtes amenés à ouvrir le casier numéro 37 une seconde fois, c'est que vous avez vu le papier numéro 37 quelque part, dans un autre casier que vous avez ouvert. Donc, vous avez gagné.
Je récapitule pour ceux qui n'ont pas déjà arrêté de lire : par ce procédé, vous suivez une genre de "chaîne" de casiers que vous ouvrez tour à tour, qui finit forcément par boucler sur le premier casier que vous avez ouvert, celui qui porte votre numéro. Donc si vous parcourez cette chaîne en entier, jusqu'à son dernier élément, celui qui vous ramène au casier de départ, alors vous gagnez, car dans ce dernier casier vous trouvez votre numéro. Comme vous ouvrez au maximum 250 casiers, tout dépend de la longueur de cette "chaîne" de casiers : si elle est supérieure à 250, alors vous perdez ; mais si elle est inférieure ou égale à 250, vous gagnez !
Sur ces remarques, ce que nous disent les maths, c'est qu'il y a quand même environ 30% (!) de chances que toutes ces "chaînes de casiers" soient de longueur inférieure ou égale à 250 (ce qui signifie que tout le monde gagne, puisque tout le monde parcourt alors sa "chaîne" au moins en entier !). Donc déjà, avec cette technique, en seul un jour, vous avez 30% de chances d'aller surfer sur les plages australiennes ! En une semaine, donc 7 essais, ce taux monte à environ 92%, comme l'annonçait notre ami normalien qui va pouvoir aller draguer l'académie des sciences australienne.
Bon, c'est beau tout ça, et si tout est clair, ça devrait se prouver mathématiquement, non ? Effectivement, et c'est ce que je fais dans ce document : http://shkdee.info/fichiers/EnigmeC... , où je reprend d'abord l'énoncé et à peu près l'explication phénoménologique ci-dessus, et où vous trouverez le raisonnement mathématique à partir de la troisième page. Compréhensible en principe par n'importe qui qui sait ce qu'est une permutation, et qui est plus ou moins familier avec sa décomposition en cycles à supports disjoints.
"Compréhensible en principe par n'importe qui qui sait ce qu'est une permutation, et qui est plus ou moins familier avec sa décomposition en cycles à supports disjoints."
Je crois que je vais m'arrêter là hein :D
Mais merci quand même :p
J'ai compris, je te fais confiance pour le calcul... et je rejoins Camille vers la sortie XD
Pourant, si vous avez compris tout ça, vous n'êtes en substance pas très loin de savoir ce qu'est une permutation (qui correspond au processus qu'à un numéro sur un papier, on fait correspondre un casier avec un autre numéro à l'intérieur), et non moins loin de savoir ce qu'est un cycle (la "chaîne de casiers") :D . Le reste n'est que du jargon formel, nécessaire mais non fondamentalement utile.
salut monsieur,
par rapport à ton raisonnement sur ces chaines de casiers, qu'est ce qui m'empeche de faire le même raisonnement, mais avec chacun qui cherche dans un autre casier de manière completement aléatoire. J'entends par là. On ne donne pas de numéro au casier, chacun l'un après l'autre va rechercher dans un casier puis dans un autre comme bon lui semble, il commence meme n'importe où a priori. Cela crée tout de même une chaine de casier (cycle bla bla bla) et on peut toujours à ce moment là faire le calcul de la probabilité qu'il n'y ait pas de chaine de casier de plus de 250 éléments, ne devrait-on pas trouver le même résultat qu'en faisant ta méthode ?
La question est : Pourquoi ne peut on pas adapter ton raisonnement à ces 500 personnes qui cherchent tous leur casier aléatoirement ?
Non, on ne trouve pas le même résultat car donner des numéros aux casiers, qui sont les mêmes pour tout le monde, permet d'avoir une seule et unique permutation, que tout le monde suit. Si les gens y vont tous au hasard, on peut effectivement imaginer qu'ils suivent un cycle mais alors chacun suit un cycle d'une permutation différente ; il s'agit alors plutôt de calculer la probabilité qu'étant données 500 permutations au hasard, elles n'aient toutes que des cycles de longueur inférieure ou égale à 250... ce qui me parait beaucoup plus faible (1-P exposant 500, comme 1-P est plus petit que 1 c'est très très très faible).
Ce que tu calculerais, en adaptant ta méthode à chacun, est que chaque type a, individuellement et séparément des autres, au moins un peu plus de 90% de chances de gagner au moins une fois en 7 jours (en fait encore plus probablement parce que le raisonnement ne s'adapte pas tout à fait). Mais pas qu'ils aient tous 90% de gagner le même jour, en 7 essais.
(et encore s'ils commencent n'importe où ça n'a plus de sens de raisonner avec les cycles puisque le seul intérêt que ça avait était de pouvoir donner un critère facile de reconnaissance de si un des type trouve son numéro ou pas)