## 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..

3. The logician is at the tee junction which means he had come thru one road to a point where two more roads fork ahead to the village. Now he is at a point where there are three roads one of which he has come from and knows for sure that road doesn't go to the village. He now needs to find out about the other two roads to reach to the village. The logician asks one simple question to the bystander showing the three roads that :Out of the three roads which are the roads that do not go to the village? If the by stander is a truth-teller he will say the truth showing exactly two roads that don't go to the village including the one the logician as come along and the logician will know he is telling the truth and take the third road to go to the village . And if the bystander is a liar then he'll show only one road which actually goes to the village as the road not going to the village. So the logician knows that there are two roads which don't go to the village as he has come from one road which doesn't go to village so this bystander is a liar and will take the road shown by the bystander to reach the village! Thats how the logician reaches the village!!

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.