Try this good brain teaser:

A king is angry at two mathematicians, so he decrees the following punishment. The mathematicians will be imprisoned in towers at opposite ends of the kingdom. Each morning, a guard at each tower will flip a coin and show the result to his prisoner. Each prisoner must then guess the result of the coin flip at the other tower. If at least one of the two guesses is correct, they will live another day. But as soon as both guesses are incorrect, they will be executed.

On the way out of the throne room, the mathematicians manage to confer briefly, and they come up with a plan. What is their strategy and how long, on average, should the king have to wait to execute them?


Here’s where the impossible comes in. What if I told you they can do better than just randomly guessing the result of the other person’s coin flip (and therefore dying with \(\frac{1}{4}\) probability each day, and therefore living, on average, 4 days)?

Do not look at the solution before you’ve either found a strategy that is better than random or you’ve sufficiently convinced yourself that it’s impossible. If you’re in the latter group, I have a favor to ask you. Please write a detailed comment explaining why it’s impossible before looking at the solution. Thanks!

Solution