Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Le chat et la souris

Bonjour,

Trouvé sur la toile cette énigme dont je n'ai pas la solution.
Je la dédie à mon compère freddy, allez donc savoir pourquoi...

Le chat et la souris

Un chat et une souris décident de jouer à pile ou face. Mais ils se disent que ce n'est pas très intéressant comme jeu donc ils compliquent un peu la règle.
Chacun choisit une combinaison de trois résultats (ex. Pile, pile, face). Ils lancent la pièce plusieurs fois, le premier qui voit sa combinaison apparaitre dans les trois derniers lancers gagne. Ils ne peuvent pas choisir la même combinaison.
Le chat, étant plus fort, décide de choisir sa combinaison en premier, et la souris, étant intelligente, le laisse faire.

Existe-t-il une stratégie pour maximiser l'espérance du gain d'un des deux joueurs ?

@+

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chat et la souris

Salut à tous,

▼une réflexion pour commencer

J'ai souvent pensé qu'au jeu de pile ou face, on pouvait bais... pardon ! ...rouler deux naÏfs.

Exemple : si je dis à Freddy et Yoshi : "on lance deux pièces : si on a deux face, Freddy gagne, si on a deux pile, Yoshi gagne, si on a un pile, un face, je gagne", comme ils me prennent pour une bille, ils ne se méfient pas et ils acceptent, alors que s'ils avaient réfléchi, ils auraient vu que j'avais deux fois plus de chances de gagner que chacun d'eux.

Le problème posé dans cette discussion me parait s' apparenter à celui-ci.

Si on individualise les trois lancers, on a 8 solutions. Si on ne considère que le résultat global, on n'en a que quatre.

Je reviendrai peut être si je ne suis pas devancé.

P.S. Il y en a qui vont tiquer : j'ai écrit "deux pile" et "deux face". Pas de S. Je persiste et signe, mais je dois admettre que j'ai un peu de mal à m'expliquer : dans ces expressions, il y a une sorte d'élision : la formulation complète serait "si les deux pièceS  tombent sur pile.

Il va sans dire que j'accueillerai avec intérêt et courtoisie tout contradicteur éventuel.

Dernière modification par nerosson (18-03-2013 15:23:52)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Le chat et la souris

Salut à tous,

▼ je continue à réfléchir

J'ai dit ci dessus que si on individualise les lancers, on avait huit solutions. C'est évident, mais je vais tout de même expliciter pour que Freddy arrive à suivre :

1) pile, pile, pile
2) pile, pile, face
3) pile, face, pile
4) pile, face, face

5) face, pile, pile
6) face, pile, face
7) face, face, pile
8) face, face, face.

Par contre, si on ne considère que le résultat global, on n'a que quatre résultats :

1) trois face
2) trois pile
3) deux face, un pile
4) un face, deux pile.

Si on confronte les deux manières, on constate que, avec la seconde manière,  les solutions 1 et 2 ont chacune une chance sur huit de se produire, alors que les solutions 3 et 4 ont chacune trois chances sur huit de se produire.

Donc :

-un joueur qui dispose du cas un ou du cas deux a trois fois moins de chances de gagner qu'un joueur qui se trouve dans le caca cas quatre ou dans le cas trois.

A+

Dernière modification par nerosson (18-03-2013 15:42:42)

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : Le chat et la souris

salut

▼intuition

je pense que la souris pourrait maximiser son gain en choisissant un triplet qui se termine par le premier doublet du triplet choisit par le chat, par ex. si le chat choisit pile pile face, la souris choisira soit pile pile pile soit face pile pile, ainsi à chaque fois que le chat pourrait gagner, la souris aura une chance sur deux de l'emporter avant lui!
après, mathématiquement parlant, je ne sais pas si tout ce baratin a du sens!!

A+

rjab

Invité

Re : Le chat et la souris

Salut,

▼Ma proposition

Si le chat dit PPP la souris doit dire FPP car au 3ème coup les chances sont égales, mais avec son F la souris a plus de chance pour la suite

Pareil, si le chat dit FFF la souris doit dire PFF

J'ai regarder aussi si le chat dit PFF la souris doit dire PPF

@+

Dernière modification par yoshi (18-03-2013 19:05:44)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Salut,

▼Texte caché

Si le chat dit PPP la souris doit dire FPP car au 3ème coup les chances sont égales, mais avec son F la souris a plus de chance pour la suite

Pareil, si le chat dit FFF la souris doit dire PFF

J'ai regarder aussi si le chat dit PFF la souris doit dire PPF

Salut,

il faut te lire de droite à gauche ou bien de gauche à droite ? ... :-)

Dernière modification par yoshi (18-03-2013 19:07:10)

rjab

Invité

Re : Le chat et la souris

re salut

