Discussion :

[pseudocode]

Quelle chance ! Le roi vous donne l'une de ses 100 filles en mariage.
Mais plus que la beauté légendaire des 100 filles, vous etes surtout interessé par leur dot !

Chaque fille a une dot differente... mais malheureusement inconnue.

Le roi vous proprose alors de vous présenter, une par une, ses 100 filles.
A chaque fois, le roi vous annoncera la dot pour la fille en question.

Vous aurez alors le choix entre la prendre pour épouse sur le champ, ou la laisser partir définitivement.

Comment maximiser vos chances d'avoir la plus grande dot ?

[zodd]

Je tue le roi, prend possession de son royaume.. Je mes les moches a la cuisine et au ménage.. Et je me fais un harem avec les plus jolies !!!
CQFD

[pseudocode]

Je tue le roi, prend possession de son royaume.. Je mes les moches a la cuisine et au ménage.. Et je me fais un harem avec les plus jolies !!!
CQFD

Si on etait dans un jeu de rôle, et si j'etais le MJ, je t'enverrai croupir dans les oubliettes du chateau...

[zodd]

Tu es jaloux.. c'est tout..

[Biosox]

Elles ont toutes des dot différentes.
Mais est-ce qu'on en sait pas plus?
est-ce qu'on ne connait pas un ecart maximum entre 2 dots, ou un maximum absolu ou quoi que ce soit?

[pseudocode]

Elles ont toutes des dot différentes.
Mais est-ce qu'on en sait pas plus?
est-ce qu'on ne connait pas un ecart maximum entre 2 dots, ou un maximum absolu ou quoi que ce soit?

Et bien, non. On ne sait rien d'autre...

De serieuses connaissances en proba sont necessaires. Ce probleme fait partie des plus compliqués que j'ai dans ma besace .

Spécial dedicace pour prgasp77:

J'aime bien tes enigmes, continue s'il te plaît, mais pimente un peu ^^

[prgasp77]

Je connais alors je laisse chercher, un indice : il est possible de maximiser ses gains, mais pas de connaitre avec certitude les filles qui ont la plus grande dote.

[sdx]

Les dotes sont des nombres entiers ou des réels ?

[pseudocode]

Les dots sont des nombres entiers ou des réels ?

Comme ca t'arrange...

[DarkMolo]

Moi je ne tuerais pas le roi, mais je lui demanderais d'appliquer un tri croissant au vector de filles sur la base de leurs dotes avant de me les présenter, pourquoi croissant et pas décroissant?? Peut-être que plus la dot est élevée moins la fille est belle(je risque pas de me tromper sur ce point rien qu'avec les 3 premières), alors à un moment vaut mieux s'arrêter même si je sais que la dernière des filles a la dot la plus élevée.

Sinon sérieusement, t'es sûr pseudocode que t'as pas dissimulé aucun indice, parce sinon je vois pas comment faire, même en parcourant les 99 premières filles, il est probable que ce soit la dernière qui aie la dot la plus élevée...

[Aitone]

Ne doit-il pas commencer par faire une moyenne à chaque nouvelle fille qu'il voit ?

[charly]

Je laisserais passé 20 demoiselles pour connaitre le max et le min des dotes , et je prenderais la première qui sera le plus proche du max que j'avais trouvé précédement c'est a dire que on prends l'écart entre le min et le max qu'on divise par 20 et la premiere qui est superieur au max-(max-min)/2

[pseudocode]

Sinon sérieusement, t'es sûr pseudocode que t'as pas dissimulé aucun indice, parce sinon je vois pas comment faire, même en parcourant les 99 premières filles, il est probable que ce soit la dernière qui aie la dot la plus élevée...

Non ! il n'est pas "probable" que ce soit la derniere qui aie la plus grande dot.
C'est juste "possible"...

- La "probabilité" que ce soit la derniere qui aie la plus grande dot c'est 1 chance sur 100.
- La "probabilité" que ce soit la premiere qui aie la plus grande dot c'est 1 chance sur 100.
- La "probabilité" que ce soit la n-ieme qui aie la plus grande dot c'est 1 chance sur 100.

Et c'est la tout le probleme....

@charly: La methode est pas mal... encore un peu de recherche....

[gorgonite]

un indice, on obtient une solution optimale avec un estimateur de quel rang ?

[méphistopheles]

Je la connais (enfin, je connait plutot sa version histoqire avec un nombre quelquonque d'argent (de dots), de lots d'argent(de filles) et surtous d'essais (de rois).)

charly n'a pas exactement la solution, mais n'en est pas tres tres loin.

[pseudocode]

Bon je vous donne la méthode, a vous de trouver les valeurs:

<Methode>
Il faut laisser passer les N premieres filles, puis choisir la premiere fille qui aura une dot superieure au N premieres.
Reste a trouver N pour maximiser ses chances....
</Methode>

@méphistopheles: Il y a beaucoup de variantes, avec des boules, des cartes, des nombres, ... Mais l'argent, ca reste une valeur sure.

[BertrandA]

Je demande au roi de ne me présenter que 2 filles (j'ai pas que ça à fiche non plus).

A la première je dis :
"Je suis joli garçon, sportif et je fais la cuisine" (ce qui n'est pas un postulat, c'est parfaitement exact, je tiens à le préciser).

Cette phrase n'ayant néanmoins aucun intérêt pour la résolution du problème, je poursuis :
"Dis-moi laquelle de tes soeurs a la plus grosse dot et nous partagerons tous les 2, je suis nul en mathématiques, mais j'ai un très bon conseiller financier !"

Comme elle est jalouse de sa frangine, elle n'hésite pas à me dire son nom.
Il ne me reste plus qu'à demander au roi de me présenter la fille en question... et à choisir celle qui a les plus gros seins !
Voilà...

[méphistopheles]

@méphistopheles: Il y a beaucoup de variantes, avec des boules, des cartes, des nombres, ... Mais l'argent, ca reste une valeur sure.

disons que je pensait à une hitoire réelle de persones qui, sur un bateau qui remontais le misisipi (je crois) proposaient aux voyageurs d'incrire autemp de nombre qu'il voulaient sur un bout de papier. puis, ils proposaient le pari suivant: si il trouvaient le plus grand nombre, il prenaient cinq fois la mise, sinon, les voyageurs voyaient leur mise doublée (ce qui ne paraissait pas habérant vu qu'on pouvais jouer un grand nombre de numéraux, mêmes décimeaux). néamoins, il gagnaient presque toujours et suite à une plainte, le gouverneent envoya des enqueteur, puis un mathématicien qui pu résoudre le problème.

Sinon, si M est le nombre de chiffres en jeu, N=M/cste que je ne donnerais pas pour laisser les gens chercher.

[sdx]

Soit N le nombre d'entiers naturels
Soit d_n la dot de la nième fille

Si tous les entiers naturels sont equiprobables, alors la probabilité d'avoir d_(n+1) dans [|0; d(n)|[ est de : d(n)/N, et d(n)/N = 0 puisque N est un infini.
Donc d_(n+1) >= d(n)
Donc les dots vont croissante.
Donc la dernière fille a la plus grande dot, c'est tout.

[ganga]

Je suis pas d'accord avec ta methode pseudocode :

Imagine que dans tes N premieres quelques soit N tu ai la plus grande dot, ben tu risques de galerer dans les 100-N suivantes pour trouver une dot plus grande...