Répondre à la discussion
Page 1 sur 3 12 DernièreDernière
Affichage des résultats 1 à 30 sur 65

Tirage au sort avec un dé

  1. #1
    Juzo

    Tirage au sort avec un dé

    Bonjour à tous,

    [habillage]Un jeu avec N joueurs est sur le point de démarrer. Le maître du jeu désire tirer au sort le celui ou celle qui jouera en premier.
    Pour cela il dispose uniquement d'un dé à 6 faces.[/habillage]

    Quelle est la méthode la plus économe en nombre de lancers de dé, pour tirer au sort équitablement un joueur parmi N joueurs avec un dé à 6 faces, et quelle sera une estimation du nombre de lancers nécessaires ?

    Quelques éléments de réflexion en spoiler

     Cliquez pour afficher

    -----

    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  2. Publicité
  3. #2
    CM63

    Re : Tirage au sort avec un dé

    Bonjour,

     Cliquez pour afficher
    Dernière modification par CM63 ; 26/02/2018 à 08h42.

  4. #3
    ansset

    Re : Tirage au sort avec un dé

    @CM63:
    question sous spoiler car en référence à sa proposition.
     Cliquez pour afficher
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  5. #4
    Médiat

    Re : Tirage au sort avec un dé

    Bonjour CM63

    Le problème avec cette approche (elle est peut-être optimum, mais cela reste à démontrer), c'est pour des nombres du genre 6^n + 1 où l'on risque beaucoup de répétitions et à chaque fois de n lancers (6 en moyenne je pense)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  6. #5
    Médiat

    Re : Tirage au sort avec un dé

    Pour être concret :

     Cliquez pour afficher
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  7. #6
    vgondr98

    Re : Tirage au sort avec un dé

    Mettons qu'il y a 100 joueurs, tout d'abord on choisit un nombre entre 11 et 66 et composé que des chiffres 1,2,3,4,5 et 6, par exemple 33.
    Chaque joueur tire 2 fois le dé, ensuite les chiffres obtenus sont concaténés pour obtenir un nombre à 2 chiffres. Le joueur le plus proche du résultat devient le premier. La probabilité d'obtenir 33 est de 1/36, on peut s'attendre à environ 3 ex aequo, au grand max 10 ex aequo.
    Dans ce cas peu probable, il faudrait 100*2 + 10*2 = 220 lancés.

  8. #7
    ansset

    Re : Tirage au sort avec un dé

    Citation Envoyé par vgondr98 Voir le message
    Mettons qu'il y a 100 joueurs, tout d'abord on choisit un nombre entre 11 et 66 et composé que des chiffres 1,2,3,4,5 et 6, par exemple 33.
    ça ne commence pas très bien.
    comment choisis tu ce nombre.?
    le principe est que l'on a que deux dés à disposition.
    si ton idée est de dire : on le tire "au hasard", alors on fait de même avec les participants, et on a même pas besoin de dés.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  9. #8
    Juzo

    Re : Tirage au sort avec un dé

    Bonjour à tous

    La méthode proposée par CM63 me posait la même question qu'à Médiat, et comme ansset je n'ai pas compris comment il a obtenu ce nombre de lancers estimé.

    Citation Envoyé par Médiat
    Si on compte en base 3, on lance 2 fois le dé et c'est fini !
    Si on obtient 00 il faut relancer les dés non ?

    @vgondr98 : autant choisir le joueur qui a fait le plus gros score, ce qui revient presque à la méthode que j'ai proposée plus haut.
    S'il reste encore 10 participants après la 1ère étape, il peut encore y avoir des ex aequo... Et on peut aussi s'attendre à 100 ex aequo à la 1ère étape, même si c'est très peu probable.
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais

  10. #9
    CM63

    Re : Tirage au sort avec un dé

     Cliquez pour afficher

  11. #10
    ansset

    Re : Tirage au sort avec un dé

    certes, mais ce n'est pas "équiprobable" .
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #11
    Médiat

    Re : Tirage au sort avec un dé

    Citation Envoyé par Juzo Voir le message

    Si on obtient 00 il faut relancer les dés non ?
    Je voulais dire 9 joueurs numérotés de 0 à 8
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #12
    vgondr98

    Re : Tirage au sort avec un dé

     Cliquez pour afficher

  14. #13
    CM63

    Re : Tirage au sort avec un dé

    Citation Envoyé par ansset Voir le message
    certes, mais ce n'est pas "équiprobable" .
     Cliquez pour afficher

  15. #14
    ansset

    Re : Tirage au sort avec un dé

    merci pour ta réponse mais je n'ai pas compris.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  16. #15
    CM63

    Re : Tirage au sort avec un dé

    Bonjour,

    Mais je n'ai pas pensé à une chose: si on laisse tomber les chiffres sans intérêts, et qu'on refait un tirage jusqu'à obtenir un chiffre valide, du coup on ne maîtrise plus le nombre de tirages

  17. #16
    Amanuensis

    Re : Tirage au sort avec un dé

    Idée: tirer le dé pour chaque joueur, et ne garder que ceux qui ont obtenu la plus grande des valeurs les moins représentées parmi celles obtenues, et recommencer sur ceux-ci, jusqu'à ce que le nombre de joueurs restant en lice soit de la forme 2^p 3^q...

    (Cela me semble nécessairement plus efficace que la méthode générale proposée message #1. Le nombre de tirages n'est pas borné (cas où tous les tirages sont égaux), mais la proba semble chuter vite.)
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  18. #17
    Amanuensis

    Re : Tirage au sort avec un dé

    Autre piste, dans la même filière:

    Si le nombre de joueurs est de la forme 2^p 3^q, procéder selon la méthode adaptée ;

    sinon, tirer le dé pour chacun, cela donne 6 sous-ensembles de cardinaux n_1 à n_6 ; tester si une ou plusieurs sommes des n_i est de la forme 2^p 3^q, auquel cas prendre parmi les plus petites celle de valeurs de tir la plus "petite" selon un ordre pré-établi, et continuer avec les joueurs ayant eu une des valeurs ; sinon, recommencer avec les joueurs ayant obtenu la plus grande des valeurs les moins représentées parmi celles obtenues.

    Exemple sur 17 joueurs, si leurs tirages sont cinq 1, cinq 2, sept 3, alors on prend ceux qui ont obtenu 1 ou 3 (avec (1, 3) considéré plus petit que (2, 3)), et on finit en deux tirages.
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  19. #18
    Médiat

    Re : Tirage au sort avec un dé

    Bonjour,
    Citation Envoyé par Amanuensis Voir le message
    Exemple sur 17 joueurs, si leurs tirages sont cinq 1, cinq 2, sept 3, alors on prend ceux qui ont obtenu 1 ou 3 (avec (1, 3) considéré plus petit que (2, 3)), et on finit en deux tirages.
    Soit un total de 19 tirages.

    Pour 17, on peut (je ne sais pas si cela est optimum)

    On lance 3 fois le dé, on interprète le premier modulo 3, les deux suivants modulo 2, ceci permet d'écrire un nombre en base 3 (de 0 à 17), si on obtient 17, on recommence (le calcul de l'espérance doit être très inférieur à 19)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #19
    Amanuensis

    Re : Tirage au sort avec un dé

    Question: Y-a-t'il une solution en un nombre borné de tirages ne serait-ce que pour N=5?
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  21. #20
    Médiat

    Re : Tirage au sort avec un dé

    Citation Envoyé par Médiat Voir le message
    On lance 3 fois le dé, on interprète le premier modulo 3, les deux suivants modulo 2, ceci permet d'écrire un nombre en base 3 (de 0 à 17), si on obtient 17, on recommence (le calcul de l'espérance doit être très inférieur à 19)
    Je corrige :
    on interprète le premier modulo 2, les deux suivants modulo 3,
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #21
    Amanuensis

    Re : Tirage au sort avec un dé

    Citation Envoyé par Médiat Voir le message
    On lance 3 fois le dé, on interprète le premier modulo 3, les deux suivants modulo 2, ceci permet d'écrire un nombre en base 3 (de 0 à 17), si on obtient 17, on recommence (le calcul de l'espérance doit être très inférieur à 19)
    Oui, effectivement N=17 n'est pas un bon exemple pour une méthode "générale". N=19 aurait été mieux.

    Plus généralement j'ai l'impression que cela dépend beaucoup de la décomposition en facteurs premiers. On peut déjà réduire en gérant les puissances de 2 et 3 directement. Ensuite, les facteurs premiers de la forme 2^p 3^q - r, avec r petit sont favorables a une méthode utilisant un tirage sur 2^q 3^p valeurs.

    Alors, les cas intéressants seraient des nombres premiers comme 7, 19, 31, 37, etc. ?
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  23. #22
    Amanuensis

    Re : Tirage au sort avec un dé

    Citation Envoyé par Médiat Voir le message
    Je corrige :
    on interprète le premier modulo 2, les deux suivants modulo 3,
    Pourquoi pas seulement deux tirs, le premier interprété modulo 6 et le second modulo 3?
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  24. #23
    Médiat

    Re : Tirage au sort avec un dé

    J'ai peur que chaque cas soit particulier :

    Pour 19 :

    On jette une fois le dé que l'on interprète modulo 3
    On jette une fois le dé
    que l'on interprète modulo 3
    , si le premier a donné 2 et le deuxième 1 ou 2, on recommence, sinon
    On jette une fois le dé que l'on interprète modulo 3
    ,
    si le premier a donné 2 et le troisième 1 ou 2, on recommence, sinon, on a obtenu un nombre en base 3 entre 0 et 18.

    Là encore, sans la calculer, l'espérance me semble très inférieur à 19 (minimum pour une technique consistant à lancer un dé par personne avant d'aller plus loin)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #24
    Médiat

    Re : Tirage au sort avec un dé

    Citation Envoyé par Amanuensis Voir le message
    Pourquoi pas seulement deux tirs, le premier interprété modulo 6 et le second modulo 3?
    Pourquoi pas, effectivement, ce qui me renforce dans mon opinion du message précédent
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  26. #25
    vgondr98

    Re : Tirage au sort avec un dé

    On peut utiliser une méthode dichotomique.
    Si on a 100 joueur, on tire le dé, mettons qu'il tombe sur 1, 2 ou 3, alors les 50 premiers joueurs sont gardés.
    Si le dé tombe sur 4, 5 ou 6 alors les 50 derniers joueurs sont gardés.
    Au deuxième tour, on retire le dé et on ne garde que 25 joueurs.
    Au troisième tour, on retire le dé et on ne garde que 12.5 joueurs.
    La on retire le dé et si le dé tombe sur 1, 2 ou 3 on ne garde que 12 joueurs, sinon on garde 13 joueurs.
    Et ainsi de suite.

    On n'est pas obligé de diviser le groupes de joueurs en 2, on peut aussi le diviser en 6.

  27. #26
    Médiat

    Re : Tirage au sort avec un dé

    Citation Envoyé par vgondr98 Voir le message
    On peut utiliser une méthode dichotomique.
    Si on a 100 joueur, on tire le dé, mettons qu'il tombe sur 1, 2 ou 3, alors les 50 premiers joueurs sont gardés.
    Très mauvaise méthode, pour certains nombres, par exemple, dès que n n'est pas une puissance de 2, vous pouvez être amené à relancer le processus (ou une partie) pour forcer l'équiprobabilité), et même pour les puissances de 2, si une puissance de 6 n'est pas trop loin, on peut améliorer par rapport à la dichotomie.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  28. #27
    Amanuensis

    Re : Tirage au sort avec un dé

    Citation Envoyé par Médiat Voir le message

    Là encore, sans la calculer, l'espérance me semble très inférieur à 19 (minimum pour une technique consistant à lancer un dé par personne avant d'aller plus loin)[/COLOR][/LEFT]
    Effectivement. Un gros pas serait fait si on pouvait montrer qu'il y a toujours une méthode en une puissance de ln N, puisque la méthode que j'indique (et de même celle dans le message #1) implique un terme en N.

    Quelque part cela semble "raisonnable", le gain de chaque tir paraissant multiplicatif (en espérant que cette idée floue soit comprise pour ce qu'elle est).
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  29. #28
    Amanuensis

    Re : Tirage au sort avec un dé

    Citation Envoyé par vgondr98 Voir le message
    La on retire le dé et si le dé tombe sur 1, 2 ou 3 on ne garde que 12 joueurs, sinon on garde 13 joueurs.
    Cela ne peut pas être "juste", les joueurs du groupe de 12 sont favorisés par rapport à ceux du groupe de 13 (si on suppose qu'ensuite ce soit "juste" groupe par groupe, ceux du premier groupe ont une proba de 1/24 d'être choisis alors que c'est 1/26 pour les autres...).
    Dernière modification par Amanuensis ; 27/02/2018 à 14h34.
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  30. #29
    ansset

    Re : Tirage au sort avec un dé

    De fait, la question pourrait avoir deux types réponses, non ?
    l'une consistant à trouver la méthode optimale qui assure à 100 % un choix équiprobable ( borne sup de n élevée mais certaine )
    une autre minimisant ( d'un point de vue probabiliste ) l'espérance du nb de tirages.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  31. #30
    Médiat

    Re : Tirage au sort avec un dé

    Sauf erreur de calcul de ma part, la technique qui consiste à écrire un nombre en base 6 (en rejetant les valeurs invalides) fonctionne toujours, avec un espérance majorée par
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Page 1 sur 3 12 DernièreDernière

Discussions similaires

  1. Question tirage au sort avec remise
    Par Satsatas dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 29/10/2014, 17h30
  2. Tirage au sort possible pour ecole vétérinaire en belgique avec bac stl
    Par Joannanageuse dans le forum Orientation après le BAC
    Réponses: 13
    Dernier message: 30/12/2013, 17h49
  3. Tirage au sort universitaire ?
    Par Amyyy dans le forum Orientation après le BAC
    Réponses: 7
    Dernier message: 28/05/2013, 15h09
  4. Veterinaire en belgique: tirage au sort
    Par drmouse13008 dans le forum Orientation après le BAC
    Réponses: 16
    Dernier message: 23/02/2012, 16h22
  5. dénombrements tirage au sort
    Par betibex dans le forum Mathématiques du collège et du lycée
    Réponses: 0
    Dernier message: 08/12/2011, 15h16