Two Mathematicians and a Coin

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?

Solution