Le plus grand ...

[Médiat]

Bonjour,

Le jeu est le suivant : des nombres entiers relatifs tous différents sont écrits sur des feuilles de papiers, le jeu consiste à en consulter un certain nombre, une par une, puis à affirmer que le dernier effectivement découvert est le plus grand de toute la pile.

Il n'y a aucun moyen de savoir d'avance ce qu'il y a d'écrit sur une feuille, aucun moyen de connaître le minimum, le maximum, la moyenne, la répartition de ces nombres (autrement dit, on ne peut rien déduire de la connaissance des nombres déjà vus quant à la distribution de ces nombres). Le choix des nombres est laissé à un être humain, mais l'ordre dans lequel ils sont présentés est purement aléatoire.

1) Quelle stratégie adopter ?
2) Si on fixe le nombre de feuilles à 120 quelle est la probabilité de gagner.

Personnellement je suis arrivé à 37.053% (sans aucune preuve que c'est la meilleure solution).

Peut-on faire mieux ?

PS : c'est un classique, certains doivent connaître.

[danyvio]

Chic ! de la combinatoire ! En première analyse (mais il est déjà tard!) il faut pour chacune des 120! arrangements déterminer où est le plus grand nombre, et calculer la proba pour que le plus grand soit au rang 1 ou 2 ... 120. La suite au prochain numéro....

[danyvio]

La nuit portant conseil... Je pense que chaque fois qu'on trouve un nombre plus grand que tous ceux qu'on a trouvé précédemment, on [ré]-value le classement de ces nombres. Je m'explique : on a tiré dans l'ordre 8,1,7,15,2,85

Le classement provisoire (en appelant 1er le plus grand nombre, puis 2ème etc.) est

3,6,4,2,5,1
Il faut alors calculer le nombre d'arrangements dont les 6 premiers nombres sont classés ainsi, comparés aux 120 ! et ainsi apprécier la proba d'apparition.
Si cette proba n'est pas satisfaisante, on continue le tirage. Supposons qu'on tire alors 14 puis 97. Pour la séquence 8,1,7,15,2,85, 14, 97 le nouveau classement provisoire devient :

5,8,6,3,7,2,4,1 et on refait le calcul....
L'approche est-elle bonne ?

[homotopie]

E(nombre/nombre célèbre)
Si avec un indice pareil, on ne trouve pas...

[Médiat]

Envoyé par homotopie

E(nombre/nombre célèbre)

C'est effectivement ce que je trouve, mais je n'ai pas la preuve que cette stratégie est la meilleure. L'as-tu ?

[homotopie]

Envoyé par Médiat

C'est effectivement ce que je trouve, mais je n'ai pas la preuve que cette stratégie est la meilleure. L'as-tu ?

Malheureusement non.

[homotopie]

Envoyé par danyvio

Le classement provisoire (en appelant 1er le plus grand nombre, puis 2ème etc.) est

3,6,4,2,5,1
Il faut alors calculer le nombre d'arrangements dont les 6 premiers nombres sont classés ainsi, comparés aux 120 !

As-tu fait attention que ceci ne dépend pas de l'ordre des 5 premiers ?

Envoyé par danyvio

L'approche est-elle bonne ?

pour un traitement complet, peut-être, mais tu devrais trouver une simplification.

[danyvio]

J'efface tout ce que j'ai écrit et on recommence !!
Quand au tirage n je retourne une carte supérieure à toutes les précédentes, la proba qu'elle soit la plus grande des 120 est alors 1/(121 - n).
Etes-vous OK ?
A partir de là : Un indice SVP (peut être suggéré précédemment mais ...)

[homotopie]

Envoyé par danyvio

J'efface tout ce que j'ai écrit et on recommence !!
Quand au tirage n je retourne une carte supérieure à toutes les précédentes, la proba qu'elle soit la plus grande des 120 est alors 1/(121 - n).
Etes-vous OK ?

Essaye avec N=3 ou 4.
Perso j'obtiens pour N=3 et n=2, 2/3 au lieu d'1/2.
pour N=4 et n=2, 1/2 au lieu d'1/3 et N=4, n=3, 6/8=3/4 au lieu de 1/2.

[danyvio]

Soient N cartes (ou morceaux de papier, mais c'est + court à écrire)
J'ai établi (?) que la probabilité pour que la carte tirée au tirage t, (à condition d'être la plus grande des cartes n° 1 à t-1), soit la plus grande de toutes, est de t/N.
Mais j'ai une réticence : ci dessus est vrai statistiquement, basé sur l'ensemble des arrangements possibles, alors que lorsqu'on lit des cartes, on a une connaissance réelle des (t-1) premières cartes,
Enfin je ne vois pas la stratégie optimale Aidez moi à ne pas faire d'insomnie...

[homotopie]

Envoyé par danyvio

Soient N cartes (ou morceaux de papier, mais c'est + court à écrire)
J'ai établi (?) que la probabilité pour que la carte tirée au tirage t, (à condition d'être la plus grande des cartes n° 1 à t-1), soit la plus grande de toutes, est de t/N.
Mais j'ai une réticence : ci dessus est vrai statistiquement, basé sur l'ensemble des arrangements possibles, alors que lorsqu'on lit des cartes, on a une connaissance réelle des (t-1) premières cartes,
Enfin je ne vois pas la stratégie optimale Aidez moi à ne pas faire d'insomnie...

La stratégie optimale est du type à partir de deux critères :
a) il faut que le dernier sorti soit plus grand que les précédents (on s'en doutait)
b) le numéro de sortie de ce nombre doit être dans un ensemble choisi d'avance (on ne préoccupe pas de savoir quel ordre avaient les n(n-1) 1ères cartes).

