Results 1 to 6 of 6

Math Help - Each inhabitant of a remote village always tells the truth ...

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by smkxn View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614
    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 (T).

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


    Suppose he asked a Liar (L).

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

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


    Either way, we'd get the correct answer.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2010
    Posts
    5
    Ok I get it now, thanks guys.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Remote island with a happy tribe
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 30th 2010, 10:15 PM
  2. A Village Problem
    Posted in the Math Puzzles Forum
    Replies: 2
    Last Post: November 30th 2009, 11:21 AM
  3. what the slope tells us
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 6th 2009, 11:08 AM
  4. Truth value of the statement
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 30th 2008, 07:59 AM
  5. truth tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2006, 06:47 AM

Search Tags


/mathhelpforum @mathhelpforum