Partie 4 : Monte-Carlo

les petits papiers.

Le meneur de jeu prend "n" cartons identiques, au moins une dizaine, et inscrit sur chacun d'eux un nombre positif (ce peut être un nombre à virgule) ; la seule contrainte est que tous les nombres soient différents. L’inscription étant cachée, le joueur les mélange à sa façon, et les dispose ensuite en une file. On peut admettre que la distribution des nombres est aléatoire, dans la mesure où, même si on en connaît la moitié par exemple, on ne peut pas dire grand chose de l'autre moitié.

Le joueur a le droit de retourner autant de cartons qu'il le veut dans l'ordre de la file, l'un après l'autre ; il s’arrête quand il le désire. Il gagne si le dernier carton retourné porte le plus grand nombre du lot. Le jeu n'est pas équitable ; mais le droit de participation qui est demandé au joueur est très inférieur au lot obtenu quand il est gagnant. Le problème pour le joueur est donc d'optimiser sa stratégie, et de voir quel est le rapport minimum qui rend le jeu équitable.

Le logiciel TAPIS.EXE (sur le site du challenge) présente une version électronique de ce jeu, avec n=30 ; pour retourner un carton, cliquer « le suivant !!! », pour indiquer que l’on n’ira pas plus loin, « j’arrête ! ! ! » ; si on clique sur un carton, on retourne d’un seul coup ceux qui suivent. Ne cherchez pas s’il y a une astuce pour deviner les nombres : mis a part le fait que l’on ne dépasse pas cinq chiffres, toute autre particularité serait indépendante de notre volonté ! On notera que si on numérote les éléments de la file, le premier élément est en queue de file, et que la tête de file a pour numéro "n" : c’est cette convention, arbitraire, que l’on demande d’utiliser.

une stratégie.

La meilleure stratégie consiste à retourner de façon systématique un certain nombre k de cartons ; puis de continuer à retourner un à un les cartons et de s’arrêter sur le premier qui s’avère le plus grand des retournés. On peut montrer que c’est la meilleure stratégie ; mais ce n’est pas notre propos de l’établir ici (si le coeur vous en dit !). L’objectif est double : trouver le nombre k qui maximise le rapport du nombre de parties gagnantes au nombre de parties jouées, et trouver ce rapport maximum p (ce qui est une manière depuis Blaise Pascal de fixer le prix du billet pour que le jeu soit équitable, « qu’il soit d’espérance nulle »).

Il existe une solution mathématique ; nous en avons trouvé une assez élémentaire, qui n’utilise que des mathématiques de terminale… Si le cœur vous en dit ! (bis) Mais c’est hors challenge. L’intérêt de l’approche mathématique est de montrer que le rapport p et le rapport k/n sont quasi constants lorsque n varie.

Monte-Carlo.

Les rapports k/n et p ne varient donc pas beaucoup avec n. Aussi, nous vous proposons de faire une simulation informatique qui fournisse un ordre de grandeur réaliste de ces rapports en prenant n = 100, et en fixant l’ordre de grandeur du nombre de tests (par exemple 10000 ; une simulation ne prend que quelques microsecondes). Ce genre d’expérimentation pour simuler une situation marquée par des aléas, est souvent désignée comme sous le nom de méthode de Monte-Carlo ; on utilise ce type de procédé quand les méthodes purement probabilistes ne sont pas maîtrisables (ce qui n’est pas le cas ici).

ce qui est demandé.

Grâce aux moyens informatiques, effectuer la simulation précédente ; il s’agit d’afficher sous forme d’un tableau les valeurs de k et pk (probabilité de gagner si on fixe le seuil à k) obtenues par la simulation, ainsi que la plus grande valeur de pk. La figuration graphique est facultative. On demande alors d’évaluer p et de discuter un procédé pratique pour jouer sans trop avoir à calculer.