Tirage au sort avec un dé

[Juzo]

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

- Si N = 2^p3^q le nombre de lancers nécessaire est max(p;q)
- Si N = 2^p3^q5^r l'espérance du nombre de lancers est max(p;q)*r*5

Une méthode qui fonctionne pour tout N est de tirer le dé pour chaque joueur, de garder uniquement le ou les joueurs qui ont le plus gros score, puis de recommencer l'opération avec les joueurs restants jusqu'à ce qu'il y ait un "vainqueur". Par contre j'ai bien du mal à estimer l'espérance du nombre de lancers nécessaires pour cette méthode.

-----

[CM63]

Bonjour,

 Cliquez pour afficher

Tirer au sort les chiffres de l'écriture du numéro en base 6. Estimation du nombre de tirages :
Si N est juste au dessus d'une puissance de 6, on risque faire des tirages pour rien, mais bon. Si par exemple il faut tirer un chiffre parmi {0,1}, on va se contenter de la parité du résultat, etc.
Même problème si N n'est pas divisible par 6.

[ansset]

@CM63:
question sous spoiler car en référence à sa proposition.

 Cliquez pour afficher

bjr, l'approche par les congruences me semble effectivement la plus directe.
mais comment en arrives tu à ce résultat ?

[Médiat]

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)

[A voir en vidéo sur Futura]

[Médiat]

Pour être concret :

 Cliquez pour afficher

Avec 8 personnes, si on compte en base 6, on lance 2 fois le dé, mais il y a plus de 4 chances sur six que l'on doive recommencer.
Si on compte en base 3, on lance 2 fois le dé et c'est fini !

[vgondr98]

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.

[ansset]

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.

[Juzo]

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é.

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.

[CM63]

 Cliquez pour afficher

La remarque de Mediat est juste, avec ma méthode on peut perdre du temps car tous les chiffres entre 0 et 5 ne sont pas forcément utilisés pour représenter N en base 6. Le système ne sera vraiment efficace que si N est une puissance de 6, ou une somme de puissances de 6. Quant à l'évaluation du nombre de tirages nécessaires, c'est (majoré par) le nombre de chiffres qu'il faut pour représenter N en base 6, c'est de l'ordre de .

[ansset]

certes, mais ce n'est pas "équiprobable" .

[Médiat]

Si on obtient 00 il faut relancer les dés non ?

Je voulais dire 9 joueurs numérotés de 0 à 8

[vgondr98]

 Cliquez pour afficher

Un autre système consiste à demander à chaque joueur d'écrire un numéro à 5 chiffres sur un papier (le 5 est arbitraire). Les chiffres étant bien sûr 1,2,3,4,5,6. Celui qui se rapproche le plus commence la partie.

[CM63]

certes, mais ce n'est pas "équiprobable" .

 Cliquez pour afficher

Si car on laisse tomber les chiffres sans intérêt.

[ansset]

merci pour ta réponse mais je n'ai pas compris.

[CM63]

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

[Amanuensis]

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.)

[Amanuensis]

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.

[Médiat]

Bonjour,

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)

[Amanuensis]

Question: Y-a-t'il une solution en un nombre borné de tirages ne serait-ce que pour N=5?

[Médiat]

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,

[Amanuensis]

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. ?

[Amanuensis]

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?

[Médiat]

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)

[Médiat]

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

[vgondr98]

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.

[Médiat]

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.

[Amanuensis]

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).

[Amanuensis]

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...).

[ansset]

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.

[Médiat]

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