excuse, le premier coup est à gauche puis les suivant sur la droite, comme la lecture normale

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Salut,

je pense avoir une piste, mais faut que la creuse plus avant, avant de l'exposer.

▼une idée ...

Il faut que les deux protagonistes jouent un triplet alterné, type PFP ou bien FPF.
La raison remonte aux résultats connus sur la modélisation de la marche aléatoire où l'on établit que si P=+1 et F=-1 à partir de l'origine, on sait qu'en moyenne, on tourne autour de l'origine.
Mais il faut que je développe un peu plus ...

(...)

rjab

Invité

Re : Le chat et la souris

salut

j'ai regardé tout ce qui est caché
le chat choisi sa combinaison et la souris la connait et choisi après lui. Elle est bien avantagée

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Salut,

c'est dans l'énoncé, non ?

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Re,

la souris, fixant après le chat sa règle, a une stratégie qui domine, en espérance, dans tous les cas celle du chat.

rjab

Invité

Re : Le chat et la souris

Salut,

J'ai eu un peu de temp, et j'ai trouvé pour cacher

▼solution

le chat est bête.
Il peut pas faire mieux que gagner
1 partie sur 8 si il dit PPP ou FFF
1 partie sur 4 si il dit PPF ou FFP
1 partie sur 3 si il dit PFP ou PFF ou FPP ou FPF

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Salut,

voilà ce que je trouve en utilisant un automate pour simuler. Par contre, je n'ai pas encore trouvé la preuve formelle.

▼stratégies gagnantes

on note +1 et -1 au lieu de pile et face, permettant de symétriser à l'envi.

si chat joue +1 +1 +1, alors la souris gagne avec +1 +1 -1 environ 8 fois sur 10 ;

si chat joue +1 -1 +1 , alors la souris gagne avec +1 -1  -1 enriron 7 fois sur 10 ;

si chat joue +1 -1 -1 alors la souris gagne avec -1 -1 +1 environ 7 fois sur 10 ;

si chat joue +1 +1 -1, alors la bonne stratégie pour la souris est +1 -1 + 1 qui donne un peu plus de chance à cette dernière (ce qui voudrait dire que ce doit être parfaitement équilibré en théorie ?!?)

Les autres stratégies que peut opposer la souris ne sont pas évoquées, car très largement perdantes pour elle.

A vérifier au plan formel.

Dernière modification par freddy (20-03-2013 13:54:35)

rjab

Invité

Re : Le chat et la souris

salut

je trouve pas comme freddy qui a une erreur la 3ème ligne
tu dis "si chat joue +1 -1 +1 , alors la souris gagne avec +1 -1 + 1 enriron 7 fois sur 10 ;"
la souris peut pas choisir comme le chat

avec+1 +1 -1, le dernier coup c'est +1 ou -1 ?
moi je prend 1 et 0 et avec 110, le 0 est le dernier coup :à un momentsi on a 011 on garde 11 et si 0 sort on obtient 110
si encore 0 sort on a 100...
explique ton automate

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Re,

j'ai fait un petite erreur d'écriture. J'ai corrigé ! Merci.

Cela étant, il faut se mettre d'accord sur la séquence : quand je dis +1 +1 -1, c'est dans l'ordre suivant : dernier tirage, avant dernier tirage, ante pénultième tirage.

En notant P=+1 et F = -1, on aurait dans l'ordre d'apparition FPP avec F en t-2, puis P en t-1 et P en t (instant du tirage).

Mon algo sous SAS est simple :

- tirage selon une loi uniforme sur [0,1]. Si le résultat est <= 0.5, alors la valeur = +1, sinon -1.

- Ensuite, à partir du troisème tirage, je regarde si la séquence correspond à une des deux stratégies choisies.

- Si non, je continue d'un pas et je regarde ; si oui, je stoppe la procédure et récupére le résultat en notant la stratégie qui est sortie.

- je répète ainsi 1 million de fois la procédure  (en réalité, 100 répétitions suffisent à se faire un très bonne idée) et je compte le nombre de résultat en faveur des deux stratégies proposées.

Je pense avoir trouvé une piste pour expliquer ces observations.

Dernière modification par freddy (20-03-2013 14:06:18)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Re,

la piste de ce matin.

▼paradoxe de Walter Penney

tout le sujet repose sur un paradoxe mis à jour en 1969 par l'auteur ci-dessus.

Le sujet était : Titi et Groucha jouent ensemble avec une pièce parfaitement équilibrée.

Titi propose à Groucha de le déclarer vainqueur si la séquence PPF sort avant la séquence FPP. Sinon, c'est Titi qui ramasse la mise.

Groucha est d'accord, car il estime à juste titre que chacune des deux séquences a la même probabilité d'apparaître, soit 1/8.

