10
$\begingroup$

In the spirit of some of my Raymond Smullyan favorites, here's a relatively hard puzzle from a Dennis Shasha collection of $1988$:

Eight kids and their guide are lost on a forest exactly one hour before night falls. They are on a glade from which four paths leave. The guide knows that one of the paths leads to the camp site in exactly $20$ minutes but doesn't know which one.
enter image description here
The guide thinks that the best solution to find the right path is send small groups of campers (where he could include himself) for $20$ minutes, then the groups turn back to the glade, share what they found with the others and finally, thanks to that information, they pick the right path and use the last $20$ minutes before night falls to reach the camp site.
It could be an easy foolproof plan, but the guide also knows that two of the eight kids (not which ones) like to tell lies one in a while.

How should the guide divide the groups to find the right path using this plan?

EXTENDING THE PROBLEM:

Since I didn't do my homework correctly (I didn't search properly for a duplicate problem - here), I decided to investigate a little variant so we don't waste this space on Puzzling. Here it goes:

When the guide was ready to send the groups on their mission, he realized that the two possible liars were on the morning group. The group he was dealing with had three compulsive liars (they always lie) and two of them always walk together. Besides that, Martin, the youngest one, has to be part of a group of at least four people.

How should the guide divide the groups now?

$\endgroup$
5
  • $\begingroup$ "the guide also knows that two of the eight kids like to tell lies one in a while." Does the guide know WHICH two kids? $\endgroup$
    – FlanMan
    Aug 10, 2020 at 11:36
  • $\begingroup$ @FlanMan, no. Added to the problem already :) $\endgroup$
    – Pspl
    Aug 10, 2020 at 11:46
  • $\begingroup$ Is Martin one of the compulsive liars? (i.e. does "the youngest one" refer to the youngest of the compulsive liars or the youngest of the whole group?) $\endgroup$ Aug 10, 2020 at 20:42
  • $\begingroup$ @JaapScherphuis, he may be. The guide doesn't know... He's simply the youngest of the whole group. $\endgroup$
    – Pspl
    Aug 10, 2020 at 22:41
  • $\begingroup$ For what it's worth, this variant in my opinion reads much better than duplicate. $\endgroup$ Aug 11, 2020 at 2:53

3 Answers 3

10
$\begingroup$

Here is my answer for the new version of problem.

Split the kids in groups of sizes:

4, 3, 1, with the guide taking the fourth path.

When the kids report back, there are the following possible outcomes.

A group may be unanimous, or split into two subgroups that give opposite answers. Here is a table of all possible ways the groups can split, and the unique arrangement of the liars in those groups:

 Group splits    Liars
 4    3    1   : 0/3/0
 4    1+2  1   : 0/2/1
 1+3  3    1   : 3/0/0
 1+3  1+2  1   : 1/2/0 (1/1/1 is not possible)
 2+2  3    1   : 2/0/1
 2+2  1+2  1   : 2/1/0
The only tricky case is the 1+3 / 1+2 / 1 split, where the 1/1/1 arrangement of liars is not possible since you know that two of the liars will always be together in the same group.

If the group of size 4 splits as 2+2, then you don't know which pair are the liars. This does not matter however, as you have uniquely identified the liars in the other groups and so know what the real answer is for three of the roads, and the real answer for the fourth road can then be deduced.


NOTE: The answer below was for the original problem, which turned out to be a duplicate.


Split the group as follows:

One path is taken by the guide. The kids are split into two groups of 3, and one group of 2, and they go down the other three paths.

To recover the correct information from the kids' reports:

Let's call a group of kids inconsistent if they don't all give the same answers. Clearly an inconsistent group contains at least one liar.

If there are no inconsistent groups, then the two groups of three kids (and the guide) must be telling the truth. So three correct reports are known and the correct path can be deduced, possibly by elimination.

If there is one inconsistent group, then the other two groups (and the guide) must be telling the truth. Again you have three correct reports and the correct path can be deduced.

