## Wednesday, May 26, 2010

A logician vacationing in the Bahamas finds himself on an island inhabited by two proverbial tribes of liars and truth-tellers. Members of one tribe always speak the truth, while other always lie. He stands at the fork of a road (a Tee-junction) and has to ask a bystander which leg he needs to follow to reach the village. He knows not whether the native is a truth-teller or a liar. The logician thinks for a moment and then asks only one question. What does he ask?

1. This comment has been removed by the author.

2. sorry the above explanation is wrong..

4. Another solution, if you are a logician or familiar with computer science, is to use XOR (exclusive OR). XOR is true only if exactly one of the statements is true:

A B A XOR B
1 1 0
1 0 1
0 1 1
0 0 0

If we say that "L" is the proposition "The bystander is a liar", it's nor hard to see that for any question "Q" that can be answered by yes/no, the bystander will answer Q XOR L. (If he is a liar he will answer the negation of Q, otherwise he will answer Q).

The neat thing about XOR is that if we apply the same statement twice, it is equivalent to not applying it at all (that is, A XOR B XOR B = A).

We want to know if one road is the right one R. If it is, we take it. If it isn't we take the opposite one. This is equivalent to R XOR L XOR L, which is precisely the answer we will get if we ask "Is it true that either this is the right road or you are liar?"

=)

5. Ask them which road would someone from the other tribe tell the logician to go down to reach the village.

Then go down the other one.

This works as if a person from the truthful tribe got asked, they would truthfully say the road not to go down as they know that someone from the lying tribe would send the logician down the wrong route.

But if you asked someone from the lying tribe this question, they would know that someone from the other tribe would send the logician down the correct route and then they would lie and say that the logician should go down the wrong route.

So then the logician goes down the route that they don't say and ends up in the village.