Toutefois, Groucha ne voit pas que s'agissant d'une chaîne discrète de Markov dans laquelle le temps joue un rôle prépondérant, le choix de Titi est tout sauf innocent.

En effet, après les deux premiers lancers apparaissent les quatre cas possibles suivant : PP, PF, FF et FP.

Et il est clair que si le premier cas est tout à fait favorable à Groucha (il ne peut que gagner), les trois autres sont exclusivement favorables à Titi.

Si on suppose que P sort au tirage n° 3, Titi gagne dans le cas FP ; dans les trois autres cas, il faut attendre le tirage n° 4 avec la suite : PP ; FP ; FP. Là, si P sort à nouveau, Titi gagne dans les deux autres cas, tandis que Groucha n'a qu'une seule chance de gagner, c'est que F sort au tirage n° 3 ou 4.

Le problème proposé par yoshi doit s'inspirer de ce paradoxe (le paradoxe est que Groucha a une chance sur quatre de gagner, quand Titi en a 3 sur quatre, avec le même temps d'attente).
Très, très joli sujet !

Dernière modification par freddy (20-03-2013 22:33:54)

rjab

Invité

Re : Le chat et la souris

Salut

Bravo pour le paradoxe
j'ai calculé les probabilités exacte en disant que la probabilité que le chat gagne se fait en ajoutant les probabilité que le chat gagne au 3ème lancement, puis au 4ème, puis au ...
j'ai fait les calculs jusqu'a 30 lancer

▼calcul

si la souris choisi bien, le chat peut pas faire mieux que gagner
1 partie sur 8 si il dit PPP ou FFF, la souris choisit FPP pour PPP   ou PFF pour FFF
1 partie sur 4 si il dit PPF ou FFP, la souris choisi encore FPP pour PPF ou PFF pour FFP
1 partie sur 3 si il dit PFP ou PFF (la souris choisis PPF) ou si il dit FPP ou FPF (la souris choisis FFP)
la souris ne choisi jamais PPP ou PFP ou FPF ou FFF

t'a écris "si chat joue +1 +1 -1, alors la bonne stratégie pour la souris est +1 -1 + 1 qui donne un peu plus de chance à cette dernière (ce qui voudrait dire que ce doit être parfaitement équilibré en théorie ?!?)"
je trouve qu'il y a jamais équilibre 50 50
es-tu d'accord ?

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Le chat et la souris

Salut,

▼J'ai triché

Comme Freddy le signale, c'est un "paradoxe" bien connu des mathématiques, semblable au jeu "feuille caillou ciseau" joué dans les cours d'école. Dans ce jeu, le ciseau coupe la feuille, le caillou enraye le ciseau et la feuille entoure le caillou. Aucun des 3 éléments n'est meilleur que les deux autres, et si vous en choisissez-un, votre adversaire peut en choisir un autre qui l'emportera à coup sûr.

La situation est très similaire ici, si ce n'est qu'il s'agit de probabilités et de calculs donc en moyenne, et que les calculs sont nettement plus compliqués... J-P Delahaye en a fait une explication très convaincante dans un article récent de Pour La Science. Par chance, cette article
est disponible sur page web.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Salut,

moi, j'aime bien quand Fred triche !...

rjab

Invité

Re : Le chat et la souris

Salut

j'avais fait un petit programe de calcul lundi soir,
merci freddy j'ai regardé walter penney, y a des pages en anglais mais j'ai vu que j'avai bon
merci fred j'ai vu l'article du J-P Delahaye. y a beaucoup de choses, je regarderai tout plus tard

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Salut,

pour compléter l'information, un des sujets de mathématiques du concours HEC de 2004 conduisait les prépas à approcher finement ce paradoxe.

Peut-être que Fred pourrait l'intégrer dans la base de sujets HEC (j'ai trouvé sur la toile deux versions, dont une assez intéressante car elle fait établir au préalable un résultat utile sur les séries entières).

Bb.

PS : l'article de JP Delahaye est de novembre 2011 - n° 409.

Dernière modification par freddy (22-03-2013 14:15:14)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Le chat et la souris

Re-

Tu peux me donner les références???

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Le chat et la souris

Re,

www.bankexam.fr/telecharger/annale?pdf=1634_HEC_2004...pdf

et www.youscribe.com › ... › Education › Annales d'examens et concours

c'est la seconde référence qui passe par un résultat sur les séries entières.

Dernière modification par freddy (21-03-2013 11:18:51)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Le chat et la souris

Merci.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Le chat et la souris

Re,

Moi aussi, j'ai fortement apprécié la "tricherie" de Fred...
J'ai lu avidement le contenu du lien qu'il donne... et il va falloir que je lise, relise encore !
C'est décoiffant...
En postant ce sujet que j'avais jugé pas évident, j'étais loin d'en mesurer toutes les implications !!!

@+