# Alternative solutions to a Michael Rabin puzzle

I first heard the puzzle below around 1990 while working at Carnegie Mellon University; the puzzle was attributed to Michael Rabin. After solving it, I realized that alternative solutions are possible.

There is a world in which the inhabitants have a strange physiology. A healthy person who ingests a poison will die within an hour unless he or she ingests a stronger poison; the stronger poison restores complete health. The poisons in this world are strictly linearly ordered in strength. Moreover there are two kinds of poisons: magical and medical, which are dispensed by the Royal Magician and the Royal Physician respectively. No magical poison has the same strength as a medical poison. All of these facts are common knowledge.

The King decides that he wants to find the strongest poison in the land, because it will not only be very useful for eliminating enemies but will also act as an antidote against any other poison. So he calls in the Royal Magician and the Royal Physician and says, "I want each of you to return here to my royal chambers at noon one week from now. Bring a vial of your strongest poison. To give you incentive to bring your strongest poison, you must do the following: each of you must drink from the other's vial first and then drink from your own vial. I will have trained observers present to make sure that you cannot cheat. Then you will be watched for one hour, during which you may not ingest any substances. The person who has the stronger poison will of course survive and the other will die. This is unfortunate but I have decided that it is worth it, in the interests of national security. If I detect any attempt to circumvent these rules you will both be executed. You may go now, but you must return at the specified time."

The Royal Physician and the Royal Magician go off, both very disturbed, because neither wants to die. Each has had some experience with the other's poisons and knows that some of them are quite potent. Neither of them is fully confident of having the strongest poison. Nor does either have any way of getting access to the other's poisons. They rack their brains all week trying to think how they can best ensure their own survival.

The appointed time rolls around and the two Royal Servants return. They follow the specified protocol exactly, and are watched carefully for one hour. To everyone's astonishment, both Royal Servants keel over and die within the hour. The Royal Coroner confirms that both died of poisoning.

There are two parts to this puzzle.

1. Find the original, intended solution.

2. Find three alternative solutions that are arguably just as plausible as the intended solution.

Here is a hint for part 2:

Use "Sicilian reasoning" à la The Princess Bride.

• Multiple "arguable" solutions indicates this should be closed as inviting speculative answers May 10, 2023 at 4:15
• @bobble The intended answer is a satisfying one once you hit upon it. It feels like the correct answer. However, once you accept the intended answer as valid, and think further about it, then you can show that there are three other possibilities that are equally valid, in the sense that they have the same general structure as the intended answer. I included the word "arguably" only because it is the nature of a lateral-thinking puzzle that the validity of an answer cannot be proved using pure logic. Perhaps I should delete the word "arguably" so as to avoid confusion? May 10, 2023 at 4:36
• To put it another way, I can give what I find to be a compelling argument that there are exactly four valid solutions to the puzzle. So it's not that the puzzle is ill-defined or open-ended in the sense that it invites "speculative answers." But as I said, my "compelling argument" falls just short of a rigorous proof, since that is the nature of lateral-thinking puzzles. May 10, 2023 at 4:50
• Given the OP's explanations, I think this question satisfies the site's rules and thus should remain open. May 10, 2023 at 12:58
• If you want to be extremely formal about it, we can even avoid the word "stronger." The toggling elixirs have special properties. Given any two elixirs A and B, either drinking A (when healthy) followed by drinking B (before dying) will make you healthy again, or drinking B (when healthy) followed by drinking A (before dying) will make you healthy again, but not both. In the former case, we say that B is "more bodacious" than A; in the latter case, we say that A is "more bodacious" than B. Moreover, if A is more bodacious than B and B is more bodacious than C, then A is more bodacious than C. May 13, 2023 at 0:20

The intended solution is:

Each Royal Servant drank a weak poison just before arriving at the showdown, and, instead of bringing a strong poison as requested, brought water. They drank the other Servant's water, then drank their own water, and died of their own poison.

But why did they do this?

Each one was hoping that the other would not think of the same trick and would, as requested, bring a strong poison to the showdown; that way, the opponent's strong poison would cure them of their own weak poison, and they would live, while the opponent would die of their own poison.

I personally think that this is a brilliant puzzle, and I congratulate Michael Rabin for coming up with it. However, if one takes the logic a step further, one realizes that there are further possibilities.

Let's use the term "Conventional Strategy" for the strategy of bringing a strong poison to the showdown, and arriving healthy. Let's use the term "Weak Poison Strategy" for the strategy of drinking a weak poison just before arriving at the showdown, and bringing water. There are two other strategies to consider. The "Water Strategy" is to arrive healthy and bring water. The "Double Dose Strategy" is to drink some poison ahead of time and bring an even stronger poison.

