Two Mathematicians and a Coin (Solution)
This problem was very unintuitive to me!
Here’s a strategy that will allow them to live indefinitely. Mathematician #1 always guesses the same result as the coin flip that he was shown. Mathematician #2 guesses the opposite as the result of the coin of the coin flip that he was shown.
To prove this works, here are the possible outcomes:
| M#1 sees H | M#1 sees T | |
| M#2 sees H | (H, T) | (T, T) |
| M#2 sees T | (H, H) | (T, H) |
The simple way to state why this works is that M#1 guesses the result of the coin flips will be the same and M#2 guesses that they will be different. One of them has to be right! Althought that’s a very elegant way of summarizing the solution, I think it’s only useful in understanding the solution after you know it, not in actually generating the solution.
Here’s how I think one could generate the solution. Let’s first focus on deterministic strategies. Without loss of generality, we can say that when M#1 sees H he will guess H (we could have picked T and the following chain of logic would work just as well).
| M#1 sees H | M#1 sees T | |
| M#2 sees H | (H, ) | ( , ) |
| M#2 sees T | (H, ) | ( , ) |
So, still assuming that M#1 saw H, if M#2 sees H, then M#1 will be correct and they will survive, so it doesn’t matter what M#2 does in that case. However, if M#2 sees T then M#1 will be wrong and therefore M#2 needs to be correct in order for them to survive, so M#2 needs to pick H if he sees T.
| M#1 sees H | M#1 sees T | |
| M#2 sees H | (H, ) | ( , ) |
| M#2 sees T | (H, H) | ( , H) |
So now we see that if M#2 sees T and M#1 sees T, M#2 is going to guess wrong, so M#1 better guess right (i.e. T).
| M#1 sees H | M#1 sees T | |
| M#2 sees H | (H, ) | (T, ) |
| M#2 sees T | (H, H) | (T, H) |
Finally, it’s clear the case in which they still have problems is if M#1 sees T and M#2 sees H. We haven’t determined what M#2 will do in that case yet, so let’s say if M#2 sees H, he guesses T.
| M#1 sees H | M#1 sees T | |
| M#2 sees H | (H, T) | (T, T) |
| M#2 sees T | (H, H) | (T, H) |
As you can see, from a random first decision (M#1 will guess H if he sees H), every other decision was forced, and we somehow come to a solution which never loses.