On Monday I posted the following puzzle:
“A prisoner is given a choice between two doors; one of which leads to freedom and the other of which leads to certain death. In front of the doors stand three guards, one of whom always tells the truth, one of whom always lies and the other of which answers randomly. The guards will only answer ‘yes’ or ‘no’ to questions. The prisoner does not know which guard is which.
In only two questions, how does the prisoner find out which door is safe?”
The trick to this problem is realising that – even more so than in the case of two guards and one question – you do not have enough questions to find out much of what you might like to know. You can’t find out the natures of all the guards; in fact, you can’t even definitively find out the nature of one of them, not and solve the problems. So what do you do?
Well, there are a number of solutions to this, but all of them involve identifying a guard who is definitely not the inconsistent guard. If we have a guard that always tells the truth or always tells lies, we know how to get through, regardless of whether they are a truth-teller or a liar. The problem reduces to the two guards and one question, along the lines of, “If I asked your exact opposite which door was the door to freedom, what would they say?” (and then going through the other door) will work. So the first question needs to identify such a guard.
This is where my instincts really misled me, when I first tried to solve it. The natural path is to try to identify the inconsistent guard, but it turns out that that’s not the way forward. What you can do, however, is to find a guard who is definitely not inconsistent – and that’s all you need.
I find the most elegant framing is to ask one guard (say Guard A), “Of the other two guards, which one tells the truth more often?”
– If Guard A is the truth-teller, they will point to the inconsistent guard, as that guard tells the truth more than the liar. The guard not pointed at is the liar.
– If Guard A is the liar, they will also point to the inconsistent guard, as that guard tells the truth less than the truth-teller, and the liar always lies. The guard not pointed at is the truth-teller.
– If Guard A is the inconsistent guard, they will point at either of the other two guards – either the truth teller or the liar.
We can therefore see that, in each case, the guard that is not pointed at will be consistent (either the truth-teller or the liar). We have then identified a consistent guard, either the truth-teller or the liar. This is all we need; we can then ask a question as set out above (“If I asked your exact opposite which door was the door to freedom, what would they say?”), go through the opposite door and be free.