Jeu de cartes

Je ne crois pas qu'il existe une solution explicite. Il y a un probleme analogue dans 'Problemes de Probabilite" Presses Universitaires de France 1970, ou on retourne 52 cartes et il faut seulement deviner rouge ou noir: le probleme se modelise beaucoup plus facilement. Il y est mentionne que le probleme n'a pas de solution connue s'il faut deviner trefle-carreau -coeur-pique.

Déjà, je pense que l'on peut réduire "l'espace des configurations", en considérant les vecteurs de $\{ 0,1,2,3,4,5 \}^5$, avec $a \leq b \leq c \leq d \leq e$, qui représentent les cartes restantes dans le paquet, en "oubliant" le symbole, et classant dans l'ordre par nombre de symboles.

Dans la configuration $x = (a,b,c,d,e)$, si on note $|x| = a+b+c+d+e$, la probabilité de deviner juste est $p(x) = \frac{ \min x }{|x|}$

Il y a ${ 10 \choose 5 } = 252$ possibilités (ça peut être vu comme une combinaison avec répétition), ce qui réduit pas mal le problème par rapport à une modélisation naïve.

On peut alors faire un graphe, mettre la probabilité de transition sur les arrêtes $P(x\to y)$, et la probabilité de deviner la bonne carte à ce noeud, $p(x)$. Ensuite, on va "sommer le graphe" :

On dira que $x$ est de niveau $n$ si $|x| = n$. On note alors $N(n) = \{ x : |x| = n \}$

Ensuite, en partant du niveau 25 :

Pour chaque nœud de niveau $n$ on calcule la proba d'y être : c'est donné par $P(x) = \sum_{y \in N(n+1)} P(y) P(y \to x)$.

Et alors l'espérance est $\sum_{n=0}^{25} \sum_{x\in N(n)} p(x)P(x)$


A vue de nez, ça me semble très très raisonnable comme complexité algorithmique (sous réserve que ce que j'ai écrit plus haut soit correct)