You are lost in the forest with eight campers, two of whom sometimes lie; how do you find the one path of...

logic/lost.in.woods New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

You are lost in the forest with eight campers, two of whom sometimes lie;
how do you find the one path of four that leads back to camp?

You are a counsellor [Editor: "councellor" in the original] at a summer
camp, out on a nature hike with eight young campers.  You get lost in
the forest and wander around aimlessly [Editor: "aimplessly" in the
original] for hours.  Suddenly you come to a clearing, and find yourself at a
four-way intersection.  A broken sign lies on the ground, stating that
the camp is one mile away, but it is impossible for you to tell which
direction the sign had been pointing.  As it is now one hour before
nightfall, and travelling in the dark is dangerous, you decide on the
following plan:

You split-up into groups and each group explores one path (remember, there are
four unknown paths, since you didn't walk down one of them to the
intersection.)  Each group will walk one mile down the path (which will
take 20 minutes -- the campers are slow), note what they find, and then
walk back.  At that point, with 20 minutes left until nightfall, you ask
each group what they found, and based on their replies you select one
path.  The last 20 minutes, hopefully, will be spent walking to the
camp.

There is just one teensy-weensy problem.  Two of the campers sometimes
lie.  Not always, just sometimes.  There's one more teensy-weensy
problem.  You don't know which ones.

How do you break-up into groups, and how do you make your decision based
on the results?

[ Editor: Posted by Walter Prager <wprager@Newbridge.COM>, from The
  Puzzling Adventures of Dr. Ecco by Dennis Shasha (spelled "Sasha" in
  the original posting). ]

Show solution

I assume that I can also explore the terrain.
I split into 2 groups of three, one group of two, and myself as 4th
group.  These groups are sent as described and I ask everybody what he
saw afterwards.
If my path was correct --> we go this way.
If in a group of three all say the same, they all speak truth
[Editor: "thruth" in the original].  So if this happens for both groups
of three, I know the correct answer to the question "Leads this way to
the camp" for three directions and I can decide where to go.  If both
groups of three are in itself contradicting, there must be exactly one
liar in every group of three.  Hence the majority [Editor: "mayority" in
the original] in each group of three speaks the truth and again I know 3
correct answers to the above question and I can deduce the 4th answer
and therefore decide where to go (same as above).
So we have one [Editor: "on" in the original] group of three where
everybody says the same (and therefore the truth [Editor: "thruth" in
the original]) and one group of three where there are contradictions.
If the truth speaking group of three says "we found the way to the
camp" we go that way.  Else the correct way must be either the way of
the contradicting group of three or of the group of two.  If the group
of two is in itself contradicting then there is one liar in that group
and one in the contradicting group of three.  Hence the majority in the
group of three says the truth and again I know three correct answers
for three ways.  If (last case!) the group of two has in itself no
contradictions they cannot both speak false since we have only 2 liars
and at least one is in the contradicting group of three.  So we know
that the group of two speaks truth and we again know 3 correct answers.
In either case we found the way out.
I hope my reasoning is (somewhat) understandable.

-- Ingo Warnke <nfa031@hp1.uni-rostock.de>

I take one path, and send the others out in two groups of three and one
group of two.  If all three groups come back and say they didn't find
the camp (assuming I didn't also), I know that I put the two liars
together, and that they did indeed find the camp.

-- Phil Sandler <fibby@MCS.COM>