Defi proba 4

par **BancH** » 23 Juin 2007, 02:02

Ma solution : XYX.

par **BancH** » 23 Juin 2007, 02:18

Si le chat prend XXX, la souris prendra YXX, et au premier Y sorti, le chat aura perdu.

S'il prend XXY, la souris prendra XXX, et si le chat ne gagne pas du premier coup il se fera manger.

S'il choisi XYY, la souris prendra XXY, or dans l'absolu XXY est meilleur que XYY puisqu'il permet d'avoir constamment 50% de chance de gagner à chaque lancer après que XX soit sorti.

Finalement s'il prend XYX, la souris choisira YXY ou YYX (les deux sont équiprobables je crois), or XYX=YXY.

Le dernier cas est le seul où le chat n'a pas plus de chance d'être mangé que la souris.

EDIT : en fait non, j'ai tout faux -_-

par **alben** » 23 Juin 2007, 13:18

Flodelarab a écrit:Il faut que le code du second joueur finisse par les 2 du début du premier.

Et je maintiens que si le chat prend FPP, il faut que la souris prenne PFP

Bonjour,
En toute cohérence, il faudrait que la souris prenne PFP ou FFP
Tu es bien parti Flodelarab, il reste à départager ces deux choix possibles

@BancH : tu n'as pas trouvé de collégien à 2h du mat ! ça devrait aller mieux aujourd'hui

par **Flodelarab** » 23 Juin 2007, 13:32

alben a écrit:Bonjour,
En toute cohérence, il faudrait que la souris prenne PFP ou FFP
Tu es bien parti Flodelarab, il reste à départager ces deux choix possibles

Bien sur qu'il y a 2 cas par rapport a mon hypothèse de base.
Je n'ai pas argumenté le P car je trouve ma justification bancale pour cette première lettre.
Tant qu'un F n'apparait pas, il ne peut pas commencer sa séquence. Or, moi, si je prends l'inverse de sa première lettre, je commencerais ... et comme il ne peut pas commencer grace a mes 2 dernières lettres, je trouve ça plutot positif pour moi (enfin la souris, le second joueur).

par **Imod** » 23 Juin 2007, 13:39

Je regarderais demain ( je suis en dessous de zéro quand mon esprit est ailleurs ) mais le problème me plait .

Imod

par **Imod** » 24 Juin 2007, 12:58

J'ai commencé à regarder tous les "mots" contenant une et une seule fois chaque suite de trois jets du genre "PFFFPFPPPF" pour voir si on pouvait en tirer quelque chose mais pour le moment je suis à sec .

Imod

par **alben** » 24 Juin 2007, 23:01

Bonsoir,
Après une petite fièvre du vendredi soir, c'est le calme plat. Besoin d'indices supplémentaires ? (il y en a pas mal dans le post 25)

par **Imod** » 25 Juin 2007, 01:12

Ah non Alben ,

je n'ai pas trop eu le temps de regarder mais c'est prévu ( j'ai commencé le cas par cas mais il y avait vraiment trop de bruit à la maison ) .

Imod

par **alben** » 25 Juin 2007, 11:52

Imod a écrit:Ah non Alben ,
je n'ai pas trop eu le temps de regarder mais c'est prévu ( j'ai commencé le cas par cas mais il y avait vraiment trop de bruit à la maison ) .
Imod

Tu sembles le seul à continuer. Pourtant, si le chat a fait une prépa, la souris n'a pas dépassé le collège (elle n'a jamais entendu parler d'un fromage appelé markov) et elle sort très bien... pendant que le chat remplit des pages de tribus de borelliens...
On peut s'en sortir avec juste un peu de réflexion

par **Imod** » 25 Juin 2007, 12:10

Bonjour Alben .

J'ai regardé tous les cas , il est clair que si la souris joue au mieux , le chat perd tout le temps et qu'il perd plus sûrement s'il choisit PPP ou FFF et de façons équivalentes pour les autres choix . La souris , elle , utilise les réponses suivantes :

PPP -> FPP
FFF -> PFF
PFP -> PPF
FPF -> FFP
FFP -> PFP
PPF -> FPF
PFF -> PPF ou FPF
FPP -> FFP ou PFP

Par contre je n'ai pas eu le courage de calculer la probabilité de gain de chacun . S'il y a plus simple , je ne vois pas :doh:

Imod

par **alben** » 25 Juin 2007, 13:51

Oui Imod, c'est bien la stratégie de la souris qui lui garantit une espérance de gain positive ou nulle.
Tu as utilisé le fait que le second a intérêt à terminer sa séquence par les deux premiers choix du premier. A PFP, il faut donc répondre XPF ce qui donne deux possibilités PPF ou FPF. Mais le second est à éliminer car la séquence du premier se termine aussi par les deux premiers du second, et cette symétrie conduit à une espérance de gain nulle.
On peut facilement montrer que cette stratégie est avantageuse pour le second joueur :
Si une des séquences sort dès le début (3 lancers), les choix sont indifférents.
Si ce n'est pas le cas, il suffit de supposer que les lancers ont été pratiqués et notés par un arbitre avant les choix des triplets. A chaque fois que le couple commun apparaît il sera encadré par deux valeurs que l'on suppose inconnues :
Dans l'exemple ci dessus ....XPFY -> 4 possibilités

X # choix du second et Y # choix du premier --> le jeu continue
X = choix du second et Y # choix du premier --> X gagne
X # choix du second et Y = choix du premier --> Y gagne
X = choix du second et Y = choix du premier --> X gagne avant

L'avantage pour le second joueur est clair, toutefois l'équilibre n'est pas impossible (cas de la situation symétrique mais ce n'est pas le seul).

Mais il existe deux cas où cette simple règle ne permet pas de trancher et ce n'est pas neutre : un des deux choix ne confère aucun avantage au second, il assure simplement l'équilibre.
Ce qui nous donne d'ailleurs la stratégie du chat (qui sait que la souris n'a pas dépassé le niveau collège) : il choisit PFF ou FPP :we:
Sinon, il faut rentrer dans Markov pour trancher le cas douteux et, avec une petite astuce, c'est très simple. Lorsqu'on a évalué les probas dans un cas, on trouve très vite la méthode pour déterminer toutes les config (pas si nombreuses avec les symétries)

