I came across this nice little puzzle that I got from the Quora website from someone named Alejandro Jenkins who said that he cannot recall where he first heard or read about it. In its essentials it is easy to state and understand even though, as seems to be the tradition with such puzzles, a story is constructed around it.
The two leading mathematicians in the kingdom, Alice and Bob, have run afoul of their tyrannical king. Rather than behead them outright, the king decides to prolong their misery by locking them in separate dungeons, so that any communication between them is impossible.
Each morning, a guard is to enter the corresponding dungeon and toss a coin so that the prisoner in that dungeon can see the outcome. Then the prisoner will be asked to guess the outcome of the coin toss in the other dungeon (i.e., Alice has to guess the outcome of the toss witnessed by Bob, and Bob has to guess the outcome of the toss witnessed by Alice). If at least one of the two prisoners guesses correctly, they will live to see another day. Otherwise they will be put to death forthwith.
It would seem that the mathematicians are doomed. But as they are being led away in chains Alice and Bob manage to confer for a brief moment and they agree on a strategy that will delay their execution indefinitely. What is the strategy?
What I like about this puzzle is that there is no trickery involved, no hidden meanings and the like. It is a straightforward logic puzzle. Jenkins provides the solution but for some reason, I cannot deep link to it and so will wait a day to let people discuss it in the comments if they so choose and then post the solution in the comments.
An elegant problem and solution.
I don’t know the answer. But the puzzle reminds me of one of the Car Talk puzzlers, involving prisoners and light switches: https://www.cartalk.com/radio/puzzler/prison-switcharoo-0
Actually it was only when looking for the above, that I realized all the Car Talk puzzlers are available in an archive at https://www.cartalk.com/radio/puzzler
Yes, that Is quite a clever little problem. Fortunately I was able to work out a solution.
Is the solution that the first one always guesses that the second one’s coin will be the same as their coin, while the second one always guesses that the first one’s coin will be different from theirs. As such, if the two coins do show the same result then the first one is correct, while if they show different results then the second one is correct.
@4 cartomancer
By my reading, that would imply communication between the two, since “same” and “different” refer to the other’s outcome, and Manu said there’s “no trickery involved, no hidden meanings and the like.”
@4 cartomancer
Actually, no, I got the timing wrong. First the coins get tossed THEN they see the outcome, so their prediction only depends on what they see, in which case your solution would work.
This is one of the most satisfying riddles I have ever seen. It still bends my mind in a way, but the constraints are absolutely perfect in that one of the two mathematicians will always be wrong (in order to assure that one will always be right).
It’s obvious! Everyday, the Mathematician’s Liberation Front subreptitiously exchanges the guard’s coins by a pair of entangled quantum coins prepared in a correlated Bell state. Simple and efficient! 😁
cartomancer @4: Ye gods, historians can think!
無
As soon as I saw this puzzle, I knew it would come down to some area of linguistic ambiguity, because these sorts of puzzles usually do. The solution, ‘one guesses the flips will match, the other guesses they will not match’ does not, to my reading, match the demand: “Then the prisoner will be asked to guess the outcome of the coin toss in the other dungeon (i.e., Alice has to guess the outcome of the toss witnessed by Bob, and Bob has to guess the outcome of the toss witnessed by Alice).”
Notice the wording: the coin toss, the toss, the toss. Singular each time. The king is demanding that they guess the result of one of the tosses, not both as a pair. Since neither ‘they match/they don’t match’ makes a statement as to the outcome of any one toss, they lose and get executed on the first night.
Holms:
Usually does not mean always.
Each prisoner (plurality) will be asked to guess the outcome of the other’s coin toss. Two prisoners, two guesses. Two singulars together add up to a brace.
So, no.
Ahem:
“If at least one of the two prisoners guesses correctly, they will live to see another day.”
Each one makes a statement about the outcome one toss; such matching as there is relates to the truthfulness of either, not to their concordance.
Holms @11: There is no ambiguity whatsoever. They confer briefly. Alice says to Bob “You assume the coin tosses agree. I’ll assume they differ.” Bob nods. One of them will always be right.
#12 John
Which is why I refrained from saying always.
Each prisoner is ordered to guess the result of a specified coin toss, out of the two.
So, yes.
But if their guesses are not within the permitted parameters (i.e. guessing the result of one specific coin toss), then their answer can hardly be considered a correct guess. Hence execution.
#13 Rob
My objection is not based on their being able to confer and coordinate before being separated, it is based on the king demanding they guess the result of a single specific toss, rather than the combined pair.
@Holms #11
Consider: Alice’s coin comes up Heads and Alice guesses Bob’s came up Tails (always guesses the opposite). If Bob’s did come up Tails, Alice was right and they live. If Bob’s came up Heads, Alice was wrong, but since Bob chose Heads (always guesses the same), Bob correctly guessed Alice’s coin, and they live. Foolproof.
(I didn’t work it out myself)
@Holms
Meh, never mind my reply; I misunderstood your objection to the problem as misunderstanding the solution. I don’t really understand your objection either since the posed problem does clearly say If at least one of the two prisoners guesses correctly, they will live to see another day. I’ll just go back to sleep.
Mea culpa, I am the one who misunderstood the wording of the reply, I am wrong.
@quantumdad you jest about using entangled coins, but I think that this problem can be mapped to Deutsch’s algorithm (Can a function f:{0,1}->{0,1} be distinguished as balanced or constant in just a single evaluation?)