Petit problème de pile ou face
Bonsoir à tous
C'est un problème posté sur internet et dont je n'ai pas le niveau pour trouver la réponse sachant qu'elle n'y était pas.
"Alice et Bob coopèrent pour essayer de gagner au jeu suivant.
Chacun de son côté va tirer à pile ou face 100 fois (évidemment de façon indépendante). Puis, après avoir observés leurs pièces respectives, ils choisissent (secrètement) chacun un nombre entre 1 et 100. Disons que Alice a choisi n, et que Bob a choisi m. Ils gagnent alors si le n-ième lancé de Bob est un pile, et que le m-ième lancé d'Alice est aussi un Pile. Donc en gros, chacun essaye de "prédire" un résultat pile de l'autre.
Peuvent-ils élaborer une stratégie meilleure que la stratégie naïve consistant à choisir un entier au hasard / choisir 1 quoi qu'il arrive ?"
Si quelqu'un a une piste, merci beaucoup.
C'est un problème posté sur internet et dont je n'ai pas le niveau pour trouver la réponse sachant qu'elle n'y était pas.
"Alice et Bob coopèrent pour essayer de gagner au jeu suivant.
Chacun de son côté va tirer à pile ou face 100 fois (évidemment de façon indépendante). Puis, après avoir observés leurs pièces respectives, ils choisissent (secrètement) chacun un nombre entre 1 et 100. Disons que Alice a choisi n, et que Bob a choisi m. Ils gagnent alors si le n-ième lancé de Bob est un pile, et que le m-ième lancé d'Alice est aussi un Pile. Donc en gros, chacun essaye de "prédire" un résultat pile de l'autre.
Peuvent-ils élaborer une stratégie meilleure que la stratégie naïve consistant à choisir un entier au hasard / choisir 1 quoi qu'il arrive ?"
Si quelqu'un a une piste, merci beaucoup.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tu peux expliquer plus précisément ?
Ils gagnent tous les deux simultanément si les deux conditions sont vérifiées ?
Ou bien ils gagnent chacun s'ils ont réussi leur épreuve sur l'information qu'ils ignorent ?
Je crois que je dis des trucs que je ne comprends pas moi-même, je vais aller me coucher !
J'ai trouvé le sujet sur internet et il n'est pas de moi donc je n'ai pas envie de dire une bêtise.
Cependant, je pense qu'ils gagnent tous les deux si les 2 conditions sont vérifiées.
:-S
Est-ce que quelqu'un saurait un peu expliquer avec des phrases en français "pourquoi ça marche" ou s'il y a une heuristique générale derrière? Je sais que ce n'est pas une demande usuelle en maths mais là mon intuition se heurte tellement à la réalité mathématique que c'en est troublant.
Alice parie sur l'entier i tel que i est la première fois qu'un pile apparaît chez elle et Bob parie sur l'entier j tel que j est la dernière fois qu'un pile apparaît chez lui.
EDIT: non! Voir plus bas.
Tu voulais bien dire que Alice et Bob peuvent renuméroter chacun.e différemment leurs lancers respectifs et que ça marche quand même? (par exemple Alice garde l'ordre originel et Bob inverse l'ordre)
Bonjour,
Quelqu'un peut m'expliquer ce que ça veut dire ?
Bob lance k fois une pièce équilibrée et Alice lance également k fois une pièce équilibrée.
Elles observent chacune leurs lancers (ie : Alice regarde les lancers d'Alice et Bob regarde les lancers de Bob).
À la fin elles proposent chacune un entier : Bob propose un entier m, Alice propose un entier n.
Elles mettent en commun leurs résultats (c'est le premier instant auquel l'une a accès aux résultats de l'autre) et gagneront si et seulement si le m ème lancer d'Alice est un pile et le n ème lancer de Bob est un pile.
La seule information possédée par Alice quand elle choisit un entier n est la suite des 100 résultats de ses propres tirages.
De même la seule information possédée par Bob quand il choisit m est la suite des résultats de ses 100 tirages.
Et si Alice et Bob choisissent n et m avant de faire les tirages ? Je ne vois pas quelle différence cela ferait.
Je trouve ça assez scandaleux.
[J'ai simplement corrigé les typos "iels". J'avais laissé les écritures inclusives avec les points ! C'est toi qui les a retirées !
Je trouve tes accusations assez scandaleuses (pour reprendre tes termes) ! AD]
AD : d'accord, excuse-moi, je t'ai prêté de mauvaises intentions. En fait "iels" n'était pas une typo. C'est une façon de ne pas préférer un genre à un autre lorsqu'on désigne un groupe d'individus comportant au moins un membre de chaque sexe.
Moi, je note $n=100$, au lieu de $k=100$ comme Foys.
Pour Alice : $(A_i)_{i=1\dots n} \leadsto X = \min\{i, A_i\}$ (rang du premier succès)
Pour Bob : $(B_j)_{j=1\dots n} \leadsto Y = \min\{j, B_j\}$
La probabilité de gain sous la stratégie de Foys est
$
\begin{aligned}
\P(A_Y, B_X) & = \sum_{i,j=1}^n \P(X=i,Y=j,A_j,B_i) \\
& = \sum_{i,j=1}^n \underbrace{\P(X=i,Y=j)}_{\frac{1}{2^{i+j}}} \times \underbrace{\P(A_j,B_i\vert X=i,Y=j)}_{=1_{i=j}} \\
& = \sum_{i=1}^n \frac{1}{4^i} \approx \frac{1}{3}. \\
\end{aligned}
$
Par contre, je ne suis pas d'accord avec ça Pour $Z$ le rang du dernier succès de Bob, je trouve :
$
\begin{aligned}
\P(A_Z, B_X) & = \sum_{i,j=1}^n \P(X=i,Z=j,A_j,B_i) \\
& = \sum_{i,j=1}^n \underbrace{\P(X=i,Z=j)}_{\frac{1}{2^{i}}\times\frac{1}{2^{n-j+1}}} \times \underbrace{\P(A_j,B_i\vert X=i,Z=j)}_{=1_{i=j} + \frac{1}{4} \times 1_{i<j}} \\
& \approx \text{beaucoup plus proche d'un quart que d'un tiers à mon avis !}
\end{aligned}
$
Autrement dit, je réponds non à la question de Linderberg ici : http://www.les-mathematiques.net/phorum/read.php?16,2214782,2215772#msg-2215772
Toujours $n=100$ lancers pour chaque joueur, mais cette fois-ci avec une proba de succès très faible de $p = 10^{-6}$.
Les joueurs ont pratiquement perdu d'office, car ils n'ont qu'une chance sur $10,000$ d'avoir un succès chacun, donc une chance sur $10,000^2$ d'en avoir un tous les deux.
Si jamais ils devaient avoir tous les deux eu un succès, pour gagner, ils devraient encore deviner la position du succès de l'autre. (on néglige les cas où ils auraient eu plusieurs succès !)
Ils ont 1 chance sur 100 d'avoir eu leur succès au même tirage.
Ils n'ont qu'1 chance sur 10000 de deviner autrement tous deux le succès de l'autre.
C'est vite vu, ils doivent chacun miser sur leur rang d'apparition !
Mieux vaut qu'ils décident tous les deux de miser sur le premier ou tous les deux sur le dernier, mais pas de croiser leurs choix.
Soit $d\in \N$
Soit $f$ l'application de $\{0,1\}^d$ dans $\{0,1,...,d\}$ définie par $f(0,0,..,0):=0$ et $f(x):=\min \left \{k\in \{1,2,...,d\} \mid x_k=1\right\}$ si $x\neq (0,0,...,0)$.
Lorsque $A\subseteq \{0,1\}^d \times \{0,1\}^d $ notons $$P(A):= \frac{card(A)}{card \left ( \{0,1\}^d \times \{0,1\}^d \right)} = \frac{card(A)}{2^{2d}}$$
On note également les projections sur les coordonnées de la façon suivante: $\pi^1_k (x_1,x_2,...,x_d,y_1,y_2,...,y_d):= x_k$ et $\pi^2_k (x_1,x_2,...,x_d,y_1,y_2,...,y_d):=y_k$ pour tout $k\in \{1,...,d\}$ et tout $(x,y)\in \{0,1\}^d \times \{0,1\}^d$.
Pour tous $p,q\in \{1,...,d\}$ soit $B_{p,q}:= \left \{ (x,y) \in \{0,1\}^d \times \{0,1\}^d \mid f(x)=p \text{ et } f(y)=q\right \}$.
Alors $P(B_{p,q})=2^{-p-q}$. Les $p,q\mapsto B_{p,q}$ sont évidemment disjoints. De plus $$\begin{align}\bigcup_{k=1}^d B_{k,k}= & \left \{ (x,y) \in \{0,1\}^d \times \{0,1\}^d \mid f(x)= f(y) \text{ et } f(x)>0\right \}\\ \subseteq & \left \{ (x,y) \in \{0,1\}^d \times \{0,1\}^d \mid f(x)>0,f(y)>0,\pi^2_{f(x)}(x,y)=1 \text{ et } \pi^2_{f(y)}(x,y) = 1\right \} \tag 1\end{align}$$ Et bien sûr $P\left ( \bigcup_{k=1}^d B_{k,k} \right )=\sum_{k=1}^d 4^{-k}$.
Après on peut donner un habillage probabiliste à l'énoncé de pur dénombrement fini ci-dessus ($(1)$ est l'ensemble où Alice et Bob gagnent quand ils choisissent la stratégie consistant à jouer $f$).
Mais si Alice et Bob s'entendent sur une permutation $\sigma$ de $\{1,\ldots, n\}$ :
Alice parie sur $\sigma(X)$ où $X$ est le numéro de son premier pile.
Bob parie sur $Z$ qui est le premier tel que le tirage $\sigma(Z)$ soit pile.
Alors ça marche aussi, n'est-ce pas ?
PS. Ce qui fait la différence entre parier avant les tirages ou parier après, c'est que Alice sait que Bob va parier le numéro de son premier pile. Si le premier pile d'Alice est le numéro k, il serait idiot pour elle de parier sur une numéro plus petit que k, ça serait de toutes façons perdu.
EDIT : je parle du message où tu montres qu'a priori on ne peut pas permuter comme on veut l'ordre des lancers et rester sur une stratégie qui tend vers 1/3 pour un grand nombre de lancers
D'autant moins que le problème est probabiliste, car la probabilité de succès $p=\frac{1}{2}$ y est choisie arbitrairement, et que c'est tout à fait pertinent de la faire varier, en particulier de la choisir très faible, comme je montre ici : http://www.les-mathematiques.net/phorum/read.php?12,2214782,2216052#msg-2216052
Voici un paradoxe analogue, pour mieux illustrer mon argument sous hypothèse d'unicité du succès.
> @Gabuzomeu le calcul fait par MArsup montre qu'a
> priori non on ne peut pas permuter les lancers de
> Bob comme on veut.
As-tu vraiment réfléchi à ce que j'ai écrit ?
Le fait que les deux permutations soient inverses l'une de l'autre est favorable à leur succès.
La formule de conditionnement sachant le nombre de points fixes de $\sigma_{A} \circ \sigma_B^{-1}$ est sans doute assez jolie.
effectivement on ne peut pas choisir les permutations comme on veut, je m'étais trompé là-dessus. Alice et Bob doivent s'entendre sur les permitations choisies à l'avance pour que leurs réponses coïncident et ce sur un pile (environ 1 fois sur 3) pour que la même idée marche.