Il est plus ou moins évident que pour n petit on ne prend pas (les chances sont bien trop faibles), il faut donc laisser passer quelques cartes.
Vers la fin on se décide si a) est remplie les chances sont très fortes.
Si on ne prend que les "grands" n on a beaucoup de chance que lorsqu'on se décide mais dans peu de cas, si on prend n trop petit alors dans beaucoup de cas on se décide avec peu de chance de succés.
A partir de ces indices, essaie d'établir une stratégie d'essai puis tente de calculer au moins approximativement les chances de succés, puis affine.
Il faut trouver le bon équilibre. (J'espère que tu as des possibilités de programmer ou d'établir des listes de nombres, type Excell sinon ça va être dur ).

[homotopie]

Envoyé par Médiat

C'est effectivement ce que je trouve, mais je n'ai pas la preuve que cette stratégie est la meilleure. L'as-tu ?

J'ai désormais un résultat partiel :

 Cliquez pour afficher

Après avoir trouver un moyen de modéliser ce qu'est une tactique ou stratégie, je montre successivement que :
a) la meilleure tactique est du type où on ne chosit que si le dernier est le plus grand de tout ceux déjà sortis (je crois que j'ai pulvérisé un record de trivialité)
b) aucune tactique n'est meilleure qu'une des tactiques basées sur une prise de décision basée uniquement sur les deux critères : i) le dernier sorti est plus grand que ceux déjà sortis et ii) le rang n du dernier sorti fait parti d'une liste préétabli L (donc une prise de décision indifférente de l'ordre des (n-1) premiers sortis)
c) parmi les tactqiues du type précédent et pour un cardinal de L donné, la meilleure tactique (strictement dans la plus part des cas) est une tactique du type précédent avec L={n>=n₀}
a) et b) ne présentent qu'une difficulté d'écriture formelle, c) (on peut alléger le formalisme à ce niveau) est un peu plus calculatoire mais une fois que l'on a exprimé la probabilité il est trivial que pour un nombre donné la tactique s'améliore toujours si on peut augmenter un rang dans L.

Reste le plus dur au niveau calculatoire. Montrer la valeur optimale de n₀

[danyvio]

Ceci n'est pas la solution, mais une réflexion. Je maintiens que si la carte du tirage t est la plus grande de celles déjà vues, la proba pour qu'elle soit la plus grande de toutes est t/N. Mais, et c'est là que je réfléchis si on continue à tirer des cartes, on considère que la dernière tirée devient la première d'un problème sur (N-t+1) cartes. Est-ce une bonne piste ?

[Médiat]

Envoyé par danyvio

Ceci n'est pas la solution, mais une réflexion. Je maintiens que si la carte du tirage t est la plus grande de celles déjà vues, la proba pour qu'elle soit la plus grande de toutes est t/N. Mais, et c'est là que je réfléchis si on continue à tirer des cartes, on considère que la dernière tirée devient la première d'un problème sur (N-t+1) cartes. Est-ce une bonne piste ?

Si j'ai bien compris :

 Cliquez pour afficher

Ta stratégie consisterait à regarder n₀ nombres, si c'est le plus grand on s'arrête, sinon on continue jusqu'à trouver un plus grand, si c'est bien cela, c'est exactement la solution proposée par homotopie (et la mienne ), par contre, pour ce qui me concerne, j'ai fait les calculs dans une autre optique, et le résultat est facile à obtenir ; ce qui est compliqué, c'est de trouver l'optimum de cette fonction de 2 variables (avec une somme sur une 3ième), personnellement, je n'ai pas d'autre solution que les calculs explicites .

[homotopie]

J'ai réussi à complètement caractériser la meilleure tactique et à montrer le résultat classique du moins tendanciellement.
Je rédige et je poste a priori demain.

[Médiat]

Envoyé par homotopie

J'ai réussi à complètement caractériser la meilleure tactique et à montrer le résultat classique du moins tendanciellement.
Je rédige et je poste a priori demain.

Ca va être dur de tenir jusque là .

[danyvio]

Envoyé par homotopie

J'ai réussi à complètement caractériser la meilleure tactique et à montrer le résultat classique du moins tendanciellement.
Je rédige et je poste a priori demain.

Moi aussi je vais rester les z'yeux rivés sur mon écran.

[Sylvestre]

Bonjour,

J'ai retrouvé un thread où on parlait de ce problème : http://forums.futura-sciences.com/thread36918.html