There are 2 doors—talking doors—in a room in which you are a prisoner. You must choose and then pass through one of the doors. One leads to your immediate freedom, and the other leads to your doom, but you don't know which is which (but they do). Further, one of the doors always lies, and the other always tells the truth. And you don't know which is which (but they do).
You may ask only one question of only one of the doors. What question do you ask?
For example, you could ask one of the doors, "Are you the door that leads to my freedom?" If the liar door guards the route to your freedom, the response will be no. If the honest door is the freedom door, the response will be yes.
|"Are you the door that leads to my freedom?"|
But of course since you don't know which door is which, even imagining asking more than one question is not helpful. And you can only ask one question.
There are some different ways to think about this problem, but I thought I'd apply a mathematical lens—not really to make the solution any clearer, but to show at least that such a lens can be applied.
We Have to Get Rid of the Questions
We can't really deal with "questions" mathematically. So, we have to change them to statements. Instead of, "Are you the door that leads to my freedom?" we can make the statement (to one door), "You are the door that leads to my freedom." And instead of responding with yes or no, we can imagine that the door will respond with true or false. The table below is the same as the one above, except the responses are changed.
|"You are the door that leads to my freedom."|
If we made the opposite statement, "You are the door that leads to my doom," the responses in each column would simply trade places. So, we can generalize from this: no matter which fate the liar door guards, a true statement given to that door would produce a false response, and a false statement would produce a true response. If our statement were x, then the liar door would return L(x) = -x. If the statement were -x (false), the door would return -(-x), or x.
For the honest door, a true statement would produce a true response, and a false statement a false response. Again, if our statement were x, then the honest door would always return H(x) = x. If our statement were -x, the door would return -x.
At the right, the liar's line, L(x) = -x, runs from top left to bottom right. The honest door's line, H(x) = x, runs from bottom left to top right.
Although we're not much closer to a solution, the mathematical formulation provides some clarity. It shows, for example, that no matter what question we ask, responses of the form H(x) = x and L(x) = -x will always be equal but opposite answers. So we want to get a response in a different form, but we still can use only one x—just one input from us.
And that's when function composition can come to the rescue. The rest of the story is just filling in the details! Can you fill them in?
P.S.: This is a rewrite of this but without the code.