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 ?

[invite35452583]

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

[A voir en vidéo sur Futura]

[Médiat]

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 ?

[invite35452583]

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.

[invite35452583]

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 ?

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

[invite35452583]

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

[invite35452583]

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

[invite35452583]

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]

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 .

[invite35452583]

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]

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]

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.

[invite6acfe16b]

Bonjour,

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

[invite35452583]

Bonjour,

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

Oui, j'avais ouvert aussi un sujet dessus (en laissant de la marge par rapport au résultat optimal).
Ta manière de calculer la probabilité est la même que j'avais jusqu'à présent mais elle n'est pas pratique pour montrer le caractère optimal de cette tactique.

[invite35452583]

Et maintenant, la preuve (merci à danyvio pour m'avoir donné la clé, il fallait encore trifouiller un peu la serrure )

C’est forcément assez formel par moment, désolé.

1) Modélisons :

Soit E l'ensemble des nombres, le cardinal de E est noté N.
On note S_N(E) l'ensemble des séquences de E, ou autrement dit l'ensemble des bijections de {1,...,n} dans E.
D'après les hypothèses chacune de ces séquences a une probabilité égale à 1/N!, N! étant le cardinal de S(E).

Pour un entier n compris entre 1 et N et pour une séquence w on note [w]_n la séquence tronquée (w(1),w(2),...,w(n)).
Rangé dans l'ordre décroissant on a w(f_n(w,1))>w(f_n(w,2))>...>w(f_n(w,i))>...>w(f_n(w,n)). f_n(w,-) est une bijection de {1,…,n} pour tout w et tout n.
On pose R_n(w)=( f_n^-1(w,1),…, f_n^-1(w,i),…, f_n^-1(w,n)). (A i, on attribue la place de w(i) dans le classement précédent).
En particulier, on note X_n(w)= f_n^-1(w,n).

Une tactique ne peut être définie qu'à partir des images des séquences w par les différentes applications R_n car celle-ci regroupe toute l'information que l'on a sur E à un moment donné par hypothèse.
Celle-ci va donc consister à définir un certain nombre de séquences v_i de {1,...,n_i}, celles pour lesquelles on choisit le dernier nombre sorti.
On note V l'ensemble des v_i, n_i est appelé la longueur de v_i.
Comme le « jeu » s’arrête lorsqu’une séquence v de V apparaît, ceci impose que les sont disjoints (on appellera cela la condition d’exclusion).

La probabilité qu'une tactique donnée trouve le plus grand nombre, on appellera cette probabilité efficacité de la tactique, est donc égal à
où P(gain/v_i) est la probabilité que le n_i^ème nombre soit le plus grand sachant que R_ni(w)=v_i.

2) la famille des X_n

a) “lemme fondamental“ : les X_n sont indépendants
Pour cela il suffit de montrer que pour tout N-uplet (m₁,…, m_i,…, m_N) de {1}x{1,2}x…x{1,2,…,i}x…x{1,…,N } l’intersection des (X_n= m_n) est de cardinal égal à 1.
w(N) est le m_N^ème plus grand de E donc est déterminé de manière unique.
Supposons que w(N), …,w(n+1) soient déterminés pour 0<=n<N, alors w(n) est le m_n ^ème plus grand de E privé de {w(N),w(N-1),…,w(n+1)} qui est de cardinal n donc est déterminé de manière unique.
Ainsi, il existe une et une seule séquence de S(E) w dans l’intersection.

Pour ceux qui ne sont pas habitués à ce type de résultat, soit une famille M_n de {1,…,n} n allant de 1 à N, les séquences vérifiant X_n est dans M_n pour tout n de 1 à N sont en cardinal égal à card(M₁)xcard(M₂)x…xcard(M_n)x…xcard(M_N) soit une probabilité égale à cette dernière égalité étant obtenue en reprenant ce qui précède en prenant M_m={1,…,m} pour tous les m distincts de n. On peut remarquer ici que les X_n suivent une loi d’équiprobabilité.

