Martyr to the cause of attractive consumer electronics.
Tuesday, November 27, 2012
Monday, November 5, 2012
Labyrinth Puzzle
I was thinking the other day about that Labyrinth puzzle... that scene where Sarah runs into a pair of muppet-like creatures guarding two doors. The premise, according to one of the creatures, is that one of the guards always tells the truth, and one always lies. And if Sarah chooses the correct door, she gets a cheesecake, and if she chooses the wrong door, she dies. So all she needs to do, presumably, is figure out which guard is telling the truth, and ask him which door to take. So I was thinking, what is the best approach to this situation? Here's one approach which I thought of: Ask second guard whether he agrees with the first guard, specifically that one guard always tells the truth and the other always lies. His possible answers are:
1) Yes, one tells the truth and one lies
2) No, they both always lie
3) No, they both always tell the truth
4) No, one sometimes tells the truth and the other always lies
5) No, one sometimes tells the truth and the other always tells the truth
6) No, they both sometimes tell the truth
If he answers 1), we know they are both lying. The reason is that if the statement "one tells lies one tells truth" were true, one guard would necessarily contradict the other. So this means either that both guards always lie (case 2), one guard always lies and the other only sometimes lies (case 4), or that they both sometimes lie (case 6). If the second guard answers 2) he must be lying. The reason is that if it were true, the second guard couldn't say it because he must lie. So this means one of two things: the second guard always lies and the first guard sometimes or always tells the truth; or, the second guard sometimes lies, which means the first guard must sometimes or always lie (since the first guard just said that "one always lies and one always tells the truth."). If the second guard answers 3) he must also be lying. The reason is that if it were true, the first guard couldn't contradict him. So in this situation we draw the same conclusion as if he had answered 2). If the second guard had answered 4) he could be lying or telling the truth. If he's telling the truth, we know that the first guard always lies, since the second one isn't lying (by assumption). Or, if the second guard is lying, the situation is consistent with 1)---which means the first guard always tells the truth and the second always lies---2), 5)---which means that the first guard always tells the truth and the second sometimes tells the truth---and 6). If the second guard says 5), he can again be telling the truth or lying. If he is telling the truth, then he always tells the truth since we know that the first guard at least sometimes lies because he contradicts the second guard. If the second guard is lying, the situation is consistent with 1)---in which case the first guard always tells the truth and the second always lies---2), 4) or 6). If the second guard answers 6), he could be telling the truth or lying, and if the latter the situation is consistent with 1)---in which case he always lies---2), 4), or 5)---in which case the first guard always tells the truth. Let's summarize these results in a table with ordered pairs (,), the first entry of the pair refers to the first guard and the second entry to the second guard. T means he always tells the truth, L means he always lies, and U means you can't trust him either way. So depending on how the second guard answers the question, we have the following possibilities:
1) (L,L) or (U,L) or (L,U) or (U,U)
2) (T,L) or (U,L) or (L,U) or (U,U)
3) (T,L) or (U,L) or (L,U) or (U,U)
4) (L,T) or (T,L) or (L,L) or (T,U) or (U,U)
5) (U,T) or (T,L) or (L,L) or (U,L) or (L,U) or (U,U)
6) (T,L) or (L,L) or (L,U) or (U,L) or (T,U) or (U,U)
So actually we made a lot of progress: Out of the 9 possible combinations of trustworthiness between the two guards, we have eliminated all but 4 or, at worst, 6 scenarios.The problem is that in all cases, it's possible that both guards sometimes lie. I don't see question you could ask to eliminate this possibility. So the upshot is that you can't trust anything either one of them can says as true or false. So you might as well ignore them and pick a door.
1) Yes, one tells the truth and one lies
2) No, they both always lie
3) No, they both always tell the truth
4) No, one sometimes tells the truth and the other always lies
5) No, one sometimes tells the truth and the other always tells the truth
6) No, they both sometimes tell the truth
If he answers 1), we know they are both lying. The reason is that if the statement "one tells lies one tells truth" were true, one guard would necessarily contradict the other. So this means either that both guards always lie (case 2), one guard always lies and the other only sometimes lies (case 4), or that they both sometimes lie (case 6). If the second guard answers 2) he must be lying. The reason is that if it were true, the second guard couldn't say it because he must lie. So this means one of two things: the second guard always lies and the first guard sometimes or always tells the truth; or, the second guard sometimes lies, which means the first guard must sometimes or always lie (since the first guard just said that "one always lies and one always tells the truth."). If the second guard answers 3) he must also be lying. The reason is that if it were true, the first guard couldn't contradict him. So in this situation we draw the same conclusion as if he had answered 2). If the second guard had answered 4) he could be lying or telling the truth. If he's telling the truth, we know that the first guard always lies, since the second one isn't lying (by assumption). Or, if the second guard is lying, the situation is consistent with 1)---which means the first guard always tells the truth and the second always lies---2), 5)---which means that the first guard always tells the truth and the second sometimes tells the truth---and 6). If the second guard says 5), he can again be telling the truth or lying. If he is telling the truth, then he always tells the truth since we know that the first guard at least sometimes lies because he contradicts the second guard. If the second guard is lying, the situation is consistent with 1)---in which case the first guard always tells the truth and the second always lies---2), 4) or 6). If the second guard answers 6), he could be telling the truth or lying, and if the latter the situation is consistent with 1)---in which case he always lies---2), 4), or 5)---in which case the first guard always tells the truth. Let's summarize these results in a table with ordered pairs (,), the first entry of the pair refers to the first guard and the second entry to the second guard. T means he always tells the truth, L means he always lies, and U means you can't trust him either way. So depending on how the second guard answers the question, we have the following possibilities:
1) (L,L) or (U,L) or (L,U) or (U,U)
2) (T,L) or (U,L) or (L,U) or (U,U)
3) (T,L) or (U,L) or (L,U) or (U,U)
4) (L,T) or (T,L) or (L,L) or (T,U) or (U,U)
5) (U,T) or (T,L) or (L,L) or (U,L) or (L,U) or (U,U)
6) (T,L) or (L,L) or (L,U) or (U,L) or (T,U) or (U,U)
So actually we made a lot of progress: Out of the 9 possible combinations of trustworthiness between the two guards, we have eliminated all but 4 or, at worst, 6 scenarios.The problem is that in all cases, it's possible that both guards sometimes lie. I don't see question you could ask to eliminate this possibility. So the upshot is that you can't trust anything either one of them can says as true or false. So you might as well ignore them and pick a door.
Subscribe to:
Posts (Atom)
