# Each inhabitant of a remote village always tells the truth ...

• Jan 18th 2010, 06:18 AM
smkxn
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?"

I don't quite understand why this question would reveal the correct branch to you. Can someone clear that up for me?
• Jan 18th 2010, 07:20 AM
tonio
Quote:

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?"

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
• Jan 18th 2010, 07:27 AM
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.

• Jan 18th 2010, 07:41 AM
Soroban
Hello, smkxn!

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

Quote:

The answer is apparently: "If I were to ask you whether the right branch

Suppose he asked a Truthteller \$\displaystyle (T).\$

\$\displaystyle T\$ always tells the truth.
So we can depend on his answer.

Suppose he asked a Liar \$\displaystyle (L).\$

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

Either way, we'd get the correct answer.

• Jan 18th 2010, 08:03 AM
Hi smkxn,

there are two possibilities.
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

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

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.
• Jan 18th 2010, 08:06 AM
smkxn
Ok I get it now, thanks guys.