Fun math puzzle: two mathematicians and a coin…
The king is very angry at his two best mathematicians, but rather than executing them immediately institutes the following process:
They are banished to opposite ends of the kingdom, kept under 24 hour guard. Every day in both Westerville and Eastgate where the mathematicians are being kept one of the guards flips a coin and records the result. Each mathematician must then guess the result of the flip at the other end of the kingdom. A messenger is then dispatched from each location to the royal palace to share the results of the flip and their mathematician’s guess. As long as one of the two mathematicians guesses right, the lives of both mathematicians are spared until the next day. The first day that both mathematicians are wrong, they are both executed.
The king imagined this game would not last more than a week or so. The mathematicians, however, hatched a clever plan as they were being ushered out the door of the castle.
What do the mathematicians do to live as long a life as they can, and on average how long should the king have to wait to execute them?
— Max
Max Schireson's blog 
first thing that comes to mind is that one gussies tails and the other heads
obviously it not the wright answer but it’s a start
That would work if they were both trying to guess the result of a single flip – but I wouldn’t have bothered to post that problem. On a reasonable track, keep working on it!
For full points, can you provide an explanation of why one is guaranteed to be correct?
OK. Let’s call the mathematicians X and Y and their guards A and B.
The mathematicians have agreed to set {X = A, Y = not(B)}
If A == B, then X == B and so the first mathematician guessed correctly.
If A == not(B), then Y == A and so the second mathematician guessed correctly.
Since a single coin flip only has two possible outcomes, the two cases above enumerates all possible situations.
One guesses the same as his result, and one guesses the opposite of his result. Writing out all of the possible combinations of this shows that one man always guesses right, one always guesses wrong, and the king will never get to execute the mathematicians.
Any simple way for us to believe that it works without having to write out all the possibilities?
— Max
simple explanation:
The results of the two coin flips must either be the same (heads-heads / tails-tails) or opposites (heads-tails / tails-heads).
If the coin flips were the same, then the mathematician who guesses the same is correct.
If the coin flips are opposites, then the mathematician who guesses the opposite is correct.
Very good.
Since each one has to guess the other one’s result, and each coin flip is independent of others, the chance of mathematicians being executed in any given day is 1/4, and there’s absolutely nothing they can do about it. Unless you didn’t describe the problem correctly.
You are correct that each one has to guess the other’s result, and you are correct that the flips are independent of each other. But it doesn’t follow that the odds of them being executed on a given day are 1/4.
Yes, the flips are independent, but what makes you so confident that the correctness of the guesses are independent?
Because I assumed they can’t communicate in anyway when they are in exile. The only prior information they have is that they haven’t been executed (i.e. either of them has been correct on any day) so far, and what the coin flip result on their side is. None of these change the fact that they can only be correct about the other side by a 50% chance. The chance of both being wrong is thus 50% * 50% = 25%.
You are correct that they can each only be correct 50% of the time. But even without communication between them, the correctness of their guesses need not be independent. For example each could guess that the other coin has the same result as theirs. They will either both be right or both be wrong. 50% chance of execution. If they can make it worse than 25%, can they make it better?
It really wasn’t clear from the problem statement that each mathematician gets to see the result of the flip on her side of the kingdom. Why would one assume that the guard flips in the presence of his prisoner, or tells her the outcome? Without that crucial detail the problem is very different….
Yes, I could have made that clearer. They do get to see the flip on their side.
amazing how nonintuitive.
what are the probabilities of failure with optimal strategies with N mathematicians where N > 2?
thinking about a tiny bit more not clear the problem generalizes in a non-boring way.
I have some that aren’t exactly generalizations of this but are conceptually similar and aren’t boring. I will do a little series.
Here’s what I think is the easiest way to understand way to explain the solution:
The prisoner who always guesses the other end of the kingdom’s toss is the opposite of his end is guessing the two tosses will never match.
The prisoner who always guesses the other end of the kingdom’s toss is the same as his end is guessing the two tosses will always match.
Each day there are only two possibilities. Either the tosses match or they don’t. If each prisoner sticks to their system, one will always be correct!
Well stated.
[…] you’d like a hint, look at this problem. Thanks to Dwight for suggesting more complex problems in that spirit; if this isn’t hard […]
[…] This is a puzzle adapted from Max Schireson’s blog. […]