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?

(In reply to N = 1 (spoiler) by Steve Herman)

As less information is better for Merkle to remain hidden Merkle would only report one of the four cardinal directions {N, S, E, W} and not one of the compound directions {NE, NW, SE, SW}, thus to simplify, only a report of one of the four cardinal directions will be assumed in the analysis. The initial report will reveal N*(N+1) possible hiding places to the Hunter, thus the probability of finding Merkle on the first turn on an NxN grid is 1/(N²+N).

For N=1, the hunter would be told either "North" or "East". Both options provide 2 possible hiding places for Merkle. If not discovered, as Merkle can not move to the locaton occupied by the hunter or remain stationary, he is limited to two possible locations to hide. The same minimal information provides the same probability, 1/2 or 50%, on each subsequent turn he remains hidden.

For N=2, given Merkle's initial location and moves are random and the Hunter is astute, in order to increase the probability of finding Merkle the Hunter's initial move would be to (1,1), the center of the grid, thus limiting the area Merkle can move to and increasing the probability of finding him. After the move, if Merkle has not been found, Merkle's report can permit a deduction of his location to two possible locations. One of these would be where the Hunter just left, i.e., the center of the grid. Thus, repeating a cycle of moving to the grid center and then to the cardinal direction reported by Merkle keeps the probability each turn, after the first, of 1/2 or 50%.

For N=3 and greater, each subsequent move of Merkle gives different probabilities, and becomes too complex without the aid of a computer program and without experience in mathematical analysis.

 

Edited on January 21, 2012, 2:53 am

Posted by Dej Mar on 2012-01-21 02:51:29