I have been given the following problem:
On a grid of n squares out of 1, a red target is randomly placed on one of the squares with the same red background. The target is therefore invisible.
After each shot, the target moves randomly to an adjacent square.
The shooter is an expert, who never misses the target square, and adopts a strategy allowing him to minimize his maximum number of shots, which is noted as M(n). (Warning! This strategy does not necessarily minimize the expectation).
If the target is hit, the square changes colour and the target then becomes visible, in order to indicate to the shooter that he has hit it and that the game is over.
Let E(n) be the average number of hits needed to hit the target.
We give E(1)=1, E(2)= 1.5, E(3)=1.5, E(4)=2.3125 and E(5)=3.16..
What is E(10)?
NB: The calculation of E(n) will be based only on all possible paths of the target that include exactly C(n) moves, as if the target always moves C(n) times, regardless of whether it was hit or not.
I agree with n=1, 2 but I can't reproduce E(n) for n > 2:
- C(1) = 1 and E(1) = 1
- C(2) = 2 (shoot twice the same box) E(2) = 1/2 + 2*1/2 = 3/2
- C(3) = 2 (shoot twice in the middle) E(3) = 1/3 + 2*2/3 = 5/3 !!
I have been struggling on this one or a while. I can't really make sense of the PS so I am not using it and I guess this is my issue at the moment. If anyone can enlighten me ?
The calculation of E(n) will be based only on all possible paths of the target that include exactly C(n) moves, as if the target always moves C(n) times, regardless of whether it was hit or not.