Thread: Each inhabitant of a remote village always tells the truth ...

There is this exercise in the "Discreet Mathematics" book I'm reading for my computer science course, which is leaving me scratching my head.

This one question goes like this: "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 deeper 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?"

The answer is apparently: "If I were to ask you whether the right branch leads to the ruins, would you answer yes?"


I don't quite understand why this question would reveal the correct branch to you. Can someone clear that up for me?

Originally Posted by smkxn

There is this exercise in the "Discreet Mathematics" book I'm reading for my computer science course, which is leaving me scratching my head.

This one question goes like this: "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 deeper 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?"

The answer is apparently: "If I were to ask you whether the right branch leads to the ruins, would you answer yes?"


I don't quite understand why this question would reveal the correct branch to you. Can someone clear that up for me?

For the sake of simplicity suppose the left branch leads to the ruins whereas the right one leads you lost deep into the jungle.

Case 1. The villager is a liar: in this case, since he knows the right branch leads to the jungle then he'd say it leads to the ruins, but he won't tell you NOW this, so his answer here is NO.

Case 2. The villager tells the truth: he will answer NO again, 'cause he knows the right branch takes you to the jungle and he will let you k now that.

From the above, it's clear you must choose THE other branch if the answer is NO...

Tonio

Hello everyone

The alternative answer, of course, is that the tourist asks the question "Did you know they're giving away free beer at the ruins today?" He then hides behind a bush, watches which way the villager goes, and then follows him to the ruins.

Grandad

Hello, smkxn!

This is a classic problem
and there is a variety of questions that could be asked.

The answer is apparently: "If I were to ask you whether the right branch
leads to the ruins, would you answer 'Yes'?"

Suppose he asked a Truthteller

always tells the truth.
So we can depend on his answer.


Suppose he asked a Liar

If were asked if the right branch is correct,
. . woulld lie and give the wrong answer.

But would lie about this . . . and give the correct answer.


Either way, we'd get the correct answer.

Hi smkxn,

there are two possibilities.
If i ask the villager which road leads to the ruins
and i do not know whether it is a lying villager or truthful villager,
then i cannot tell if i get a true answer or not.

i will get a dependable answer, i just can't depend on which type
of villager i'm asking.

Hence i ask effectively 2 questions at once, in a single question.

Instead of asking "Does the right branch lead to the ruins?"
which will leave me with only a single answer,

i ask "If i take the right branch, would you say it will lead me to the ruins?"

(The question can also be phrased with the left branch.)

If the answer is yes, then the truthful villager points it out as the correct way, or the lying villager lies because the answer he would have given
to the question "which road will take me to the village?" would have been the other.

Same logic to the situation if the answer was "no".

There's a lot to be said for Grandad's suggestion too.

Ok I get it now, thanks guys.