Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Each inhabitant of a remote village always tells the truth or always lies. A villager will give only 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?

I understand the textbook answer; which is:

“If I were to ask you whether the right branch leads to the ruins, would you answer yes?”

But my question is if this answer is equally valid:

"Do either of these roads from this fork in the road lead to the ruins?"

Now the reasoning I have is that we know that one of the roads in the fork leads to the ruins. The villager, if he is a liar, will say no. (lie). If he is honest, he will say yes.

Is this sound?

share|improve this question
3  
That will tell you whether he’s a liar or not, but it won’t tell you which fork to take. –  Brian M. Scott Feb 21 '13 at 18:31
    
Right, which means I would have to ask another question: "Which way are the ruins?". Which means that I was not able to solve this problem with one question. Got it, thanks! How do I close this or give you an upvote? –  Chase Feb 21 '13 at 18:36
    
Hang on a moment, and I’ll convert my comment to an answer. (You won’t be able to upvote, since that takes a little more reputation, but you’ll be able to accept it, if you wish, by clicking on the checkmark that appears beside it.) –  Brian M. Scott Feb 21 '13 at 18:37
    
For the record: a question about the same problem is math.stackexchange.com/q/179968/11994. –  Marnix Klooster Dec 30 '13 at 9:44

2 Answers 2

up vote 2 down vote accepted

That will tell you whether he’s a liar or not, but you’ll need a second question to determine which fork to take. The textbook answer tells you the right fork, but you’d need a second question to determine whether your informant is a liar. There’s no way to get both pieces of information from a single yes/no question.

share|improve this answer
1  
@Chase: this is often a useful way to think about these puzzles-you need one bit of data (which road) and can only ask one question. You can't afford to learn whether he is a truth-teller or liar-that would spend your bit. You need a question that truth tellers and liars answer the same way. –  Ross Millikan Feb 21 '13 at 18:49
    
Btw, thank you again for helping me! Logic puzzles have always been difficult for me, so trying to understand them bit by bit has helped me really appreciate them. :) –  Chase Feb 21 '13 at 19:12
1  
@Chase: You’re very welcome. In my experience they can be frustrating at times, but they’re still fun. –  Brian M. Scott Feb 21 '13 at 19:14

Oh it is a very nice, old, and mind blowing puzzle :)

The key to solve this puzzle, that is actually missed in this formulation (it's always had been asked in this formulation), the key is that both of the villagers knows each other! thus each of them knows who is the lair and who is not.

After this, the tricky part is to formulate the question, and the right question to ask is:

If I will ask you neighbor, what is the road that leads to the ruins, what he will answer?

Thus if you where asked the lair, he will tell you for sure into the jungle way. While if you where asked the honest one, he will tell you the way into jungle too! (because he knows that his neighbor is lair!)

So despite of the person you will ask, you will simply need to take the opposite to the answer you have been told!

Very tricky :D

P.S: Can you please tell me where you read about this puzzle? because I have been asked to solve it a long time ago and never faced it again.

share|improve this answer
    
It's from chapter 1.2 (in the exercise section) of Discrete Mathematics and It's Applications, 7th edition by Kenneth H. Rosen. I'm sure you can find a .pdf from someone who is generous online, or from the more notorious Bays of the internet. (tell me if I am crossing the line here) :P –  Chase Feb 21 '13 at 19:09
1  
@Chase: thx, I have that book. by the way, just due to curiosity, I'm pretty sure I gave you the answer, why you considered Scott's "that there is no solution" as an answer? –  TMS Feb 21 '13 at 19:28
    
Well my exact question was not about the textbook answer. My question was "Why can't I just ask the villager if one of the roads leads to the ruins?". That would only tell me if the villager is a liar or not, but not which way the ruins are. Brian M. Scott was the first one to point that out to me, but he pointed it out in the comments first, so I gave him the green check. You explained the textbook answer perfectly, but I had already understood it myself. It was my ineptitude that made me forget why my answer was not as good as the textbook answer, so sorry. :( –  Chase Feb 21 '13 at 19:35
1  
Oh I see, it's ok. –  TMS Feb 21 '13 at 19:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.