Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 10-10-2007 23:13:29

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Défi : trouver le plus grand nombre!

Bonsoir,

  Voici un petit défi mathématique pour agrémenter vos réflexions.
On vous donne un tas de n feuilles, avec sur chaque feuille un nombre aléatoire écrit dessus.
Les feuilles vous sont présentées avec le nombre caché, et vous retournez les feuilles une à une.
On retourne les feuilles une à une. Vous décidez quqnd vous voulez d'arrêter. Le but du jeu est de s'arrêter lorsque le nombre écrit sur la feuille est le plus grand possible.

  Quelle est la meilleure stratégie pour gagner?????
A vous de faire mieux que moi! Mais chose qui peut sembler étonnante à première vue, si n est grand,
j'ai au moins 36,7% de chances de m'arrêter au plus grand nombre....

A vous lire...
Fred.

Hors ligne

#2 11-10-2007 19:41:08

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : Défi : trouver le plus grand nombre!

Salut Fred,

Joli casse-tête....
Sait-on combien il y a de feuilles, donc combien de nombres ont été inscrits ?
Si ces nombres sont aléatoires, il peut donc y avoir plusieurs fois le même ?
Tu as écrit :

lorsque le nombre écrit sur la feuille est le plus grand possible.

Tu veux bien dire : lorsqu'on est sûr d'avoir sous les yeux le plus grand nombre de la liste ?

A priori comme ça, je n'ai pas la moindre idée d'une (même pas LA) stratégie à employer...
Invraisemblable ! Mais bon, demain sera un autre jour...

