3

This question is given in discrete mathematics by Kenneth Rosen. Each inhabitant of a remote village always tells the truth or always lies. A villager will only give a "yes " or a "No" response to a question a tourist asks. Suppose you are a tourist visiting this area and come to a fork in the road. One branch leads to the ruins you want to visit ;the other branch leads deep into the jungle .A villager is standing at the fork in the road.what one question can you ask the villager to determine which branch to take .

so the answer to this question is given "if i were to ask you whether the right branch leads to the ruins would you answer yes?" , what i can't understand that if the villager were a liar he'd say "no" even if the road might lead the tourist to the ruins so how does this question provide a solution to the problem?

Learner
  • 13
srishti77714
  • 31

5 Answers5

5

If you ask a liar a question the answer will be lie.

If you ask a liar what his answer will be, he will lie about his answer being a lie and he will say that his answer is the truth.

So if the path leads to ruins and you ask if the path leads to ruins he will lie and say "no". If you ask him if he will answer "yes" he will lie and answer.... "yes".

....

To get the truth out of a liar ask him "What would you say if I asked you..." the liar will lie about lying and give the true answer....[1]

[1](assuming the question was binary yes/no... otherwise he could give a second lie; the lie he *wouldn't give.)

====

Or you could parse it from the top down:

Q: ""if i were to ask you whether the right branch leads to the ruins would you answer yes?"" LIAR: "NO"

That's a lie. He would answer yes.

  • "Does the right branch leads to the ruins" LIAR: "YES"
  • That's a lie. The right branch does not lead to the ruins.
  • Conclusion: The left branch lead to the ruins.

Q: ""if i were to ask you whether the right branch leads to the ruins would you answer yes?"" TRUTHTELLER: "NO"

That's the truth. He would answer no.

  • "Does the right branch leads to the ruins" TRUTHTELLER : "NO"
  • That's the truth. The right branch does not lead to the ruins.
  • Conclusion: The left branch lead to the ruins.

Hence "NO" means left branch.

Q: ""if i were to ask you whether the right branch leads to the ruins would you answer yes?"" LIAR: "YES"

That's a lie. He would answer no.

  • "Does the right branch leads to the ruins" LIAR: "NO"
  • That's a lie. The right branch does lead to the ruins.
  • Conclusion: The right branch lead to the ruins.

Q: ""if i were to ask you whether the right branch leads to the ruins would you answer yes?"" TRUTHTELLER: "YES"

That's the truth. He would answer yes.

  • "Does the right branch leads to the ruins" TRUTHTELLER : "YES"
  • That's the truth. The right branch does lead to the ruins.
  • Conclusion: The right branch lead to the ruins.

Hence "YES" means right branch.

fleablood
  • 124,253
1

You need to differentiate between two different questions:

Q1: Does the right road lead to the ruins?

Q2: Would you say "yes" to question Q1?

If the right road does lead to the ruins, the liar will say "No" to Q1, and therefore say "Yes" to Q2!

Bram28
  • 100,612
  • 6
  • 70
  • 118
0

You have to consider each of the cases separately. First, let us assume that right path leads to the ruins. Then a villager telling the truth would answer "Yes". A lying villager would answer "Yes" as well, since his answer to the question "Does the right path lead to the ruins?" would be "No".

On the other hand, if the right path leads into the jungle, the answer from the villager telling the truth would be "No". The lying villager would also say "No", because his answer to the question "Does the right path lead to the ruins?" would be "Yes".

Thus, in both cases a "Yes" means that the right path leads to the ruins, and a "No" means that the left path leads to the ruins.

René B. Christensen
  • 480
0

If I were in this situation in real life, I will ask them about a different place different from the two in the fork, The truth teller will always say "no". On the other hand the liar will say "yes". For that I can identify whether the person is a truth-teller or not, then I will ask him the direct question. For example, if I am walking in the street and I know one of the branches leads to Ali's house and the other leads to Yasser's house and I seek Ali's house. I would first ask if the right path leads to (some name other than the expected) for example Omar's house which isn't existent. the truth-teller will say "no" while the liar, will say "yes". So I will proceed with the question of interest and determine the result based upon the previous response? I hope this helps!

If something is wrong or ambiguous, correct me.

Abdelrahman Torki
  • 113
0

Since the liar always lies, the only way to extract a truth from a liar is to make him lie a lie, as $\neg (\neg T) = T$.
Let $p$ be the case that the villager tells the truth.
Let $q$ be the case that the right branch leads to the ruins.
We shall prove this by taking cases:

  1. The right branch leads to the ruins. (i.e $q$)
    1.1 If $p$, then the answer will be yes and you are good to go.
    1.2 If $\neg p$, if you had asked the liar a question whether $q$, he would say "No" as he wants to lie. However since you've asked him whether he'll answer "yes", if he were not lying then he would have answered "no" but as he always lies, he will answer $\neg$no$=$yes. Thus, you are good to go.
  2. The left branch leads to the ruins. (i.e $\neg q$)
    1.1 If $p$, then the answer would be "no" and you should thus take the left branch.
    1.2 If $\neg p$ then the answer would be still be "no" as the villager will lie twice.

Thus if the answer is "no", you should always go left, and if it's "yes" then you should go right.

Bingwen
  • 25