An "x-y" grid game that I know as "Find Merkle" [
M] requires a player [
H] to begin at (0,0) and zero in on a hidden co-ordinate location of the creature by nominating
one of the 4 cardinal directions and an integer distance. Upon failure to land on that location you are given just one cardinal direction towards that site.
Supposing "Merkle" is hiding at (5,5) and you are at (3,8) after your second play, which was either E3 or N8, you are told E or S, nothing more.
Let us allow two changes to this.
Firstly the player is told to move in
one of 8-point compass rose directions.
Secondly, upon failure to capture, "Merkle", having no knowledge of the hunter's location, randomly relocates to any of his immediately adjacent 8 locations except for one if already occupied by the hunter.
- This is exemplified if "H" has been told "SE" and has relocated to (6,5).
Oh, and the hunter only knows "Merkle's" location upon capture.
Given that the hunter is astute and multiple games are played, what is the most likely number of moves to capture "Merkle" within an NxN grid?
If N = 1, then Merkle is equally likely at all times to be in any one of the three spaces not occupied by H. If H can move freely, then the cardinal direction information (because it is given before M randomly relocates) is of no value. So H has a 1/3 chance of finding M in 1 move. If he has not found M in 1 move, which occurs with probability 2/3, then he has 1/3 chance of finding him on move 2. Putting that together, he has a 2/9 chance of finding M on move 2. He has a 4/27 chance of finding N on move 3, 8/81 chance of finding N on move 3, Etc. Since 1/3 is the highest value out of 1/3, 2/9, 4/27, 8/81, etc., 1 is the move on which he is most likely to find Merkel.
Same answer if H is forced to move in the indicated cardinal direction.
N=2 is too complicated a case to be dealt with analytically under these rules, and I will not attempt it.
N = 1 (spoiler)