;-(

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 11-10-2007 20:49:36

pin-pon
Membre
Inscription : 23-09-2007
Messages : 16

Re : Défi : trouver le plus grand nombre!

Bonjour !

Je partage la même "dubitativation" que Yoshi.

Mon gros problème pour établir une stratégie est : "sur chaque feuille un nombre aléatoire écrit dessus..."

Ca veut dire quoi ? C'est quoi le "aléatoire" en question ?
De la loi exponentielle ? De l'uniforme (sur quel intervalle ?) ? Les nombres de 1 à n mélangés sur les feuilles ?

Drôle d'énigme...

Dernière modification par pin-pon (11-10-2007 20:50:26)

Hors ligne

#4 11-10-2007 22:14:21

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Défi : trouver le plus grand nombre!

Hello tous,
... le genre de Pb qu'on ne sait pas par quel bout prendre !
Mais quand il y a n qui intervient, on peut tjs faire n=2 (comme disait un de mes anciens profs). Alors voilà ce que ça donne :
Il y a 2 feuilles portant chacune un nombre différent.
Il y a 2 stratégies possibles :
   A : On tire une seule feuille ;
   B : On tire 2 feuilles.
La proba. de gagner avec A est p(A) = 1/2
La probab. de gagner avec B est p(B) = 1/2.
Facile !
Alors on passe à n = 3 et ainsi de suite jusqu'à ce que la lumière jaillisse.
A+

Hors ligne

#5 11-10-2007 23:03:00

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Défi : trouver le plus grand nombre!

Bonsoir,

  J'apporte donc quelques éclaircissements :
*on peut supposer que tous les nombres inscrits sont distincts. Peu importe comment ils sont choisis aléatoirement, le problème n'est pas là.
*on gagne si on s'arrête à la feuille qui porte le plus grand nombre. Bien sûr, si on joue vraiment à ce jeu, on retourne ensuite la fin du tas pour savoir si vraiment on avait gagné.

Bonne recherche...
Fred.

Hors ligne

#6 12-10-2007 09:45:10

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : Défi : trouver le plus grand nombre!

Bonjour,

Fred a écrit :

Le but du jeu est de s'arrêter lorsque le nombre écrit sur la feuille est le plus grand possible.

Peut-être que j'aperçois une lueur au fond du tunnel...
Moi, j'avais compris ; lorsqu'on a la certitude absolue d'avoir le plus grand nombre sous les yeux...
John, ce puits de science, arrive avec ses probas.. Si j'ajoute à cela que j'avais occulté le pourcentage final du 1er post, cela tendrait-il à vouloir dire que je dois me poser la question ainsi :

Quelle stratégie adopter pour avoir la probabilité maximum de s'arrêter à la feuille qui porte le plus grand nombre ?

Là, je comprendrais déjà mieux la problématique...

Cela dit, je me trompe peut-être, mais la probabilité cherchée ne doit pourtant pas être la même, que les n nombres différents soient ceux de 1 à n ou pris entre 1 et 2n, 1 et n² par exemple... Non ?

En tout cas, belle colle, sauf pour John (comme d'hab !)

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#7 12-10-2007 13:20:16

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Défi : trouver le plus grand nombre!

Salut à tous,
Bien yoshi ! c'est effectivement la bonne question :
"Quelle stratégie adopter pour avoir la probabilité maximum de s'arrêter à la feuille qui porte le plus grand nombre ?"
Pour répondre à ta dernière question : peu importe les nombres, l'important c'est qu'ils forment un ensemble ordonné dont on ne connait que le cardinal.
Pour la stratégie optimale, il faut s'arrêter lorsque le dernier nombre tiré est plus grand que tous ceux déjà tirés (Lapalisse). Le problème c'est que ça peut se produire dès le second tirage.
A+

Hors ligne

#8 14-10-2007 09:54:34

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Défi : trouver le plus grand nombre!

Bon dimanche à tous,
... et sur ce défi, ça roupille ou ça dort ?

n = 3
a < b < c (trois nombres)

Stratégie 1 (1 seul tirage)
-------------
a
b
c => gagné
p(S1) = 1/3

Stratégie 2 (2 tirages en aveugle)
-------------
a b
a c => g
b c => g
b a
c a
c b
p(S2) = 1/3

Stratégie 2/3 (2 tirages + 1 si le dernier tiré est inférieur aux nombres déjà obtenus)
---------------
a b
a c => g
b c => g
b a c => g
c a b
c b a
p(S2/3) = 1/2

Stratégie 3 (3 tirages en aveugle)
-----------
a b c => g
a c b
b c a
b a c => g
c a b
c b a
p(S3) = 1/3

Bon, c'était juste pour relancer le débat avant que Fred ne s'impatiente.
A+

Hors ligne

#9 16-10-2007 09:14:45

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Défi : trouver le plus grand nombre!

Salut,

Alors yoshi... aurais-tu jeté l'éponge ?
Si non, jette un oeil ici :
http://www.bibmath.net/dico/index.php3? … ropie.html
A+

Hors ligne

#10 22-10-2007 07:24:20

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Défi : trouver le plus grand nombre!

Salut,

  Bon, cela fait 11 jours que le défi traine, et vu le peu d'intérêt qu'il suscite,
je crois que l'on peut le clore. Je laisse John présenter sa solution...

F.

Hors ligne

#11 22-10-2007 10:38:04

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Défi : trouver le plus grand nombre!

Hello Fred,
je savais bien que tu t'impatienterais... et tu savais que j'allais te demander encore un peu de temps.
J'ai des idées bien précises sur ce problème mais je n'ai pas encore formalisé la solution. Elle repose sur des calculs de proba des événements qui peuvent se produire au cours du tirage. C'est assez basique...
Il y a peut-être une autre approche à explorer par la théorie de l'information et l'entropie.
Mais si je suis à côté de la plaque, tu peux livrer la solution car j'ai peu de temps en ce moment. En tout cas, c'est un défi très intéressant.
A+

Hors ligne

#12 22-10-2007 11:43:39

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Défi : trouver le plus grand nombre!

Salut,

  Je te laisse le temps qu'il te faut.
Je n'ai pas de meilleure réponse que par des calculs de proba élémentaires ...

Fred.

Hors ligne

#13 06-11-2007 11:29:35

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Défi : trouver le plus grand nombre!

Salut à tous,
J'ai évalué une stratégie consistant à arrêter le jeu dès que le dernier nombre tiré est supérieur à tous les nombres  déjà tirés. La proba. de gagner est assez élevée lorsque n est petit. En revanche, plus n augmente, plus les chances de gagner s'amenuisent.
En effet, la proba. de gagner avec cette stratégie s'écrit :
Pr{Obtenir le plus grand nombre au dernier tirage} = [1 + 1/2 + 1/3 + ... + 1/(n-1)]/n
Sauf erreur, cette série converge vers 0.
Je laisse donc à Fred le soin de nous présenter une stratégie bien meilleure.
A+

Hors ligne

#14 06-11-2007 22:04:23

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Défi : trouver le plus grand nombre!

Bon, je me lance donc en espérant me souvenir de mon argument d'il y a presque un mois.

La stratégie que je propose est la suivante :
on retourne d'abord une proportion p des feuilles sans réfléchir.
Lorsque toutes ces feuilles sont retournées, on continue
en s'arrêtant dès qu'on a trouvé un nombre plus grand que ceux déjà vus.

Déterminons la proportion p pour obtenir une probabilité optimale de gagner
et calculons cette probabilité.

On gagne si (et seulement si) :
* la feuille portant le nombre le plus grand se trouve dans le paquet de feuilles non retournées,
et la feuille portant le second plus grand nombre se trouve dans le paquet de feuilles retournées.
La probabilité de ce cas est (1-p)*p.
*la feuille portant le nombre le plus grand se trouve dans le paquet de feuilles non retournées,
la feuille portant le second nombre le plus grand se trouve dans le paquet de feuilles non retournées
et est après la première,
la feuille portant le troisième nombre le plus grand est dans le paquet de feuilles retournées.
La probabilité de ce cas est [tex]\frac{p(1-p)^2}{2}[/tex].
*les feuilles portant le premier, le second et le 3ème plus grand nombre sont dans le paquet de feuilles non retournées, celle portant le premier étant devant les autres, et la feuille portant 4ème nombre est
dans le paquet de feuilles retournées. La probabilité de ce cas est
[tex]\frac{p(1-p)^3}{3}[/tex]
*et ainsi de suite.

La probabilité que l'on gagne est donc, quand n devient grand, équivalente à  :
[tex]\sum_{k=1}^{+\infty}p\frac{(1-p)^k}{k}[/tex]
On reconnait alors le développement de ln(1+x) et on obtient que la probabilité vaut
[tex]{-}pln(p).[/tex]

On optimise cette quantité pour p dans [0,1]. Le maximum est atteint en p=1/e,
et vaut 0,3678.

Qui dit mieux???

Je vous donne rdv pour un nouveau défi bcp plus simple dans un nouveau message!

Fred.

Hors ligne

Pied de page des forums