Two Mathematicians an 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 HM#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 HM#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 HM#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 HM#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 HM#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.