Nombres dans un chapeau

[Sylvestre]

Bonjour,

Je suis en train de lire "Problèmes pour mathématiciens petits et grands" de Paul Halmos (c'est un vrai bijou ce livre) et je suis tombé sur le problème suivant qui m'a l'air vraiment incroyable :
On a 100 nombres réels distincts dans un chapeau. On n'a aucune idée de l'amplitude de ces nombres. Ensuite, on a le droit de tirer des nombres un à un du chapeau et de les regarder à chaque fois. A chaque tirage, on peut soit continuer à tirer et dans ce cas, on jète le numéro tiré, soit s'arrêter et dans ce cas, on termine avec le nombre que l'on a en main. Le but du jeu est de terminer avec le plus grand nombre du chapeau dans les mains. Il faut payer un franc pour jouer à ce jeu et on en gagne 5, si on gagne. La question du livre est "Est-ce que cela vaut la peine ? ". Je n'ai pas encore lu la solution à la fin du livre, et j'aimerais beaucoup partagé mes réflexions sur ce problème avec vous avant de le faire. Pour l'instant, je me suis dis que l'on pouvait tirer n numéros (n à déterminer) et une fois ceci fait, tirer les autre jusqu'à ce qu'on obtienne un nombre plus grand que le maximum des n premiers. J'ai calculé que l'on a un peu plus d'une chance sur 4 de gagner avec n=50, mais j'ai encore deux problèmes.
1) Comment trouver le meilleur n ?
2) Est-ce que c'est vraiment la meilleure stratégie (ce dont je doute, car c'est moi qui l'ai trouvée) ?

Merci pour vos réflexions
-----

[matthias]

pour la question un (le meilleur n), si tu as calculé la probabilité de gagner pour n = 50, tu dois pouvoir étendre ton calcul à un n quelconque facilement, non ?

[Sylvestre]

pour la question un (le meilleur n), si tu as calculé la probabilité de gagner pour n = 50, tu dois pouvoir étendre ton calcul à un n quelconque facilement, non ?

Oui, c'est vrai, j'ai fait les calculs et je crois que je trouve n=37 (sauf erreur). Mais c'est en tatonnant, et j'aimerais bien savoir s'il y a un moyen de trouver cette valeur pour tout n.
Et il reste toujours la question de savoir si c'est la meilleure stratégie.

[matthias]

Oui, c'est vrai, j'ai fait les calculs et je crois que je trouve n=37 (sauf erreur). Mais c'est en tatonnant, et j'aimerais bien savoir s'il y a un moyen de trouver cette valeur pour tout n.
Et il reste toujours la question de savoir si c'est la meilleure stratégie.

Je suis en train de regarder, mais c'est pas évident à calculer comme proba. Tu as fait comment ?
Pour la stratégie, aucune idée.

[A voir en vidéo sur Futura]

[Sylvestre]

Je suis en train de regarder, mais c'est pas évident à calculer comme proba. Tu as fait comment ?
Pour la stratégie, aucune idée.

Ben, en fait, j'ai regardé la probabilité que le second plus grand nombre soit dans les n premiers et pas le plus grand. Cela donne une minoration de la probabilité de gagner et après j'ai un peu améliorer le programme pour qu'il tienne compte d'autres cas, où l'on peut gagner.

[matthias]

Ben, en fait, j'ai regardé la probabilité que le second plus grand nombre soit dans les n premiers et pas le plus grand. Cela donne une minoration de la probabilité de gagner et après j'ai un peu améliorer le programme pour qu'il tienne compte d'autres cas, où l'on peut gagner.

C'est une approximation alors ?

On peut essayer de faire le calcul exact.
On appelle X_i la valeur lue au tirage i
X_M = max {X_i} (i <= 100)
X_m = max {X_i} (i <= n)

On cherche la probabilité de:
M > n et pour tout i tel que n < i < M, X_i < X_m

Je ne sais pas si c'est la meilleure approche ...

[Sylvestre]

C'est une approximation alors ?

On peut essayer de faire le calcul exact.
On appelle X_i la valeur lue au tirage i
X_M = max {X_i} (i <= 100)
X_m = max {X_i} (i <= n)

On cherche la probabilité de:
M > n et pour tout i tel que n < i < M, X_i < X_m

Je ne sais pas si c'est la meilleure approche ...

C'est très juste, il doit être possible d'utiliser une approche consistant à essayer toute les possibilités (en améliorant un peu pour éliminer des cas), mais j'aimerais bien pouvoir le faire de manière théorique. Et là-dessus, je bloque sérieusement. Pour l'instant, je n'ai pas grand chose de plus que ce que tu as décris et pourtant j'y ai déjà passé pas mal de temps. Je persévère...

PS : Si jamais tu essaies de faire un programme qui calcule la proba exacte, je serais très intéressé pour le faire ensemble.

[Sylvestre]

Salut,

juste pour vous donner des nouvelles sur mes avancées sur ce problème. J'ai réussi à trouver une formule donnant la probabilité que la stratégie que j'ai indiquée dans le premier message fonctionne.
Voici comment j'ai fait

Soit n, le nombre de nombres dans le chapeau.
La stratégie consiste à tout d'abord sortir a nombres du chapeau, ensuite à regarder quel est le plus grand de ces a nombres, et enfin de continuer à tirer jusqu'à ce qu'un nombre plus grand que ce maximum sorte. Si cela, n'arrive pas, on garde le dernier.

Voici comment j'ai procédé pour calculer la probabilité de succès.
Pour fixer les idées, je suppose que les nombres du chapeau sont numérotés de 1 à n.

Supposons que le nombre maximum dans les a premiers nombres soit k. Quelle est la probabilité de succès dans ce cas ? Pour gagner, il suffit de regarder le placement des n-k nombres plus grands que k sur les n-a dernières places. En effet, on gagne si et seulement si le plus grand nombre est le premier apparaissant dans cette liste de n-k nombres. Donc la probabilité est 1/(n-k).

Maintenant, il faut encore calculer la probabilité que le maximum des a premiers nombres soit k. Il s'agit de combinatoire. Premièrement, le nombre k doit être dans les a premiers nombres : probabilité a/n.
Deuxièmement, les n-k nombres plus grands que k doivent être dans les n-a dernières places : nombre de possibilités . De plus, le nombre de façon de placer ces n-k nombres au total est (c'est n-1 plutôt que n, car le nombre k est déjà placé).
La probabilité que le maximum parmis des a premiers nombres soit k est donc

et la probabilité de gagner dans ce cas est
.
On fait alors la somme sur k de a à n-1 et, après simplification, on obtient que la probabilité de gagner est



Bon, maintenant, il me faut voir s'il est possible de trouver une forme fermée de cette formule. Quelqu'un voit comment faire ?