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.
Since this nice little puzzle is fresh in my mind, and I want to waste 20 minutes before quitting work for the weekend, I can go through the thought processes I used to solve it. My wife likes logic puzzles more than I do, so maybe I’ll give it to her to chew on over the weekend.
It took me about 20 minutes to solve, I’m certain that’s not a record, but I did the logical thing first and charted all the coin-flips, guesses, and winning scenarios, looking for a pattern among the losing scenarios. At the end of that time I said to myself, “okay, any random choice will cause them to lose 25% of the time.”
But then I looked at the problem differently. Alice and Bob each have two choices on what to say, Heads or Tails. Does it matter what they say if they based their decision on the coin flip they did see? Well, I thought, it might if they make their decision after they see how the coin flipped (I didn’t know how at that point), but it certainly wouldn’t if they made their decision prior to the coin flip. I had to go back a re-read the puzzle at that point, and noticed that the puzzle explicitly said they gave their response after the coin flip was witnessed. So the key was somehow related to witnessing the coin flip.
So what were the options for Alice and Bob? They could always predict the other’s flip was the same as their own, or always predict it as opposite from their own. Or, maybe, there was a much more complex strategy, maybe one day pick their own and another day pick the opposite. I felt that was unlikely as the solution was mentioned to elegant, but I didn’t completely discount it either. What’s elegant to Mano may seem very complex to me. However, on some reflection I rejected a more complex strategy because without knowledge passing between Alice and Bob, the coins would align properly with the wrong choice.
It wasn’t hard to see that if both Alice and Bob chose the same strategy of predicting the same as the coin they could see, there would be a case where they both were wrong (Alice sees heads and predicts Bob’s coin shows heads while Bob sees tails and predicts Alice’s coin shows tails). The same applies to them predicting the opposite of the coin they saw flipped. Which left the strategy of one always picking the same as the coin they saw flipped, and the other always picking the opposite. Running that strategy through my logic table showed that while there are some winning combinations which are missed with that strategy, there were no losing combinations.
It does appear to me that as long as they are not executed there is one piece of information which does pass between Alice and Bob every day. They know at least one of them guessed correctly. But I couldn’t figure out how that would have any bearing on their strategy, but maybe someone else can figure out a complex strategy using that information.
And now I’ve completed my nine hours here at work, and I feel comfortable going home. Happy Weekend!
There’s really a whole class of solutions. A nice and simple one is that Alice guesses that they’re the same while Bob guesses that they’re different (or vice versa). But they could also have a strategy in which they swap roles every other day … or all sorts of other variations like that, as it’s totally irrelevant how they go about determining what they’re going to do, what information they may use for that purpose, etc. For another example, Alice could say they’re the same only when the number times they’ve guessed a coin toss is prime, while Bob does the opposite. Or it could be when the number of Saturday coin tosses is divisible by 5, or whatever you like really.
Of course, making it more complicated runs the risk of them forgetting what they’re supposed to do for any given coin toss. But if we’re allowed to simply give a strategy and assume they will carry it out perfectly, the important thing is just that they somehow conspire to pick “same outcome” and “different outcome” every time, because one of those must be correct.
Well, I said it “must” be so, but let’s hope a coin never lands on its edge. If that ever happened, perhaps everyone will be so thoroughly surprised by it that the prisoners can make their escape.