If there are two inconsistent groups, then they must each contain one liar. At least one of the inconsistent groups has 3 kids, so the majority result of those kids must be the correct one. Again you now have 3 correct reports, and can deduce the correct path.

$\endgroup$
2
  • $\begingroup$ Wow. You really did it... I was afraid I was turning the problem too much hard and tricky, but apparently, I was wrong :D $\endgroup$
    – Pspl
    Aug 11, 2020 at 7:13
  • $\begingroup$ Actually the difficulty is not so much to find a solution as it is to find one that minimizes the number of cases to consider. And you did a good job on that. $\endgroup$
    – Florian F
    Aug 11, 2020 at 16:36
2
$\begingroup$

The guide knows that two kids can lie.

He divides the team in 3 groups of 3 people and explores 3 paths. This way, 7 people will always give correct info and 2 will/could lie. So when the groups come back from the "scouting" they'll give the feedback of what they found.

There are some occasions:

A group of 3 people, no liars -> Unanimous info

A group of 3 people, 1 liar -> 2 vs 1 info

A group of 3 people ,2 liars -> 1 vs 2 info

Now you just have to spot which groups have divergence of opinions and you'll spot who are the liars.

If the liars were split into different groups, you'll have 2 groups with 2 vs 1 info. And if that's the case then it's easy to exclude the liar's opinion. If this happens, then you know that at least one group is telling the truth and you extract the truth from the 2 "liars" group. If the liars are in the same group, you'll have only one case of 1 vs 2 info, then you know that the correct info is the one contrary to the liars. If this happens, then you know that the other two groups are telling the truth and you extract the truth from this "liar" group.

Now, finally

If after getting the feedback the guide comes to the conclusion that nobody found the way back to the campsite, then the path to take is the path that was not previously explored.

$\endgroup$
6
  • 1
    $\begingroup$ What if only one liar lied? $\endgroup$
    – msh210
    Aug 10, 2020 at 12:07
  • $\begingroup$ This won't work. If the right path is the unexplored one and in a group of three kids are different answers, the guide can't conclude the right path. Sorry :( $\endgroup$
    – Pspl
    Aug 10, 2020 at 12:10
  • $\begingroup$ I'm assuming they are lying. Plus, you'll always have one group that is telling the truth. If you have a 3 groups with 3 people and 2 liars, at least one group is telling the truth and has a unanimous opinion. Now you have two different cases. One group with 2 liars or one group with one liar and two groups with one liar each. Now if you have two groups telling the truth then you know that the lying group has two liars and so you take info least popular of the group (1 kid vs 2 liars). If you have two groups with mixed info, you take the info that has the majority (2 kids vs 1 liar) $\endgroup$
    – Uba
    Aug 10, 2020 at 12:20
  • $\begingroup$ I may be missing a point or so, but if they are guaranteed to lie, I think its possible $\endgroup$
    – Uba
    Aug 10, 2020 at 12:21
  • $\begingroup$ If only one liar lied, then it's the same process but even simpler. $\endgroup$
    – Uba
    Aug 10, 2020 at 12:27
1
$\begingroup$

The guide will split the groups as such:

3 campers, 3 campers, 2 campers, the guide

He then sends out the groups down each of the four paths, and when they return he has the following possibilities:

Path 1 and Path 2 with 3 campers each, if all three campers agree you know they are all telling the truth since there are only two liars.
If there is a disagreement, you know that group has at least 1 liar.
Path 3 with the group of 2, if there is a disagreement you know that group has at least 1 liar. If they are in agreement they can be both liars
Path 4, the guide knows he will tell the truth

Worst case scenario:

Both liars are in one of the groups of 3, and the correct path is either their path or the path with only two students. However, since there is a disagreement the guide knows that at least 1 liar is in the group of three, so both campers in the group of 2 can't be lying. That means if the group of 2 both say the same thing they must both be telling the truth.
The guide won't know if there are two or only one liars in the group of 3, but by using the fact that he knows all three other groups are telling the truth, he can determine the correct path.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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