Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

denombrement étonnant



  1. #1
    zinia

    denombrement étonnant


    ------

    Bonsoir,

    Je n'ai pas trouvé ce problème assez ancien sur le forum, aussi je vous le propose.

    Six personnes portant chacune un chapeau se rendent au restaurant et déposent leurs couvre-chefs avant de déjeuner. Après un repas bien arrosé, elles reprennent chacun un chapeau au hasard car elles ne sont pas en état de choisir.
    1 Quelle est la probabilité qu'aucune ne reprenne son propre chapeau.
    2 généralisation à n personnes et n chapeaux et limite de la probabilité.
    Il est intéressant d'essayer de répondre à la question finale avant de faire les calculs, on risque d'être surpris.

    -----

  2. Publicité
  3. #2
    shokin

    Re : denombrement étonnant

    Pas si simple, je trouve une "méthode" pour calculer n en fonction de (n-1) et ainsi je peux trouver chaque nombre.

    Mais si n est très grand, ça risque de durer.

    Voici comment :

    Pour 1, 2, 3 chapeaux, je fais sans formule (par énumération).

    Soit p(x;y) la probabilité de trouver x chapeaux justes parmi y chapeaux.

    Alors p(x;y) = [y!/[(x+1)!(y-x-1)!] * p(0;y-x) ]/y! pour x naturel non nul.

    Et pour calculer p(x;y) avec x nul :

    p(0;y) = 1 - Somme des p(i;y), i allant de 1 à y. Je n'ai pas trouvé d'autres trucs.

    Je ne vois pas de formule a priori.

    Doit pourtant y avoir un truc.

    Si j'appelle p(x;y) la probabilité de retrouver x chapeaux justes parmi y chapeaux, je trouve :

    p(a;a) = 1/a! pour tout a naturel non nul
    p(a-1;a) = 0/a! pour tout a naturel non nul
    p(a-2;a) = [n(n-1)/2]/a! pour tout a naturel non nul

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  4. #3
    zinia

    Re : denombrement étonnant

    Citation Envoyé par shokin
    Pas si simple, je trouve une "méthode" pour calculer n en fonction de (n-1) et ainsi je peux trouver chaque nombre.
    Mais si n est très grand, ça risque de durer.
    Shokin
    Je n'ai pas encore bien compris tes formules mais il y a effectivement plus simple.
    Il faut établir une récurrence sur le nombre de personnes en posant par exemple X(n) = nombre de permutations de n objets tels qu'aucun ne retrouve sa place initiale et ensuite essayer d'établir X(n+1) en fonction de X(n), X(n-1)....
    Le raisonnement n'est pas évident mais les formules sont simples et avec un peu d'astuce, on peut faire les calculs avec les doigts d'une seule main.

    Au fait, à ton avis, intuitivement, vers quoi va tendre la proba quand n grandit ?

  5. #4
    GuYem

    Re : denombrement étonnant

    Intuitivement évidemment on a l'impression que la proba va tendre vers 0 quand n grandit : plus ya de monde, plus ya du bordel, moins les gens vont retrouver leur chapeau.

    Cependant mon petit doigt me dit que ce sera pas 0 ... à suivre
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  6. A voir en vidéo sur Futura
  7. #5
    zinia

    Re : denombrement étonnant

    Citation Envoyé par shokin
    p(x;y) = [y!/[(x+1)!(y-x-1)!] * p(0;y-x) ]/y! pour x naturel non nul.
    Shokin
    Bonjour,
    Je dirais plutôt p(x;y) = [y!/[(x)!(y-x)!] * p(0;y-x) * (y-x)! ]/y!
    Cela se simplifie beaucoup : p(x;y) = p(0;y-x)/(x)!
    Tu as introduit un "+1" étrange et sans doute confondu proba et nombre de cas.
    Je pense qu'on peut y arriver avec ta démarche mais je n'ai pas encore réussi...

  8. #6
    GuYem

    Re : denombrement étonnant

    Avec ton indication Zinia : pour X(n) je, trouve la relation de récurrence :
    X(n) = (n-1)( X(n-1) + X(n-2) ) en distinguant deux cas :
    -l'image de 1, appelons la i est a nouveau envoyée sur 1 apr la permutation, cela donne le terme (n-1)X(n-2)
    -i n'est pas envoyé sur 1, cela donne le terme (n-1)X(n-1)

    Cette relation à l'air de marcher au moins pour n=4, puisqu'on trouve dans S_4 9 permutations qui ne fixent personne : les 6 4-cycles et les 3 doubles permutations ; et que 9 = 3*(2+1) = (n-1)(X(3) + X(2)).

    Avec cette formule on trouve X(6) = 265, et donc la proba cherchée à la première question serait 256/6! = 0.24 si je sais me servir de la calculatrice de windows.

    Reste à trouver une expression fermée de X(n) en fonction de n, ou peut-être juste de trouver la limite de X(n)/n! pour voir apparaitre la chose étrange dont tu parles.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  9. Publicité
  10. #7
    zinia

    Re : denombrement étonnant

    Citation Envoyé par GuYem
    Avec cette formule on trouve X(6) = 265, et donc la proba cherchée à la première question serait 256/6! = 0.24 si je sais me servir de la calculatrice de windows.
    Bravo tout a tout juste sauf qu'il faudrait apprendre à te servir d'une calculatrice 265/6! = 0.368

  11. #8
    GuYem

    Re : denombrement étonnant

    lolo, les calculatrices, ça sert à rien.

    Par contre pour la suite je suis un peu embété puisque je ne parviens pas à déduire ni une expression de X(n) en fonction de n, ni la limite de X(n)/n!
    Si je divise ma relation par n! et que je fais n->oo, ça me donne, en appelant L la limite cherchée ; L = L, super !
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  12. #9
    zinia

    Re : denombrement étonnant

    essaie la suite u(n)=P(n)-P(n-1) avec P(n)=X(n)/n!

  13. #10
    GuYem

    Re : denombrement étonnant

    Rhaa, moi qui croyais que ça servait jamais de regarder des séries télescopiques ! Va falloir changer d'avis.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  14. #11
    GuYem

    Re : denombrement étonnant

    Alors après indication, on trouve une relation simple sur u_n qui est :
    u_n = -1/n * u_{n-1}
    Vu que u(2) = 1/2 on déduit que u_n = (1-)^n/n! et que la somme des u_n de 2 plus l'infini fait 1/e.
    Comme ça se bidouille bien pour les premiers termes et que p(1)=0, cette limite 1/e est également la limite de la proba recherchée quand n tends vers +oo.

    C'est réconfortant puisque 1/e = 0.36787 et on voit que pour n=6, on est à 0.38, ce qui n'est pas loin du tout. Cela confirme le fait que la série converge trés vite vers sa limite.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  15. #12
    rvz

    Re : denombrement étonnant

    Citation Envoyé par GuYem
    Alors après indication, on trouve une relation simple sur u_n qui est :
    u_n = -1/n * u_{n-1}
    Vu que u(2) = 1/2 on déduit que u_n = (1-)^n/n! et que la somme des u_n de 2 plus l'infini fait 1/e.
    Comme ça se bidouille bien pour les premiers termes et que p(1)=0, cette limite 1/e est également la limite de la proba recherchée quand n tends vers +oo.

    C'est réconfortant puisque 1/e = 0.36787 et on voit que pour n=6, on est à 0.38, ce qui n'est pas loin du tout. Cela confirme le fait que la série converge trés vite vers sa limite.
    Très très joli

    __
    rvz, qui avait essayé d'attaquer le problème initial, mais sans succès...

  16. Publicité
  17. #13
    GuYem

    Re : denombrement étonnant

    Citation Envoyé par rvz
    Très très joli

    __
    rvz, qui avait essayé d'attaquer le problème initial, mais sans succès...
    C'est vrai que ça fait toujours bizarre de voir sortir des e dans des exos de probas comme celui-là.
    Si ça t'intéresse je t'invite à regarder ce fil : http://forums.futura-sciences.com/thread43917.html
    où le brave e sort aussi d'on ne sait où ; les probas, c'est beaaaau.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  18. #14
    zinia

    Re : denombrement étonnant

    Bravo GuYem
    Je pense que la difficulté majeure était d'établir la relation de récurrence.
    En regardant le fil que tu cites, je me suis demandé quelle était l'espérance du nombre K d'objets inchangés dans une permutation aléatoire (uniforme) de n objets.
    En utilisant la démarche de shokin, je suis arrivé à 1, ce qui semble faible mais va savoir !

  19. #15
    zinia

    Re : denombrement étonnant

    Bonjour,

    Je reviens à la charge : l'espérance du nombre d'objets inchangés dans une permutation est effectivement égale à un et ce quel que soit le nombre d'objets permutés de 1 à l'infini.
    En outre à partir d'un nombre assez petit, la variable aléatoire K= nombre d'objets inchangés suit presque exactement une loi de Poisson de paramètre .
    Par exemple la proba d'avoir trois objets non modifiés est égale à 6,2 % pour n=3,
    6,11 % pour n=5,
    6,131 % pour n=7
    6,1313 % (1/6e) pour n= 12 843
    Qui aurait une explication logique à cette belle convergence ?

  20. #16
    GuYem

    Re : denombrement étonnant

    Euh j'avoue que la loi de Poisson je connais pas trop !
    Mais il me semble qu'on peut approximer des B(n,p) par des poissons sous certaines conditions sur n et p non ?

    Comment as-tu fait pour trouver que l'espérance en question est 1 ?
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  21. #17
    zinia

    Re : denombrement étonnant

    Citation Envoyé par GuYem
    Comment as-tu fait pour trouver que l'espérance en question est 1 ?
    Désolé, c'est d'une simplicité decevante :
    Comme indiqué, je pars de la démarche de shokin en posant
    p(k,n) = probabilité pour qu'une permutation de n objets en laisse k inchangés.
    On a possibilités de choisir les k inchangés et pour les autres il existe X(n-k) avec les notations précédentes.
    On établit donc facilement que p(k,n)= (i)
    Donc E(K) =
    en réutilisant la relation (i) : E(K)= = 1
    Concernant Poisson, une chose est certaine, on n'a pas de loi binomiale là dedans.

  22. #18
    shokin

    Re : denombrement étonnant

    A plusieurs nous y arrivons.

    Arg ! ces probabilités !

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  23. Publicité
  24. #19
    invite986312212
    Invité

    Re : denombrement étonnant


  25. #20
    zinia

    Re : denombrement étonnant

    Oui, effectivement en cherchant "problème des rencontres" sur Google, on trouve de tout avec là dedans les résultats énoncés mais pas de justification de la convergence vers Poisson (à moins de j'ai raté quelque chose ?)

  26. #21
    fderwelt

    Re : denombrement étonnant

    Bonsoir,

    Apparemment, tout le monde a trouvé le Wiki sur le nombre de "dérangements" (permutations sans point fixe).

    Donc j'arrive trop tard... mais c'est vrai que le résultat est (un peu) surprenant. En fait, plus il y a de monde, moins il y a de chances que le bordel soit vraiment complet, on peut toujoursdse dire que sur le tas ce serait vraiment pas de bol qu'il n'y en ait pas au moins un qui retrouve son chapeau...

    -- françois

  27. #22
    invite986312212
    Invité

    Re : denombrement étonnant

    Citation Envoyé par zinia
    Oui, effectivement en cherchant "problème des rencontres" sur Google, on trouve de tout avec là dedans les résultats énoncés mais pas de justification de la convergence vers Poisson (à moins de j'ai raté quelque chose ?)
    je ne sais pas quel genre de justification tu voudrais, mais la loi de Poisson est la loi limite dans pas mal de situations. C'est une loi "infiniment divisible" c'est-à-dire que pour tout entier n, il existe une distribution dont elle est la n-ième puissance de convolution.

  28. #23
    invite986312212
    Invité

    Re : denombrement étonnant

    j'essaie de répondre à la question de Zinia: quel est la raison profonde de la convergence vers la loi de Poisson, et je ne trouve rien d'intelligent à dire. Je remarque juste que si les personnes choisissaient leurs chapeaux au hasard et indépendamment, alors le nombre de personnes retrouvant leur chapeau (ou le nombre de chapeaux retrouvant leur tête) suivrait une loi binomiale de paramètres n et 1/n, et il est bien connu que quand n croît, ça converge vers une loi de Poisson de moyenne 1. Mais les choix ne sont pas indépendants (tirage avec remise) et donc il doit se faire que quand n croît, les tirages "deviennent de moins en moins dépendants". Ca me fait penser à ce qu'on appelle en proba les "conditions de mélange" pour les processus aléatoires (mixing processes) mais comme cette notion dépend de l'ordre de l'ensemble des indices, je ne vois pas comment l'étendre au cas des chapeaux (qui ne sont pas numérotés).

    par contre, j'ai déniché un truc intéressant: un autre cas de proba qui vaut 1/e. Il s'agit du fameux "problème de la secrétaire": un employeur veut embaucher une secrétaire (ou un, ne soyons pas sexiste), et il reçoit
    les candidat(e)s un(e) par un(e). S'il laisse passer un candidat sans le choisir, il ne pourra plus le revoir (ce problème date d'une période de plein-emploi...). Les candidats sont en nombre fini. Le problème est de trouver la stratégie qui maximise la probabilité de choisir le meilleur candidat. Je vous laisse essayer de résoudre le problème, mais la probabilité en question, si on suit la stratégie optimale, n'est autre que 1/e.

  29. #24
    homotopie

    Re : denombrement étonnant

    Citation Envoyé par ambrosio
    par contre, j'ai déniché un truc intéressant: un autre cas de proba qui vaut 1/e. Il s'agit du fameux "problème de la secrétaire": un employeur veut embaucher une secrétaire (ou un, ne soyons pas sexiste), et il reçoit
    les candidat(e)s un(e) par un(e). S'il laisse passer un candidat sans le choisir, il ne pourra plus le revoir (ce problème date d'une période de plein-emploi...). Les candidats sont en nombre fini. Le problème est de trouver la stratégie qui maximise la probabilité de choisir le meilleur candidat. Je vous laisse essayer de résoudre le problème, mais la probabilité en question, si on suit la stratégie optimale, n'est autre que 1/e.
    Bonjour,
    ce que j'ai mis en gras, ce n'est pas plutôt la limite de la probabilité quand n tend vers l'infini?
    Ceci dit je ne sais le montrer que partiellement (je connais la stratégie qui donne ce résultat et c'est l'optimum en empruntant une stratégie du même type)
    Je ne donne pas la réponse je connaissais déjà (je laisse chercher les intéressés) mais je suis intéressé par ce qui me manque : la stratégie que je connais est bien l'optimale de "manière absolue", pas mon domaine ces problèmes là.

    Autre apparition de e (et non 1/e), on coupe un bâton d'un mètre en deux on en jette une partie on garde l'autre. On continue et on met bout à bout les morceaux conservés. En moyenne, au bout de combien de coups le tronçon ainsi constitué atteint ou dépasse un mètre?
    "Preuve rapide" : c'est clairement plus grand que 2, on sent que c'est moins que 3, or il n'y a qu'un nombre intéressant entre 2 et 3, c'est e Il ya évidemment une preuve sérieuse (pas très difficile)

  30. Publicité
  31. #25
    invite986312212
    Invité

    Re : denombrement étonnant

    oui, ça doit être la limite (si n=1 ce n'est pas 1/e). Je vais chercher pour les autres stratégies, je crois qu'il y a une abondante littérature sur le sujet.

  32. #26
    homotopie

    Re : denombrement étonnant

    Précision : le en tête de mon précédent post est une erreur de manip (je viens seulement de le voir).
    ambrosio, j'espère que tu ne l'as pas mal pris, je désirais seulement faire une précision, désolé.
    Dernière modification par homotopie ; 03/04/2006 à 17h16.

Discussions similaires

  1. Phénomène étonnant.
    Par checo dans le forum Physique
    Réponses: 7
    Dernier message: 05/10/2007, 12h07
  2. spectacle étonnant cité des sciences
    Par shazam1 dans le forum Actualités
    Réponses: 0
    Dernier message: 05/12/2006, 14h56
  3. dénombrement
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 01/10/2006, 17h36
  4. Comportement étonnant
    Par Quetzalcoatl. dans le forum Biologie
    Réponses: 1
    Dernier message: 25/08/2006, 18h01
  5. Étonnant !
    Par MimasMimas dans le forum Archives
    Réponses: 12
    Dernier message: 08/08/2005, 15h41