The solution to yesterday’s puzzle was deduced by some in the comments. I was not able to solve the puzzle myself but in such cases, once I know the solution, I try to figure out why I could not figure it out, to see what I had overlooked.
In this case there are four possibilities for the two coin tosses: HH, HT, TH, and TT where H stands for heads and T for tails. The two coin tosses are independent of each other and so knowing the result of one doesn’t enable one to predict the result of the other. This tempted me to ignore (or not properly register) the information that each person gets to see the result of his or her own toss before predicting the other. And since the captives each gets to make just one guess, that seemed to me to suggest that they must guess wrong at some point.
But that information of knowing your own result is critical in reducing the number of possibilities from four to just two by grouping them: either both tosses give the same result or they give opposite results. If one captive chooses to predict the same result as his/her own and the other the opposite result, together they will cover both possibilities and one must be right.
As Jenkins explains more fully:
If Alice gets heads, she will guess that Bob also got heads, and if she gets tails she will guess that Bob also got tails. Meanwhile, if Bob gets heads he will guess that Alice got tails, and if he gets tails he will guess that Alice got heads. Then exactly one of them will always be right.
The simplest way that I can see of explaining this solution is that the outcomes of the two coin tosses must be either the same or different, so one of the mathematicians should always guess that they were the same, and the other that they were different. It’s irrelevant whether the coins are fair or not.
The solution is simple, but there’s still a slightly magical flavor to it in my mind. What I find so remarkable is that, for the strategy to work, both Alice and Bob need to see the outcome of their own coin toss, even though it’s totally uncorrelated with the outcome of the other’s toss!
Post-script (12 Oct. 2017): I was forgetting to mention that the puzzle has a happy ending. After a full year of one of the mathematicians guessing correctly every morning, the king, who understood very little about logic or mathematics, became convinced that Alice and Bob could communicate telepathically. Concerned that they might have other uncanny powers that they could use to harm him, he freed them under the condition that they leave the kingdom and never return.
As I said, this is a nice puzzle.