b) une tactique peut être entièrement décrite par les X_n
En effet, soit v un élément de V de longueur n. Pour une séquence de et pour tout 1<=m<=n, la place de w_m dans {w(1),…,w(m)} est complètement déterminée par v (exemple si v=(4,1,3,2,5) w(1)=1, w(2)=1, w(3)=2, w(4)=2, w(5)=5).
De même, pour un n-uplet (m₁,…, m_n) de {1}x…x{1,…,n} il existe une unique séquence de {1,..,n} pour laquelle, avec un abus de notation, X_k= m_k pour tout k.
.
Désormais une tactique sera la donnée des (m₁,…, m_n).

3) Caractérisation du type d’une des tactiques les plus efficaces (l’unicité ou non sera vue après)
il va être montré successivement
a) une des tactiques les plus efficaces est « non idiote » : pour tout M dans V de longueur m_n=1
b) une des tactiques les plus efficaces est du type a) et telle qu’il existe une sous-partie L de {1,..,N}
telle que V={ (m₁,…, m_n) ; n soit dans L et m_n=1 et de plus pour tout p dans L<n, m_p est distinct de 1}
Autrement dit la tactique est du type : on s’arrête dès que le dernier sorti est le plus grand des sortis et son rang est dans L.
c) pour les tactiques du type b) et pour un cardinal de L fixé, la tactique la plus efficace est celle pour laquelle L est du type {n>= n₀}
En partie 4), on déterminera quelle est la plus ou les plus efficaces des type c).

Le a) est juste pour l’exigence de rigueur un lecteur pressé peut sauter cette étape évidente.
a) soit une tactique « idiote », il existe M=(m₁,…, m_n) avec m_n distinct de 1. On considère la tactique intiale modifié en supprimant ce M.
L’efficacité est inchangée car P(gain/ (m_n distinct de 1))=0.
De plus, si n<N, on peut ajouter à V (m₁,…, m_n,1), cela respecte trivialement la condition d’exclusion et augmente strictement l’efficacité (évident).
Les seules tactiques « idiotes » qui peuvent être parmi les plus efficaces sont celles qui contiennent des (m₁,…, m_N) avec m_N distinct de 1.

b) par récurrence sur l’hypothèse : on peut toujours trouver une tactique au moins aussi efficace du type suivant :
la tactique est « non idiote « et il existe pour un entier 1<n<N une sous-partie L de {1,..,n}
telle que les éléments de V de longueur strictement inférieure à n={ (m₁,…, m_p)
tels que p soit dans L et m_p=1 et de plus pour tout q dans L<p, m_q est distinct de 1}.

Pour n=2, c’est toujours le cas car il n’y a qu’un élément de longueur 1 : (1) et que la condition pour les longueurs inférieures est caduque.

Supposons que ce soit vrai pour un certain n.
Si tous les éléments M, de la forme (m₁,…, m_n) avec n dans L et m_n=1 et de plus pour tout p dans L<n, m_p est distinct de 1,
sont tous dans V ou aucun dans V alors il est clair que l’hypothèse est également vérifiée au rang n+1.
Sinon, les éléments de ce type qui sont dans V sont notés M les autres sont notés M’.
On appelle efficacité en M la probabilité P(M).P(gain/M).
On appelle tactique en M’, les éléments de V =(m’₁,…, (m’₁,…, m’_n), m’’_n+1,…, m’’_p) (bref ceux qui « commencent par M’ »).
On appelle efficacité en M’, la probabilité :
,
où les M'' sont les éléments de la tactique en M'.
Cette dernière est égale vu l’indépendance des X_n à
.

Maintenant soit la tactique initiale à laquelle on supprime tous les éléments de la tactique de M’ et à laquelle on ajoute M’.
Pour les éléments de plus grande longueur la condition d’exclusion pour M’ est vérifiée car on a supprimé tous les éléments qu’il fallait,
pour les éléments de plus petite longueur c’est par hypothèse sur M’.
La différence d’efficacité entre la nouvelle et l’initiale est égale à efficacité en P(M’)P(gain/M’)-efficacité en M’,
mais comme les X_n sont indépendants et suivent une loi d’équiprobabilité P(M’)=P(M) et
,
le même calcul pour P(gain/M) aboutit au même résultat donc P(gain/M)=P(gain/M’) (=n/(n+1) x (n+1)/(n+2) x…x (N-1)/N=n/N ) qui ne dépend donc que de la longueur).
La différence d’efficacité est donc égale à efficacité en M-efficacité en M’.

