## A Prisoner Puzzle

This week I want to share what I thought was a very clever puzzle.  I stumbled upon this via the usual roundabout path, while investigating some new results I had learned about a couple of other problems.  This puzzle turns out to be related to those other problems in some interesting ways.  I will discuss those relationships next week… along with attribution for this puzzle in its original form, since I modified it a bit here to include pirates:

You and a friend are being held prisoner by pirates.  The pirates are bloodthirsty, and so are threatening your execution.  However, they are also eccentric, and so are offering freedom for both of you if you can solve the following puzzle.

First, one of the pirates will take you into a room, leaving your friend outside.  In the room is an 8×8 chess board and 64 identical doubloons.  The pirate will place exactly one doubloon on each square of the board, showing either heads or tails as he sees fit (e.g., randomly).  He will then select and point out to you one square on the board.  You must then turn over exactly one of any of the doubloons (i.e., turning heads to tails, or tails to heads), and exit the room.

At that point, the pirate will take your friend into the room, leaving you outside.  If your friend is able to identify the square that was selected by the pirate, then both of you will be set free.  Otherwise, you will both be forced to walk the plank.

The pirates have explained these rules to you beforehand, and have allowed you and your friend to discuss strategy before beginning.  What strategy should you use to maximize your chance of survival?

This entry was posted in Uncategorized. Bookmark the permalink.

### 5 Responses to A Prisoner Puzzle

1. It seems to me that no strategy can increase the odds of survival, at least not without some trickery that arguably bends the rules (i.e. slip in extra information by rotating the flipped doubloon a certain way, or by replacing it sloppily after the flip).

The chess board set up by the pirate is a one-time pad. The message you get to encode is a single bit set in a zeroed 64-bit bit array. Your message and the OTP are XORed together (flip one doubloon). Your partner must decode your message without knowing the OTP, an impossible task. All possible messages are equally likely.

• I had the same impression; this is one reason why I really like this puzzle, because of that first impression of hopelessness. But consider the following simpler problem: suppose there are just two squares, and two doubloons. Can you survive in that case? What about three squares? What about four?

• anon says:

The simplest strategy in the case of the 2 square scenario is to always get the doubloon on the chosen square 1, and if it is already 1 then flip the other one. This means on the non-same situations you get 11 so your partner has to guess.

Suppose the 1st square is the target.
00: 100% chance
01: 50% chance
10: 50% chance
11: 100% chance

So in the 2-square scenario you have 100% chance to win in 50% of the situations, and 50% chance to win in the other 50%. This means on average you should expect to win 75% of the time (100%*50% + 50%*50% = 0.5+0.25=0.75), which is much better than random chance.

2. Pingback: Prisoner Puzzles | Possibly Wrong

3. Knut says:

I have found a solution, so spoiler alert!
To get started we should rephrase the question in a more mathsy way. The second prisoner only has the information of a chessboard with coins, so all he can do is to evaluate some function of board-possitions. An integer between 0 and 63 can be written uniquely as a sum of terms a_n 2^n for n=0 through 7. Hence the codomain of our function can be taken to be (Z/2)^8, where Z/2 is the field with two elements. This is a Z/2 vector space. The domain is all possible positions. Suppose you have two different possitions. We define their sum to be the position obtained from the second board by turning all coins in the positions corresponding to heads on the first board. It is clear that we have made the set of possible positions into a 64 dimensional Z/2 vector-space. The standard basis corresponds to possitions with only one heads and 63 tails. We pick a bijection between the set of these 64 basis vectors and the set of squares on the board. We extend this to a surjection, f, from (Z/2)^64 to (Z/2)^8. Suppose prisoner one enters the room
and find position p on the board and square k is pointed out to him. Then he only needs to turn the coin, e_n, corresponding to k+f(p). That is, f(e_n+p)= f(e_n)+f(p)=k+f(p)+f(p)=k.