Wednesday, March 31, 2010

The Prisoner, the Liar, and the Truth, Part II: Enter the Other Guy

Recall from a couple weeks ago, the door that leads to the electric chair in the Prison for Creative and Unusual Punishment.  It is located in a depressing, windowless basement hallway near the back, right next to an identical door that leads to an unguarded fire exit.

A prisoner with similar lamentable circumstances to the guy in part 1 was being brought in for execution, and the warden wanted to give him one last chance at freedom.  This time, however, would be more complicated.  Rather than two guards, there were three guards with them, named Al, Bob, and Carl.  The warden held a brief huddle with the three guards, out of earshot of the prisoner.  He then told the prisoner some of what went down in the huddle.

"I've instructed one guard to tell nothing but lies when asked a yes-or-no question.  I've instructed another guard to tell only the truth when asked a yes-or-no question.  I then repeated one of those two instructions to the remaining guard.  Unfortunately, I'm not going to tell you whether there are two liars an a truth-teller, or two truth-tellers and a liar.  And I'm certainly not going to tell you which is which.  You have two yes-or-no questions to ask, choosing one guard at a time to respond (no asking a question of the whole crowd).  From the information you glean, you may choose a door.  Best of luck."

Solution:
The wording here is kind of tricky, so bear with me.

Question 1:
It doesn't matter whom you ask the first question, so we will arbitrarily pick Al and ask him the following: "Would Bob say that Carl tells the truth?"

You can use the answer to this question to determine whether you have two liars or two truth-tellers.  No matter whom you ask this type of question, or which guard is which, the meaning of the answers will be the same.  If there are two liars, the answer will be 'yes'.  If there is one liar, the answer will be 'no'.  Try any combination or orientation of liars and truth tellers, this will be true.

Question 2:
Again it doesn't matter whom you ask, but for consistency we will pick Al again and ask him, "Would Bob say that Carl would say the door on the left leads to freedom?"  If there are two liars, they will cancel each other out and the answer will be true.  In this case, you should go through the door on the left.  If there is only one liar, the answer will be false, and you should go through the door on the right.

Explanation
By asking the second question through all three guards, you get an answer that you can know is true or false regardless of the order of the guards being asked.  A lie about a truth and a truth about a lie both end up being false statements.  This is the principle that led the prisoner to freedom in part 1 of this riddle - the prisoner asked guard A what guard B would say about which door leads to freedom.  No matter which guard was the liar - A or B - the answer still came out a lie.

This principle can be equated to multiplying positive and negative numbers.  Just like lie about a true statement is false, a negative (-) times a positive (+) is negative (-).  This property is commutative - the order doesn't matter: (+)*(-) = (-)*(+) = (-).  Furthermore, a lie about a lie is a truth, just like a negative times a negative is a positive.

So when you ask the second question through all three guards, the answer is true if there are two liars, as modeled by the equation (-)*(-)*(+) = (+).  Or the answer is false if there is only one liar: (-)*(+)*(+)=(-).  This is true regardless of order.

1. I think I found a somewhat simpler solution.
Ask Al: Is Bob saying always the truth?
If the answer is No, one of them is a truth teller and the other a liar so we can continue with the question in part I with Al and Bob.
If the answer in Yes, both are liars or truth tellers. So we continue with the question in part I with Al and Carl (or alternatively with Bob and Carl)

swt

2. Couldn't you also ask Al "Do all three of you tell the truth?" If he says no, he's a truthful dude. If he says yes, he's a liar. Then you can ask him which door leads to freedom, and interpret his answer accordingly.

3. ^good catch!!

4. Thank for your sharing good blog comment.

goldenslot
Gclub จีคลับ