De même, on modifie la tactique initiale en retirant M et en ajoutant les éléments M’’’
tels qu’il existe un élément M’’ de la tactique de M vérifiant
m’’’_p= m_p pour p<=n et pour p>n m’’’_p= m’’_p.
Ces éléments entre eux vérifient la condition d’exclusion car le vérifier avec « M’’ comme début »,
la vérifient avec les autres éléments car ceux-ci la vérifient par rapport au « début M ».
Cette fois, on a pour différence d’efficacité = efficacité en M’-efficacité en M
pour les mêmes raisons d’indépendance et d’équiprobabilité des X_n.

Ainsi, si aucune tactique en M’ n’est strictement plus efficace que celle en M on modifie toutes les « sous-tactiques » selon la 1ère modification.
Sinon, on modifie toutes les tactiques en M selon la plus efficace des tactiques en M’.
(On peut aussi modifier les M’ moins efficaces mais on a déjà montré que c’est vrai au rang n+1).
La nouvelle tactique obtenue vérifie désormais l’hypothèse au rang n+1 et est au moins aussi efficace.

c) Désormais l’efficacité pour L={n₁,…, n_m}, écrit dans l’ordre croissant est égale, vue la loi d’équiprobabilité des X_n et du fait que P(gain/M) ne dépend que de la longueur de M à la somme de k=1 à m probabilité de gagner au rang n_k=

Si pour un certain k compris entre 1 et m, n_k+1 n’est pas dans L, on considère L’=L auquel on retire {n_k} et auquel on ajoute {n_k+1}. Les probabilités de gagner à un rang n_i i<k reste inchangées, idem pour i=k,
mais pour i>k, le facteur est remplacé par qui est strictement supérieur.
L’efficacité de la tactique de type c) avec L’ est pus grande que celle avec L.
Si n_k= n_m avec m>1, on le glisse vers la droite, ça ne modifie rien puis on glisse n_m-1 ce qui augmente strictement l’efficacité.
Ainsi, à cardinal égal=m, la liste la plus efficace, strictement sauf si m=1, est celle du type L={n>= n₀} pour un certain n₀.

4) Détermination de la meilleure tactique de type c)
On reprend le calcul fait précédemment, on a dans ce cas pour l’efficacité :

Ca se télescope.

On a en notant Eff(n₀) l’efficacité pour L={n>=n₀} :
Que l’on obtient en triturant la formule
ou en remarquant que la probabilité pour les rangs >=n₀ est multipliée par (n₀-2)/(n₀-1) et celle en n₀-1 vaut 1/N.
D’où
Tant que 1/(n₀-1)+...+1/(N-1) <1 Eff(n₀-1)>Eff(n₀)
Dès que 1/(n₀-1)+…+1/(N-1) >1 Eff(n₀-1)<Eff(n₀)
La tactique la plus efficace est celle pour laquelle n₀ est le plus petit pour lequel 1/(n₀-1)+…+1/(N-1)>=1 et au cas où cette somme vaut exactement 1 également pour ce même n₀-1.

5) La question de l'unicité ou liste exhaustive des meilleures tactiques

