# Knights and knaves in Landilandia

You're traveling on a hiking trip in the land of Landilandia when you encounter a forest. The notes in your guidebook tell you that there's a safe route here leading into the woods, but when you approach, you discover that there are actually two paths to choose from. Beside them are three men sitting outside of a tent, engaging in some sort of friendly card game.

The first man looks up as you approach. He immediately hails you, cheerfully saying "Be aware, traveler: if you enter this forest, you take your life into your own hands, for at least one of these paths will lead into peril!"

"Uh, thanks," you say. You look back and forth between the left path and the right one. "I guess this trip might not be as simple as I was hoping."

Then man laughs, then adds with a wink: "And seeing as you're probably hoping to find out which path -- if any! -- might be safe to travel, you should know that one of us is a knave (who always lies), one of us is a knight (who always tells the truth), and one of us is an alternator (who strictly alternates between lying and telling the truth)."

What an odd custom! You had read about people like this in books, but this is your first time meeting any in real life. But you re-check your trustworthy guidebook, and it confirms that this is indeed so: men in this particular region of Landilandia always travel in groups of three: one knave, one knight and one alternator (and naturally they know which of them is which).

However, your guidebook also notes that there are strict social rules on foreign visitors such as yourself interrogating the locals. Asking questions that can't be answered with a "yes" or a "no" is considered a grave insult, and asking too many questions would be tantamount to picking a fight (and you're pretty sure you wouldn't win).

How can you find a safe path into the forest with the fewest questions possible?

And a followup question, if that one is too easy for you:

Even though you don't strictly need to know in order to travel safely through the woods, you can't help but wonder which man is the knight, which is the knave and which is the alternator. After a brief internal struggle, you finally come up with a compromise between your curiosity and your politeness: How can you find a safe path into the forest and correctly identify all three men's roles at the same time, without asking the men more than one question each (i.e., not more than three questions total, one per man)?

• Wait a second, how can you be sure the information the person about the paths is correct? He could be a knave, right? – Wen1now Feb 21 '17 at 21:48
• >! Be careful about potential spoilers... – Admiral Jota Feb 21 '17 at 21:52
• Does the alternator always start out lying or is it random? – Maxqueue Feb 21 '17 at 22:00
• Random. His first statement might be true or false. – Admiral Jota Feb 21 '17 at 22:03
• Reminds me of this John Finnemore puzzle :) ...on a more serious note, this TED Ed riddle is pretty similar to yours, and is trending on YouTube now. – Shokhet Feb 23 '17 at 5:58

Ask the man that spoke to you:

Is the left path safe to travel?
If he says yes, take the left path, if he says no, take the right path.

Reasoning:

Since he has made two statements already and the second one is definitely true, there are two options left. He is either the knight and always speaks the truth, or he is the alternator, who lied the first time and spoke the truth the second time.
Option 1: he is the knight, so he always speaks the truth, which means that his first statement is true and there is at least one path that leads into peril. However, we also know from the trustworthy guidebook that there is at least one safe path, so from his answer we can gather which path we should choose.
Option 2: he is the alternator, so he alternates between telling the truth and lying. We know he told the truth the second time, so that means he will lie now. But more importantly, it also means he lied the first time, so the statement about there being at least one path that leads into peril is actually false. Consequently, no matter which route you take, it will always be safe.

Either way, taking the left path if the man answers yes and taking the right path if the man answers no will guarantee a safe trip.

For the follow-up question:

Call the man who just talked to you man A.
Question 1 (to A): Is he (pointing to one of the other men) the knave?
If A answers yes, call the man you pointed to C (and the other one B), otherwise call him B (and the other one C).
Question 2 (to B): Will you tell the truth in the following question (not this one) that is asked to you?
If B answers no, ask the third question below. Otherwise both paths will be safe, and you can choose either of them.
Question 3 (to C): Is the left path safe to travel?

If the answer to question 2 is:
Yes $\implies$ A is the Alternator, B is the Knave, C is the Knight. Since A is the Alternator, his first statement was a lie and there are no paths that lead into peril. Both paths will therefore be safe.
No $\implies$ A is the Knight, B is the Alternator, C is the Knave.

If the answer to question 3 is:
Yes -> take the right path
No -> take the left path

Reasoning behind this:

As mentioned above, the man who talked to you initially (man A) is either the Alternator or the Knight, since he told the truth on at least one occasion. If he is the Alternator, he will lie in his next statement; if he is the knight, he will (obviously) tell the truth.
This means that after asking question 1, there are two possible configurations:
Configuration 1: A: Knight, B: Alternator, C: Knave
Configuration 2: A: Alternator, B: Knave, C: Knight

We can know this, because the person pointed out as the Knave (whom we call C after that) is indeed the Knave if A is the Knight, and he is not the Knave (and therefore the Knight), if A is the Alternator (whose turn it is to lie).
Question 2 serves to point out which of these configurations is the correct one. By asking B if he will tell the truth in the following question, we can determine whether he is the Alternator or the Knave. The Knave will always answer Yes to this question (he will lie about lying) and the Alternator will always answer No (he will either truthfully say that he will lie or he will lie about telling the truth).
Therefore, if the answer is Yes, the correct configuration is 2 (A: Alternator, B: Knave, C: Knight) and if the answer is No, the correct configuration is 1 (A: Knight, B: Alternator, C: Knave).