par **Imod** » 25 Juin 2007, 14:13

alben a écrit:Ce qui nous donne d'ailleurs la stratégie du chat (qui sait que la souris n'a pas dépassé le niveau collège) : il choisit PFF ou FPP :we:

N'est-ce pas plutôt PPF ou FFP ?

Imod

par **alben** » 25 Juin 2007, 14:54

Imod a écrit:N'est-ce pas plutôt PPF ou FFP ?

Imod

Ben non, je me suis appuyé sur ta réponse ce sont les deux cas où le second joueur n'a pas de critère pour choisir entre deux possibilité (l'une neutre, l'autre favorable au second)
D'ailleurs contrairement à ce que tu as écrit, pour le premier joueur, une fois éliminé FFF et PPP, les 6 autres choix ne sont pas également défavorables. PPF et FFP le sont plus que les 4 autres

par **Imod** » 25 Juin 2007, 18:32

D'accord alben , d'ailleurs dans le cas où le chat choisit PFF il me semble que la souris a intérêt à choisir PPF plutôt que FPF . J'essaierai de pousser les calculs un peu plus loin ce soir .

Imod

PS : décidément , pas le moyen de se concentrer en ce moment , mais je compte bien y retourner dès les vacances ( heureusement bientôt ! ) .

par **Flodelarab** » 26 Juin 2007, 01:21

Ou alors, la souris fait la bonne vieille feinte de la pièce dont les 2 cotés ont le dessin d'une face.
Dans ce cas il choisit FFF. Et gagne.

:ptdr: Chat échaudé craint la souris matheuse

par **Imod** » 26 Juin 2007, 23:01

Un problème qui me plait mais comme il dépasse de beaucoup le domaine de mes compétences , et qu'il ne lève pas les foules sur ce forum : je le soumets ailleurs .

Bien sûr , alben , je te tiens au courant .

Imod

par **alben** » 26 Juin 2007, 23:16

Imod a écrit:Un problème qui me plait mais comme il dépasse de beaucoup le domaine de mes compétences , et qu'il ne lève pas les foules sur ce forum : je le soumets ailleurs .

Bien sûr , alben , je te tiens au courant .

Imod

Bonsoir,
Je suis un peu étonné. Je pensais qu'il n'allait pas faire long feu, la solution "calculatoire" est très simple à formuler (si on la prend par le bon bout).
Je donne la réponse si plus personne ne s'y attelle.

par **Imod** » 26 Juin 2007, 23:24

Tu peux la donner alben ! ( J'ai tendance en ce moment à prendre tous les problèmes par le mauvais bout ) .

Imod

Mais bon il n'y a pas urgence , en ce moment je ne trouve même pas le temps de lire mon courrier :briques:

par **alben** » 27 Juin 2007, 00:33

Bonsoir Imod
C'est une chaine de Markov assez simple : Après deux lancers, personne n'a encore gagné mais selon le résultat des deux tirages précédents, l'un des joueurs peut être en position de gagner (ou les deux ou aucun) selon leurs deux premiers choix.
Prenons l'exemple de PPF contre PFF
Si le résultat des deux premiers lancers est PP, le premier joueur a une proba de 1/2 de gagner au 3ième coup. Idem pour l'autre joueur avec PF.
Cela se généralise au coup n :
proba de gagner pour le premier joueur = (proba d'avoir PP avant le coup n)/2

Il suffit donc de connaitre les probas successives d'avoir PP à l'issu des n-1 lancers.
Après 2 lancers elles est égale à 1/4 pour toutes les paires. Ensuite elle le resterait si n'y avait pas d'arrêt parce que l'un des joueurs gagne.

Le gain du premier joueur élimine une possibilité PF et le gain du deuxième élimine une possibilité FF (la fin de leur choix).

soit

avec prob(PP/n)= proba d'avoir PP après n lancers
et

(j'ai indiqué par des -1 les possibilités qui disparaissent en cas de gains durant le coup n).
et finalement la probabilités de gains seront la somme :

avec

On ne retient que les valeurs qui correspondent au 2 premiers choix de chaque joueur
C'est vrai c'est ensuite un peu calculatoire mais ça se programme très bien.
Il s'agit d'inverser des matrices 4x4 avec des zéros et des 0,5
Avec une feuille de calcul excel, j'ai pu effectuer tous les cas en une vingtaine de minutes
Voici ce que ça donne (j'ai supposé que chacun misait 60 afin d'éviter les fractions)
En bleu ce sont les choix optimaux (maximin et minimax)

PS j'avais commencé à te répondre sur les mathématiques.net mais je suis curieux de voir ce que ça donnera. Il me semble que ce problème est assez basique et je n'ai pas compris que BQss ou autre ne nous torche pas ça en quelques heures. Merci donc de laisser l'autre fil vivre, on verra bien

par **Imod** » 27 Juin 2007, 10:51

alben a écrit:la solution "calculatoire" est très simple à formuler (si on la prend par le bon bout).

Si on veut :livre: :++:

Imod

Defi proba 4

Qui est en ligne