The two leading mathematicians in the kingdom, Alice and Bob, have run afoul of their tyrannical king. Rather than behead them outright, the king decides to prolong their misery by locking them in separate dungeons, so that any communication between them is impossible.
Each morning, a guard is to enter the corresponding dungeon and toss a coin so that the prisoner in that dungeon can see the outcome. Then the prisoner will be asked to guess the outcome of the coin toss in the other dungeon (i.e., Alice has to guess the outcome of the toss witnessed by Bob, and Bob has to guess the outcome of the toss witnessed by Alice). If at least one of the two prisoners guesses correctly, they will live to see another day. Otherwise they will be put to death forthwith.
It would seem that the mathematicians are doomed. But as they are being led away in chains Alice and Bob manage to confer for a brief moment and they agree on a strategy that will delay their execution indefinitely. What is the strategy?….
Answer: If Alice gets heads, she will guess that Bob also got heads, and if she gets tails she will guess that Bob also got tails. Meanwhile, if Bob gets heads he will guess that Alice got tails, and if he gets tails he will guess that Alice got heads. Then exactly one of them will always be right.
The simplest way that I can see of explaining this solution is that the outcomes of the two coin tosses must be either the same or different, so one of the mathematicians should always guess that they were the same, and the other that they were different. It’s irrelevant whether the coins are fair or not.
The solution is simple, but there’s still a slightly magical flavor to it in my mind. What I find so remarkable is that, for the strategy to work, both Alice and Bob need to see the outcome of their own coin toss, even though it’s totally uncorrelated with the outcome of the other’s toss!