lotus

previous page: 345 logic/smullyan/black.hat.p
  
page up: Puzzles FAQ
  
next page: 347 logic/smullyan/fork.two.men.p

346 logic/smullyan/fork.three.men.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

346 logic/smullyan/fork.three.men.p


Three men stand at a fork in the road. One fork leads to Someplaceorother;
the other fork leads to Nowheresville. One of these people always answers
the truth to any yes/no question which is asked of him. The other always
lies when asked any yes/no question. The third person randomly lies and
tells the truth. Each man is known to the others, but not to you.
What is the least number of yes/no questions you can ask of these men and
pick the road to Someplaceorother? Does the answer change if the third
man randomly answers?

logic/smullyan/fork.three.men.s

One question, and you only need one man of any type:
"If I were to ask you whether the left fork leads to Someplaceorother,
and you chose to answer that question with the same degree of truth as
you answer this question, would you then answer 'yes'?"

The truthteller will say "yes" if the left fork leads to Someplaceorother,
and "no" otherwise. The liar will answer the same, since he will lie about
where the left fork leads, and he will lie about lying. The randomizer
may either lie or tell the truth about this one question, but either way
he is behaving like either the truthteller or the liar and thus must
correctly report the road to Someplaceorother.

If however the third person randomly answers yes or no it is clear that
you must ask at least two questions, since you might be asking the
first one of the randomizer and there is nothing you can tell from his
answers.

Start by asking A "Is B more likely to tell the truth than C?"

If he answers "yes", then:
If A is truthteller, B is randomizer, C is liar.
If A is liar, B is randomizer, C is truthteller.
If A is randomizer, C is truthteller or liar.

If he answers "no", then:
If A is truthteller, B is liar, C is randomizer.
If A is liar, B is truthteller, C is randomizer.
If A is randomizer, B is truthteller or liar.

In either case, we now know somebody (C or B, respectively) who is
either a truthteller or liar. Now, use the technique for finding
information from a truthteller/liar, viz., you ask him the following
question: "If I were to ask you if the left fork leads to
Someplaceorother, would you say 'yes'?"

If the answer is "yes", take the left fork, if "no" take the right fork.

 

Continue to:













TOP
previous page: 345 logic/smullyan/black.hat.p
  
page up: Puzzles FAQ
  
next page: 347 logic/smullyan/fork.two.men.p