Now we know who is who, we only need to figure out which path to take.
If Configuration 2 is correct, A is the Alternator and his first statement was a lie, so we can safely take either path and we don't need to ask a third question.
If Configuration 1 is correct, we don't know which path to take, but we can ask C, who is the Knave and who we know will lie. So if we ask him whether the left path is safe, we take it if he answers No and we take the right path if he answers Yes.

• The problem with the second statement is that strictly speaking, it is a conditional whose truth value I find hard to evaluate, since the speaker does not know whether the antecedent is true. I feel the puzzle could do with some mild rephrasing there. – Oliphaunt - reinstate Monica Feb 21 '17 at 23:13
• Perfect! And Oliphaunt, I've edited it slightly. Does that help? – Admiral Jota Feb 21 '17 at 23:32
• What if he is a knight, answers "no", and both paths are deadly? – Erel Segal-Halevi Feb 22 '17 at 4:10
• @Erel Segal-Halevi: the truthful guidebook tells us there is a safe path, so if he is the knight, we know there is precisely one safe path. – Levieux Feb 22 '17 at 7:09
• @JLRishe It's in the second sentence. – Admiral Jota Feb 23 '17 at 23:44

Scenario 1:

Ask any of the men if they are the alternator twice in a row If first answer is yes AND second answer is yes you know he is the knave You then ask him if path on right/left is safest and choose opposite You then ask the knave if the man next to him is the knight If he says yes then you know the man next to him is the alternator and the other man is the knight If he says no then you know vice versa from above This scenario will find who is who in 4 questions and safest path in 3

Scenario 2:

Ask any of the men if they are the alternator twice in a row If first answer is no AND second answer is no you know he is the knight Then you ask him which is safest path and choose that You then ask him if man next to him is knave/alternator and you then know who is who This scenario will find who is who in 3 questions and safest path in 4

Scenario 3:

Ask any of the men if they are the alternator twice in a row If first answer is yes AND second answer is no then you know he is alternator You then ask the man next to him if the man you asked the first question to is the alternator If he says yes then he is the knight and the other man is the knave You then know who is who You then ask knight if path on left/right is safest This scenario will find who is who in 4 questions and safest path in 3

Scenario 4:

Same as scenario 3 except mans first answer is no AND second answer is yes

Conclusion:

You can find out who is who and the safest path in 4 questions

• Not bad, but can you do it in fewer questions? – Admiral Jota Feb 21 '17 at 21:57
• With this strategy if you ask the alternator if they are the alternator twice in a row then you get an alternate as you said. However you can then ask them if the left path is safest. You know whether he is going to lie or not because You know he is the alternator and you know exactly how he answered the questions (ie whether they were true or false) and thus know whether he will reply honestly to the next question. – Chris Feb 22 '17 at 9:15
• @Chris But you don't know if the alternator started out lying or telling the truth only the fact that he is the alternator – Maxqueue Feb 22 '17 at 12:27
• @Maxqueue: You know the fact that he is the alternator. So if they answered yes first then they answered truthfully to start with, falsely second and thus the third will be truthful as well. And similar logic applies if they answered no first that their third question will be answered falsely.. – Chris Feb 22 '17 at 12:37

Pick any of the men, and ask him these three questions, in order:
1. If I ask you this same question immediately after this question, will you answer it the same way?
2. If I ask you this same question immediately after this question, will you answer it the same way?
3. Is that path safe? (while pointing to the left path with your left hand)
The knight will answer "Yes" to both questions 1 and 2, and then answer truthfully.
The knave will answer "No" to both questions 1 and 2, and then lie.
If the alternator answers "Yes" and then "No", he will then lie.
Otherwise, the alternator will answer "No" and then "Yes", and then answer truthfully.

• Not bad (although the last question isn't strictly phrased as a yes/no). But there is a solution that involves fewer questions than that. – Admiral Jota Feb 21 '17 at 21:14
• @AdmiralJota -- I have updated the answer to fix the yes/no problem. – Jasper Feb 21 '17 at 21:17

The person who spoke made two different statements, and the second one has been confirmed to be true. He is therefore either the knight or the alternator.
Is that path safe? (While pointing to the left path with your left hand.)
Is that path safe? (While pointing to the same path with your left hand.)
If he answers yes both times, he is the knight, and the left path is safe.
If he answers no both times, he is the knight, and the left path is dangerous.
If he answers yes and then no, he is the alternator, and the left path is dangerous.
If he answers no and then yes, he is the alternator, and the left path is safe.

• Very good! But there is a solution that involves even fewer questions than that. – Admiral Jota Feb 21 '17 at 21:29

@Levieux has already given a perfect answer, but I have an alternative, because

I don't want to use the fact that one man has already spoken.

So, for the first part,

Ask anybody "If I next asked you an irrelevant question, and then asked you whether the left path is safe, would you answer yes?"
The irrelevant question turns the Alternator into a Knight or Knave for the relevant questions, so we can use the standard Knight/Knave solution.
So, if the answer is yes, go left, if no, go right.

A not-answer for the second question:

After thinking things over, I see that the second question is not possible within the limit I gave myself.
Three people who can have three identities give a total of 3!=6 possibilities, multiplied with the two possible paths to take, gives a total of 12 possibilities.
With a total of three yes/no answers, you can distinguish between 2³=8 different cases.
Hence, three questions are not enough.