The Conventional Strategy is the obvious strategy, and there is scant need to explain why a Servant might employ it; the Servant might not be able to think of anything else to do. We have seen a motivation for the Weak Poison Strategy; it wins against the Conventional Strategy. But we can go one step further. Suppose one of the Servants becomes convinced that the other Servant is going to employ the Weak Poison Strategy. Then neither the Conventional Strategy nor the Weak Poison Strategy will do. On the other hand, the Water Strategy will defeat the Weak Poison Strategy. Therefore, given that there exists an incentive to employ the Weak Poison Strategy, there is also an incentive to employ the Water Strategy.

This line of reasoning can be taken even further.

Suppose one of the Servants gets as far as recognizing that the Water Strategy is a viable alternative, and becomes convinced that the other Servant will employ it. What to do? All three strategies mentioned so far fail against the Water Strategy; if both players employ the Water Strategy, they will both survive the drinking ordeal, but when this happens, the King will know that at least one of them cheated and will execute them both. The Double Dose Strategy is the only way to defeat the Water Strategy (and it has the additional merit that it also wins if my opponent employs the Conventional Strategy or the Weak Poison Strategy and my opponent's poison is weaker than the poison I ingest in advance). So there is good reason to consider employing the Double Dose Strategy.

Given that all these possibilities are on the table, we can see three alternative ways that both Servants could die of poisoning.

One Servant employs the Conventional Strategy while the other Servant employs the Water Strategy.

One Servant employs the Conventional Strategy while the other Servant employs the Double Dose Strategy, and the strength of the former Servant's poison is in between the strengths of the latter Servant's two poisons.

Both Servants employ the Double Dose Strategy, and each Servant's weaker poison is weaker than the opponent's stronger poison.

Other possibilities can be ruled out by some clause in the problem statement.

For example, suppose that one Servant employs the Conventional Strategy while the other Servant employs the Weak Poison Strategy, but the "weak" poison turns out to be stronger than the "conventional" poison. This would indeed lead to both players dying, but there is no plausible reason why a Conventional Strategist would intentionally bring a weak poison, and we know that both Servants possess potent poisons.

I find it rather fascinating that all these unexpected possibilities arise naturally from the innocuous-looking problem statement. As for why I added the game-theory tag,

one can imagine assigning a payoff of 1 for surviving and 0 for dying (either of poison or by execution for cheating), and assigning different probabilities for possessing the strongest poison, and calculating what probabilistic mixture of the four possible strategies yields a Nash equilibrium. I have not worked out the details, but I suspect they could yield further surprises in this already rich puzzle.

EDIT (April 2024): I have now written a paper on this puzzle, Cooking Poisons: Thinking Laterally with Game Theory (arXiv:2404.05053), which will be published in Mathematics Magazine.

• It seems worthwhile to mention that in the DD strategy starting with the second strongest potion is always best. This also makes the 2x2posions discussion in your paper a bit skewed (if that is the right word). In addition, only C and DD are obeying the already somewhat distrusting king, the others may still mean death if the king somehow finds out the winning poison was not the strongest one. Apr 9 at 18:47
• @Retudin I'm not sure exactly what you mean that "starting with the second strongest potion is always best." If you just mean that of the two poisons I ingest, I should ingest the weaker of the two first, then yes. But if you mean it's always best for me to choose the two strongest poisons in my entire arsenal, I'm not sure that's always best. If my opponent drinks a weak poison in advance and brings water (Strategy A in my paper), then I can survive only if both of my poisons are weaker than my opponent's poison. Else, neither of us will die of poisoning and the King will execute us both. Apr 9 at 22:25
• OK, I stand corrected. I sort of assumed one could convince the King to repeat the experiment (with neither leaving) to prove the other is cheating, but indeed it says both will be killed if one is cheating; no second chance. Apr 10 at 5:49

A possible solution is:

one of the poisons was not poisonous but this would not make sense because then the person who brought it would know they would die

And so my second answer is:

the smart would have drunk their weakest poison before hand and taken a poison that would not be poisonous so their opponent would die. But if they both used this strategy they would both die.

And so my next two answers are:

if A brought their strongest poison and it was weaker than B's weakest poison. And B's drunk their weakest poison beforehand and brought poison that was not poisonous both A and B would die. The last solution is the same but a and b are swaped (The Royal Physician is a rather than b)

One last point:

the first solution does not seem conclusive so their may be one answer I have missed

• Your second answer is correct! But I would argue that your next two answers are ruled out because "Each has had some experience with the other's poisons and knows that some of them are quite potent." May 10, 2023 at 13:31

I imagine the intended solution was:

They both drink their own weakest poison in the hour before meeting the King, and they both bring water rather than poison (not realising that the other will do the same).

Another option:

Neither of them actually wanted the other one to die any more than they wanted to die themselves, and they realised / hoped (Prisoner's Dilemma style) that both of them would hit on the idea of bringing water in which case they would both be safe. However, one of them did not wash her poison bottle out very well before putting water in it, so there was enough poison left to kill them both.

• You're right about the intended solution. But notice that the King said, "If I detect any attempt to circumvent these rules you will both be executed." So there's no possibility that "they would both be safe." May 10, 2023 at 13:29