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?