Défi Turing

Accueil - Enoncés -


Problème 248

Cible mouvante

Sur un quadrillage de n carrés sur 1, une cible rouge est placée au hasard sur un des carrés dont le fond est du même rouge. La cible est donc invisible.
Après chaque tir, la cible se déplace vers une case adjacente de manière aléatoire.
Le tireur est un expert, qui ne manque jamais la case visée, et adopte une stratégie lui permettant de minimiser son nombre de tirs maximum, que l'on notera C(n). (Attention ! Cette stratégie ne minimise pas nécessairement l'espérance !)
Si la cible est atteinte, la case change de couleur et la cible devient alors visible, afin de signifier au tireur qu'il l'a touchée et que la partie est terminée.
Soit E(n) le nombre moyen de coups nécessaires pour atteindre la cible.

On donne E(1)=1, E(2)=E(3)=3/2, E(4)=37/16 et E(5)=19/6.

Que vaut E(10)?

On saisira le produit du numérateur par le dénominateur de la fraction irréductible obtenue.

Précision : le calcul de E(n) sera basé uniquement sur tous les trajets possibles de la cible comprenant exactement C(n) déplacements, comme si la cible se déplaçait toujours C(n) fois, qu'elle ait été touchée ou non.

précédent
suivant