On a vu pour le type a) que l'on peut améliorer strictement pour les tactiques "idiotes" sauf éventuellement si l'"idiotie" a lieu pour des fins en n=N. Pour ces dernières on peut considérer que ceci n'est pas une véritable non-unicté (prendre lernier ou non en sachant qu'il n'est pas le plus grand il n'y a pas de grande différence).
Pour les tactiques de type b) on peut aussi améliorer strictement, sauf si la tactique a un L qui est un singleton : ce n'est de toute façon une meilleure tactique que pour N= 1 ou 2 car dès N=3 il faut s'arrêter à un des deux derniers, pour n=2 1/(n-1)=1 dès lors la somme 1/(n-1)+...+1/N-1 est supérieure à 1 mais 1/N-1 ne suffit pas donc on est entre n₀=2 et n₀=N-1 donc au moins deux éléments dans L.
Reste les tactiques de type a). Supposons qu'il existe une tctique "non idiote" qui soit aussi performante que la meilleure décrite ci-avant mais qui n'est pas de type b). Il existe un rang n et deux n-uplets M=(m₁,...,m_i,..,m_n) et M'=(m'₁,...,m'_i,...,m'_n) un dans la tactique l'autre pour lequel aucune troncature ((m'₁,...,m'_k) ne soit dans la tactique mais n'est pas lui-même dans la tactique. La même efficacité implique que eff(M)=eff(M'). Mais maintenant la tactique en M' peut être rendu de type b) "localement" en utilisant la même même méthode que précédemment, celle-ci est alors "localement" de type c) car est censé être la plus efficace possible. D'où en divisant par Eff(M) et Eff(M') par P(M)=P(M'), on a P(gain/M)=P(gain/M'). La 1ère est égale à n/N. La seconde en reprenant ce qui a été fait au 4) est :
+) égale à si n<n₀ (n₀-1)/N (1/(n₀-1)+ ...+ 1/(N-1))>= (n₀-1)/N x1>n/N il n'y a pas égalité entre les efficacités, il y a une tactique "locale" strictement meilleure que prendre le dernier sorti.
sauf si n=n0-1 et 1/(n0-1)+...+1/(N-1)=1 cas pour lequel il y a égalité.

+) égale à si n>=n₀ ((n+1)-1)/N)x (1/(n+1)-1) +...+1/(N-1)) car on n'aboutit jamais à la somme des inverses>=1, la meillure tactique "locale" possible est donc de prendre le dernier sorti s'il est le plus grand des sortis à tous les rangs. Mais comme la somme ci-dessus est inférieure à 1 (strictement) et que n>=n₀ la tactique de prendre le dernier sorti est strictement plus efficace que toute autre tactique "locale".

[invite35452583]

Conclusion :
si pour n₀, on a 1/(₀-1)+...+1/(N-1)>1 alors il y a unicité pour la meilleure tactique "non idiote"
si pour n₀, on a 1/(₀-1)+...+1/(N-1)=1 alors toute tactique du type :
on prend le dernier sorti si le rang est >=n₀
on ne le prend pas si n<n₀-1
en n₀-1 on prend ou non
fait parti des tactiques les plus efficaces.

6) et notre nombre célèbre dans tout ça ?
On a d'abord

Donc
On a également :
donc
Finalement N/e < n₀ < N/e +(2-1/e)
Encadrement que l'on peut certainement amélioré à un point tel que l'encadrement soit de largeur inférieur à 1 (ce qui excluerait par là même le cas de la non unicité).
On a bien n₀/N tend vers 1/e et l'efficacité de la meilleure tactique tend vers (1/e) x1=1 car n₀/N tend vers 1/e et la somme 1/(n₀-1)+...+1/N-1 n'est pas plus éloignée de 1/(n₀-1) de 1.
Faire attention ici n₀ est le rang à partir duquel on s'arrête dès que l'on a un plus gros.
Attention 44 pour N=120, est n₀-1 la quantité de nombres de e qu'on laisse passer dans tous les cas. (n₀=45 pour N=120).

[danyvio]

Ben dis donc, Homotopie, quand tu te lances, il faut te suivre... Je vais renouveler le stock d'aspirine puis étudier ta démo. Cordialement...

[invite35452583]

Ben dis donc, Homotopie, quand tu te lances, il faut te suivre... Je vais renouveler le stock d'aspirine puis étudier ta démo. Cordialement...

Je n'ai jamais dit qu'elle était simple (quoique) et courte (là il n'y a pas photo elle ne l'est pas), bon courage .

