Two Guards, One Question: Finding the Door to the Offer
You have reached the final round of an interview and are shown two closed doors. Behind one is the room where you receive the job offer; behind the other is the exit. Each door has a guard standing in front of it. One guard always tells the truth and the other always lies, but you do not know which guard is which, and you do not know which door is which.
You are allowed to ask exactly one yes-or-no question to exactly one of the guards. What question do you ask, and how do you use the answer to choose the offer door?
Hints
- A direct question such as "Is your door the offer door?" fails because you cannot tell whether you are hearing the truth or a lie.
- Make the answer pass through both guards. If the truth-teller reports what the liar would say, or the liar reports what the truth-teller would say, one lie is always applied.
- Ask either guard: "Would the other guard say that your door leads to the offer?" Exactly one inversion happens in every case, so the answer is always the opposite of the truth: answer yes means take the other door.
Worked Solution
How to Think About It: With one guard you get an answer whose reliability you do not know. The fix is to design the question so that the answer's reliability becomes known regardless of whom you asked. If the question forces both guards' behaviours into the answer, the unknown "truth or lie" becomes a known "exactly one lie".
Approach: Build a self-referential question, enumerate the four cases, and read off a decision rule.
Formal Solution:
*Step 1 -- The question.* Pick either guard and ask: "Would the other guard say that the door you are guarding leads to the offer?"
*Step 2 -- Case analysis.* Let $D$ be the door of the guard you asked, and let the proposition $F$ be "$D$ leads to the offer."
- You asked the truth-teller. The other guard is the liar, who would answer the opposite of $F$. The truth-teller reports this honestly, so you hear $\neg F$.
- You asked the liar. The other guard is the truth-teller, who would answer $F$. The liar reports the opposite, so you hear $\neg F$.
In both cases the answer you hear is $\neg F$: exactly one negation is applied.
*Step 3 -- Decision rule.* If the answer is "yes", then $\neg F$ is true, so $D$ is the exit and you take the other door. If the answer is "no", then $F$ is true and you walk through $D$.
*Step 4 -- Check all four configurations.* (Truth-teller at the offer door, ask him): $F$ true, answer "no", take his door, correct. (Truth-teller at the offer door, ask the liar at the exit): $F$ false, answer "yes", take the other door, which is the offer, correct. (Truth-teller at the exit, ask him): $F$ false, answer "yes", take the other door, correct. (Truth-teller at the exit, ask the liar at the offer door): $F$ true, answer "no", take his door, correct.
*Step 5 -- An equivalent variant.* "If I asked you whether your door leads to the offer, would you say yes?" also works, with the answer being the truth: the liar lies about his own lie. Either formulation makes the number of inversions known.
Answer: Ask either guard "Would the other guard say that your door leads to the offer?" The reply is always false, so if he says "yes" take the other door and if he says "no" take his door.
Intuition
Neither guard alone is usable because you cannot decode a single unknown-reliability source. But a question that routes through both guards composes the truth function with the lie function, and truth-then-lie or lie-then-truth both equal exactly one negation. The answer is therefore deterministically wrong, which is just as informative as deterministically right. This is the same idea as combining two signals whose product has a known sign even when each sign is unknown, and it shows up whenever you can design a query so that unknown biases cancel.