Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

Le plus grand ...



  1. #1
    Médiat

    Le plus grand ...


    ------

    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.

    -----
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  2. Publicité
  3. #2
    danyvio

    Re : Le plus grand ...

    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....
    Dernière modification par danyvio ; 03/11/2007 à 19h08.
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  4. #3
    danyvio

    Re : Le plus grand ...

    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 ?
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  5. #4
    homotopie

    Re : Le plus grand ...

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

  6. A voir en vidéo sur Futura
  7. #5
    Médiat

    Re : Le plus grand ...

    Citation Envoyé par homotopie Voir le message
    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 ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. #6
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par Médiat Voir le message
    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.

  9. Publicité
  10. #7
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par danyvio Voir le message

    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 ?
    Citation Envoyé par danyvio
    L'approche est-elle bonne ?
    pour un traitement complet, peut-être, mais tu devrais trouver une simplification.

  11. #8
    danyvio

    Re : Le plus grand ...

    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 ...)
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  12. #9
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par danyvio Voir le message
    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.

  13. #10
    danyvio

    Re : Le plus grand ...

    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...
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  14. #11
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par danyvio Voir le message
    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 ).

  15. #12
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par Médiat Voir le message
    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

  16. Publicité
  17. #13
    danyvio

    Re : Le plus grand ...

    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 ?
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  18. #14
    Médiat

    Re : Le plus grand ...

    Citation Envoyé par danyvio Voir le message
    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #15
    homotopie

    Re : Le plus grand ...

    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.

  20. #16
    Médiat

    Re : Le plus grand ...

    Citation Envoyé par homotopie Voir le message
    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à .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #17
    danyvio

    Re : Le plus grand ...

    Citation Envoyé par homotopie Voir le message
    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.
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  22. #18
    Sylvestre

    Re : Le plus grand ...

    Bonjour,

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

  23. Publicité
  24. #19
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par Sylvestre Voir le message
    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.

  25. #20
    homotopie

    Re : Le plus grand ...

    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 SN(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(fn(w,1))>w(fn(w,2))>...>w(fn(w,i))>...>w(fn(w,n)). fn(w,-) est une bijection de {1,…,n} pour tout w et tout n.
    On pose Rn(w)=( fn-1(w,1),…, fn-1(w,i),…, fn-1(w,n)). (A i, on attribue la place de w(i) dans le classement précédent).
    En particulier, on note Xn(w)= fn-1(w,n).

    Une tactique ne peut être définie qu'à partir des images des séquences w par les différentes applications Rn 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 vi de {1,...,ni}, celles pour lesquelles on choisit le dernier nombre sorti.
    On note V l'ensemble des vi, ni est appelé la longueur de vi.
    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/vi) est la probabilité que le nième nombre soit le plus grand sachant que Rni(w)=vi.

    2) la famille des Xn

    a) “lemme fondamental“ : les Xn sont indépendants
    Pour cela il suffit de montrer que pour tout N-uplet (m1,…, mi,…, mN) de {1}x{1,2}x…x{1,2,…,i}x…x{1,…,N } l’intersection des (Xn= mn) est de cardinal égal à 1.
    w(N) est le mNè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 mn è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 Mn de {1,…,n} n allant de 1 à N, les séquences vérifiant Xn est dans Mn pour tout n de 1 à N sont en cardinal égal à card(M1)xcard(M2)x…xcard(Mn)x…xcard(MN) soit une probabilité égale à cette dernière égalité étant obtenue en reprenant ce qui précède en prenant Mm={1,…,m} pour tous les m distincts de n. On peut remarquer ici que les Xn suivent une loi d’équiprobabilité.

    b) une tactique peut être entièrement décrite par les Xn
    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 wm 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 (m1,…, mn) de {1}x…x{1,…,n} il existe une unique séquence de {1,..,n} pour laquelle, avec un abus de notation, Xk= mk pour tout k.
    .
    Désormais une tactique sera la donnée des (m1,…, mn).

    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 mn=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={ (m1,…, mn) ; n soit dans L et mn=1 et de plus pour tout p dans L<n, mp 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>= n0}
    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=(m1,…, mn) avec mn distinct de 1. On considère la tactique intiale modifié en supprimant ce M.
    L’efficacité est inchangée car P(gain/ (mn distinct de 1))=0.
    De plus, si n<N, on peut ajouter à V (m1,…, mn,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 (m1,…, mN) avec mN 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={ (m1,…, mp)
    tels que p soit dans L et mp=1 et de plus pour tout q dans L<p, mq 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 (m1,…, mn) avec n dans L et mn=1 et de plus pour tout p dans L<n, mp 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’1,…, (m’1,…, 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 Xn à
    .

    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 Xn 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= mp 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 Xn.

    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={n1,…, nm}, écrit dans l’ordre croissant est égale, vue la loi d’équiprobabilité des Xn 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 nk=

    Si pour un certain k compris entre 1 et m, nk+1 n’est pas dans L, on considère L’=L auquel on retire {nk} et auquel on ajoute {nk+1}. Les probabilités de gagner à un rang ni 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 nk= nm avec m>1, on le glisse vers la droite, ça ne modifie rien puis on glisse nm-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>= n0} pour un certain n0.

    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(n0) l’efficacité pour L={n>=n0} :
    Que l’on obtient en triturant la formule
    ou en remarquant que la probabilité pour les rangs >=n0 est multipliée par (n0-2)/(n0-1) et celle en n0-1 vaut 1/N.
    D’où
    Tant que 1/(n0-1)+...+1/(N-1) <1 Eff(n0-1)>Eff(n0)
    Dès que 1/(n0-1)+…+1/(N-1) >1 Eff(n0-1)<Eff(n0)
    La tactique la plus efficace est celle pour laquelle n0 est le plus petit pour lequel 1/(n0-1)+…+1/(N-1)>=1 et au cas où cette somme vaut exactement 1 également pour ce même n0-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 n0=2 et n0=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=(m1,...,mi,..,mn) et M'=(m'1,...,m'i,...,m'n) un dans la tactique l'autre pour lequel aucune troncature ((m'1,...,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<n0 (n0-1)/N (1/(n0-1)+ ...+ 1/(N-1))>= (n0-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>=n0 ((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>=n0 la tactique de prendre le dernier sorti est strictement plus efficace que toute autre tactique "locale".

  26. #21
    homotopie

    Re : Le plus grand ...

    Conclusion :
    si pour n0, on a 1/(0-1)+...+1/(N-1)>1 alors il y a unicité pour la meilleure tactique "non idiote"
    si pour n0, on a 1/(0-1)+...+1/(N-1)=1 alors toute tactique du type :
    on prend le dernier sorti si le rang est >=n0
    on ne le prend pas si n<n0-1
    en n0-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 < n0 < 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 n0/N tend vers 1/e et l'efficacité de la meilleure tactique tend vers (1/e) x1=1 car n0/N tend vers 1/e et la somme 1/(n0-1)+...+1/N-1 n'est pas plus éloignée de 1/(n0-1) de 1.
    Faire attention ici n0 est le rang à partir duquel on s'arrête dès que l'on a un plus gros.
    Attention 44 pour N=120, est n0-1 la quantité de nombres de e qu'on laisse passer dans tous les cas. (n0=45 pour N=120).
    Dernière modification par homotopie ; 08/11/2007 à 15h38.

  27. #22
    danyvio

    Re : Le plus grand ...

    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...
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  28. #23
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par danyvio Voir le message
    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=2ap et m'=2ap' 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<2ak<m'<=N mais l'exposant de 2 dans 2ak est strictement supérieur à a car k est pair, contradiction. Le nombre m=2ap 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/(2ak)+c/(2bh) avec k et h impairs et b<a la somme est égale à (h+2a-bk)/(2akh). Or, h+2a-bk est la somme d'un impair et d'un pair (car a>b) donc il existe le facteur 2a dans la fraction irréductible égale à cette somme donc ce n'est pas un entier.

  29. #24
    Médiat

    Re : Le plus grand ...

    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+2a-bck)/(2akh) et non (h+2a-bk)/(2akh), 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 )
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  30. Publicité
  31. #25
    homotopie

    Re : Le plus grand ...

    Citation Envoyé par Médiat Voir le message
    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+2a-bck)/(2akh) et non (h+2a-bk)/(2akh), 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 Xn(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 X1(w)=1, X2(w)=1, X3(w)=2, X4(w)=2, X5(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 (X1(1),...,Xn(n))}
    Cette relation n'est néanmoins pas l'identité.
    Mais les Xn 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 Xn) 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 (X1,..., Xn) 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".

  32. #26
    homotopie

    Re : Le plus grand ...

    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 C2 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/t3, on a

    Avec

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

    Et on a :

    Avec

    Or on a déjà vu que N/e<n0 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)3
    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.

Discussions similaires

  1. grand bouchon!
    Par rubi dans le forum Santé et médecine générale
    Réponses: 9
    Dernier message: 24/11/2007, 10h35
  2. Grand vide, grand froid.
    Par erectous dans le forum Archives
    Réponses: 12
    Dernier message: 02/11/2007, 19h42
  3. Louis Le Grand
    Par Rem75 dans le forum Orientation avant le BAC
    Réponses: 1
    Dernier message: 02/06/2006, 22h09
  4. un grand merci
    Par anzelyk dans le forum TPE / TIPE et autres travaux
    Réponses: 3
    Dernier message: 24/01/2006, 15h35
  5. Demi-grand
    Par Cétone dans le forum Chimie
    Réponses: 13
    Dernier message: 28/09/2004, 20h42