L'esprit devant être libéré des efforts de rédaction, j'ai trouvé comment montrer que la somme des inverses d'entiers consécutifs n'est jamais un entier et donc en particulier toujours distinct de 1 (il y a donc unicité de la meilleure tactique "non idiote") sauf dans un cas : 1/1.
Soit n le plus petit, n le plus grand. Si n=N distinct de 1 alors la somme est égale à l'inverse d'un entier1 donc n'est pas un entier.
Si N>n, il existe au moins un nombre pair, soit a la plus grand exposant de 2 dans la décomposition des nombres de n à N. Il existe un unique m entre n et n tel que a soit l'exposant de 2 dans la décomposition de m. En effet,, supposons qu'il y en ait deux m et m' ainsi. On a m=2^ap et m'=2^ap' avec p et p' impairs par maximalité de a, on peut supposer m<m'. Comme p et p' sont deux impairs distincts car m et m' le sont, il existe un nombre pair k entre p et p', on a n<=m<2^ak<m'<=N mais l'exposant de 2 dans 2^ak est strictement supérieur à a car k est pair, contradiction. Le nombre m=2^ap de plus grand exposant 2 est donc unique. On peut alors sommer les inverses de tous les autres en le ramenant à une fraction irréductible. Or, le plus petit commun multiple de tous les dénominateurs est d'un exposant en 2 strictement inférieur à a car tous les facteurs sont ainsi. La puissance de 2 au dénominateur est donc strictement inférieur à a (elle peut même être nul avec un numérateur pair).
On a donc 1/n+...+1/m+...+1/N=1/m+(1/n+..+1/(m-1)+1/(m+1)+...+1/N)=1/m+c/d=1/(2^ak)+c/(2^bh) avec k et h impairs et b<a la somme est égale à (h+2^a-bk)/(2^akh). Or, h+2^a-bk est la somme d'un impair et d'un pair (car a>b) donc il existe le facteur 2^a dans la fraction irréductible égale à cette somme donc ce n'est pas un entier.

[Médiat]

Il faut que je me fasse ré-aiguiser les neurones avant de tout comprendre...

Néanmoins j'ai remarqué une petite faute de frappe dans le dernier post :
la somme est égal à (h+2^a-bck)/(2^akh) et non (h+2^a-bk)/(2^akh), mais cela ne change rien au résultat.

Je suis embêté avec l'exemple :
(exemple si v=(4,1,3,2,5) w(1)=1, w(2)=1, w(3)=2, w(4)=2, w(5)=5).

que je ne comprends pas ... (honte sur moi )

[invite35452583]

Il faut que je me fasse ré-aiguiser les neurones avant de tout comprendre...

Néanmoins j'ai remarqué une petite faute de frappe dans le dernier post :
la somme est égal à (h+2^a-bck)/(2^akh) et non (h+2^a-bk)/(2^akh), mais cela ne change rien au résultat.

En effet une petite coquille (c'est loin d'être sûr que ce soit la seule, la preuve :

Je suis embêté avec l'exemple :
(exemple si v=(4,1,3,2,5) w(1)=1, w(2)=1, w(3)=2, w(4)=2, w(5)=5).

que je ne comprends pas ... (honte sur moi )

"w(n)" est devenu je ne sais pourquoi l'ordre du dernier sorti quand il y en a n nombres sortis càd X_n(w), vraiment la honte est pour moi, normal de ne pas comprendre ce passage.
Ainsi comme v=v=(4,1,3,2,5), on a X₁(w)=1, X₂(w)=1, X₃(w)=2, X₄(w)=2, X₅(5)=5

L'idée dans ce passage est qu'il y a une relation biunivoque entre
{ordres pour les n 1ers sortis, "ordres partiels"} <->{n-uplets (X₁(1),...,X_n(n))}
Cette relation n'est néanmoins pas l'identité.
Mais les X_n ont l'énorme avantage d'être indépendants.

Pendant que j'y suis : un résumé de la démo
Une tactique ne peut être basée que sur des décisions sur l'ordre "partiel" (dans le sens que ce n'est pas sur tous les éléments de E) au rang n des n premiers sortis. Une tactique peut donc être entièrement décrite par un certain nombre d'ordre "partiel" v pour lesquels on décide que dans cette situation on choisit le dernier. Le fait que le processus s'arrête à ce moment implique une exclusion de ces cas (il n'y a jamais deux arrêts ) qui permet de déterminer que la probabilité de succés d'une tactique donnée est la somme des P(v)P(gain/v).

La donnée de ces ordres "partiels" peut être avantageusement remplacée par la donnée des rangs du dernier des n 1ers sortis (les X_n) car ceux-ci sont indépendants.

a) Comme il est idiot de s'arrêter quand le dernier sorti n'est pas le plus grand de ceux déjà sortis (car ne peut être maximal si ce rang n'est pas le dernier et il est inutile de préciser que l'on s'arrête quand tous les nombres de E sont sortis pour le dernier rang), on peut se concentrer sur les tactiques ne s'arrêtant que lors que le dernier sorti et le plus grand des sortis à un rang donné.
b) Pour deux situations compatibles avec les arrêts de rang inférieur (il est possible que la situation v ou (X₁,..., X_n) se présente) on peut évaluer pour une tactique donnée quelle est la meilleure des deux et modifier la moins bonne en conséquence. Or cette évaluation ne dépend que du rang et non pas de l'ordre partiel (du moment que le dernier sorti soit bien le plus grand des sortis), on peut donc modifier une tactique donnée où la décision ne se prend que sur le seul critère du rang tout en ne baissant pas l'efficacité de celle-ci (on verra après que l'on peut toujours améliorer une tactique qui n'est pas construite sur ce seul critère).
Pour une tactique qui ne prend de décisions qu'en fonction du rang, on peut remarquer que si on peut déplacer un des rangs pour lesquels on décide de s'arrêter vers la droite (rang plus grand) alors on peut améliorer strictement la tactique (du moins si on ne se contente pas d'un seul rang, cas pour lequel c'est indifférent).
c) Ainsi après cette 1ère inspection on a montré qu'une des meilleures tactiques est du type on laisse passer les nombres sans broncher jusqu'à un certain rang puis dès que le dernier sorti est le plus grand des sortis on s'arrête.

