SPCoding School

A room contains a normal 8×8 chess board together with 64 identical coins, each with one “heads” side and one “tails” side. Two prisoners are at the mercy of a typically eccentric jailer who has decided to play a game with them for their freedom. The rules of the game are as follows.

The jailer will take one of the prisoners (let us call him the “first” prisoner) with him into the aforementioned room, leaving the second prisoner outside. Inside the room the jailer will place exactly one coin on each square of the chess board, choosing to show heads or tails as he sees fit (e.g. randomly). Having done this he will then choose one square of the chess board and declare to the first prisoner that this is the “magic” square. The first prisoner must then turn over exactly one of the coins and exit the room. After the first prisoner has left the room, the second prisoner is admitted. The jailer will ask him to identify the magic square. If he is able to do this, both prisoners will be granted their freedom.

These rules are explained to both prisoners before the game begins and they are allowed some time together to discuss their strategy. Of course the question is: what strategy should the prisoners adopt?

Well, I propose they should use a strategy based on the method of types. so here it goes
Assume the guy in charges puts the coins on the board in the tail position with probability p and heads position with probability 1-p. (His eccentric attitude would make him choose p=1/2).
What happens is that you would expect 64*p tails and 64(1-p) heads on the board. What actually happens would be close to this but not exactly like this.

The prisoners will decide to flip the coin on the magical room, the other one comes in and computes the probability of each type of setting assuming that the magical room could be any of the 64 options, and the one chooses the setting which maximizes the probability of that particular type given p.

(They could have agreed to change the position of another room as long as they agree on a one to one mapping to map back to the magic room)

I'll try to think of a better solution.