[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Array to string conversion
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Undefined variable: Array
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Trying to access array offset on value of type null
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Array to string conversion
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Undefined variable: Array
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Trying to access array offset on value of type null
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Array to string conversion
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Undefined variable: Array
[phpBB Debug] PHP Notice: in file [ROOT]/includes/functions_content.php on line 77: Trying to access array offset on value of type null
SPCoding School • View topic - Prisoners Puzzle: coins on a chess board

Prisoners Puzzle: coins on a chess board

Prisoners Puzzle: coins on a chess board

Postby Rafael » Mon Dec 08, 2014 7:01 pm

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?
Rafael
 
Posts: 4
Joined: Fri Dec 05, 2014 11:40 pm
Location: Unicamp

Re: Prisoners Puzzle: coins on a chess board

Postby Karzand » Wed Dec 10, 2014 6:04 pm

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.
Karzand
 
Posts: 1
Joined: Wed Dec 10, 2014 5:48 pm


Return to Puzzles

Who is online

Users browsing this forum: No registered users and 0 guests

cron