Pour les tactiques du type précédent on obtient une formule calculée comme la somme des probabilités de succés pour chaque rang sélectionné, ce qui donne une formule agréable grace à un téléscopage. Et on se rend compte qu'en augmentant le nombre de rang on augmente d'abord l'efficacité strictement on arrive à un maximum dès que la somme de 1/(n-1) où n décrit l'ensemble des rangs sélectionnés est supérieur à 1 puis cela décroît strictement l'efficacité (avec le complément de mon dernier post).

Si on reprend l'unique passage où on avait pas augmenté strictement l'efficacité et en utilisant ce qui a été démontré au dernier point et au c) on montre qu'une tactique qui n'est pas bâtie sur le seul critère du rang peut être strcitement amélioré. Il y a donc unicité de la meilleure tactique (aux éléments "idiots" de plus haut rang près).

Maintenant un peu d'analyse pour évaluer quand la somme de 1/(n-1) où n décrit l'ensemble des rangs sélectionnés passe d'une valeur inférieure à 1 à une valeur supérieure à 1, permet d'encadrer n/N où N est le nombre d'éléments et n le 1er rang pour lequel on commence à pouvoir arrêter le "jeu".

[invite35452583]

Et pour finir avec ce problème, améliorons l'intervalle de n en fonction de N. (L'objectif est que cet intervalle détermine de manière unique n donc de largeur <=1 ou en tout cas guère plus grand que 1).
"Méthode de la tangente centrée", soit a un réel>1/2
On a pour toute fonction de classe C² f (f sera la fonction inverse) :
f(t)=f(a)+(t-a)f'(a)+(t-a)²/2 f"(u) avec u entre a et t.
On a donc
Avec f(t)=1/t f'(t)=-1/t² f"(t)=2/t³, on a

Avec

On a donc en sommant (n le nombre de rangs que'on laisse passer =n₀-1)
donc

Et on a :

Avec

Or on a déjà vu que N/e<n₀ donc (N-e/2)/e<n+1/2 et N-(n+1)<(e-1)/e.N
e(N)<(e-1)e²N/(N-e/2)³
On en déduit que

et

Maintenant un petit programme montre que ce chouïa n'est utile qu'à partir de N=97, on opeut donc utiliser N>=97 et on obtient sans trop forcer sur la majoration de la constante (le numérateur est majoré par le fait que la pente de la corde d'exponentielle est croissante) :
(N/e-1/2e)-1/2 -0,15/N<n
n est quasiment dans l'intervalle de largeur 1 et de centre N/e-1/2e.
Mon petit programme ne trouve d'ailleurs que N=97 qui sorte de cet intervalle (il reste dans l'intervalle avec le chouïa) pour 3<=N<=10.000.