Tirage au sort avec un dé

[Amanuensis]

Après réflexion, il me semble que tous les éléments de démo sont dans le message #59. On aurait la démo suivante:

Soit un algorithme quelconque, et N>1 le nombre de candidats

a) Soit une suite de i valeurs parmi 6 (i tirages), on dit que cette suite termine pour l'algorithme si celui-ci permet de décider d'un candidat, à une étape quelconque, pas nécessairement la ième.

b) On note p(i) la proportion des suites qui ne terminent pas, avec par convention p(0)=1

c) [Exercice de combinatoire] la moyenne du nombre de tirs à la terminaison est

d) La contrainte d'équité impose multiple de N, et donc

e) On a donc

Conclusion:

Est optimal tout algorithme qui est tel que la moyenne du nombre de tirs à terminaison est

----

Si cela est correct ainsi que le calcul d'espérance donné précédemment pour un algorithme décrit, la question message #1 est répondue.
-----

[ansset]

merci à vous, j'ai pris plaisir à réfléchir dans mon coin à cette énigme subtile et à sa proposition de résolution astucieuse.

[Amanuensis]

Personne pour infirmer ou confirmer?

Je vais considérer le sujet clos pour moi, alors.

[Juzo]

Bonjour Amenensuis, j'avais commencé à rédiger une longue réponse mais pouvez-vous déjà détailler comment vous obtenez ? Merci

c) [Exercice de combinatoire] la moyenne du nombre de tirs à la terminaison est

[verhaeghe]

Bonjour et merci pour cet excellent problème.

Voici ma proposition sachant que je n'ai lu que l'énoncé et donc que je m'excuse par avance d'être redondant avec d'autres.

La première chose que l'on voit est qu'en fonction du nombre de joueurs au départ, il y a certains nombres particulièrement favorisés (les puissances de 6 par exemple).

On voit aussi que les multiples de 2 ou 3 des puissances de 6 peuvent être facilement déterminés mais pour les autres?

Voici une proposition qui ce veut efficiente et élégante
Prenons par exemple 50:
regardons quelle puissance de 6 est immédiatement au dessus : 6^3 soit 216
On donne alors à chaque jour 4 nombres entre 1 et 200 (le premier a 1;2;3;4, le deuxième 5;..;8 et ainsi de suite)
On fait 3 tirages de dés dont les résultats sont p,q et r et l'on dit que le résultat est p+(q-1)x6+(r-1)x6^2 ce qui nous fait une belle distribution aléatoire entre 1 et 216

on a donc 200 chances sur 216 d'avoir réussi à trouver un nombre permettant de déterminer le premier et si on a pas de bol (16/216), on recommence.
Le nombre de tirages nécessaires est donc de 3 x (1+ 16/200 + (16/200)^2 + ... + (16/200)^n) ce qui fait 3 x ( 1 + 16/184) tirages en moyenne

il faudrait faire sous excel une petite macro pour tester tous les nombres mais je dirais:
nb de participants / nb d'essais statistiquement nécessaire
1 / 0
2 / 1
3 / 1
4 < 2
5 < 2
6 / 1

7 à 35 / >2 et < 3 sauf pour
12 / 2
18 / 2
36 / 2

de 37 à 215 / >3 <4 sauf pour
72 / 3
108 / 3
216 / 3

et ainsi de suite