Two men stand at a fork in the road.

logic/smullyan/fork.two.men Added material

Problem

Two 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.  By
asking one yes/no question, can you determine the road to
Someplaceorother?  Can you identify which is which?

Show solution

The fact that there are two is a red herring - you only need one of
them.  Ask either of them the question:

"If I ask you if the left fork leads to Someplaceorother,
will you answer 'yes'?"

If the person asked is a truthteller, he will answer "yes" if the left
fork leads to Someplaceorother, and "no" otherwise.  But so will the
liar.  So, either way, go left if the answer is "yes", and right
otherwise.

It is possible, of course, that the liars are malicious, and they will
tell the truth if they figure out that you are trying to trick them.

If you just want to identify which is which, ask either one some
question like "Is one plus one equal to two?"  The truthteller will
answer "yes," and the liar will answer "no," and you can figure out the
identity of the other man by process of elimination.

Additional material

[ Editor: a 1995 thread "LOST IN THE FOREST" asked what question to ask
either a liar who always lies or an honest man who always tells the
truth to be sure of the way out.  It turned to whether such people can
exist. ]

There are no such people, and thus the puzzle setter is lying.

Proof: ask either person the question "Is it the case that you are the
truth-teller if and only if your answer to this question is 'no'?"  The
liar will be unable to lie, and the truth-teller will be unable to tell
the truth.

-- Gareth Rees <gdr11@cl.cam.ac.uk>

Actually, the correct response to this question is "no" for both the
truth-teller and the liar.

The problem here is that the question actually asks permission for the
creation of the contradiction.  If the questionee (ack!) doesn't grant
permission, the contradiction doesn't occur.  A rephrasal of the question
may clear it up:

    May I use your answer to this question to answer the
    question, "Are you a liar?" ?

  or

    May I use your answer to this question to answer Question X?
    (Question X = "Are you a liar?")

If the truth-teller answers 'yes', then he's stuck, because his answer to
"Are you a liar?" is also 'yes', which is untrue.  But if he answers 'no',
then the questioner is not allowed to use his answer for its second purpose,
so the contradiction is averted.

If the liar decides 'no' but lies by answering 'yes', then he's stuck, because
the questioner will take 'yes' to be the answer to "Are you a liar?", which is
true.  However, if the liar decides 'yes' but lies by answering 'no', then his
answer to "Are you a liar?" is also 'no', which is untrue, so he's lied about
everything.  The questioner hears the answer 'no' and thinks the liar has not
given permission, and so is misled.

Q.E.D.

To fix up the question, you need to rephrase it such that the questioner gets
to create the contradiction no matter what the questionee says.  I suggest the
following:

    Is your answer to this question the same as your answer
    to the question, "Are you a liar?" ?

Now, if the truth-teller says 'no', then his answer to "Are you a liar?" is
not 'no', and is thus untrue.  If the liar says 'no', then his answer to "Are
you a liar?" is not 'no', and is thus not untrue.

-- Tom Maciukenas <tom.maciukenas@amd.com>