9
$\begingroup$

Suppose you are traveling and come to a fork in the road. One of them leads to something good like a cat shelter and a company handing out free ice cream and money, while the other leads to something terrible like a series of pasta parties you can't join.

The path is guarded by $n>1$ guards. Each one either always tells the truth or tells lies. They all have perfect knowledge of which of them is honest or dishonest and which path goes to which destination. You know that at least one guard is honest and at least one is dishonest, but you don't know which or how the others answer questions.

As a function of $n$, what is the smallest number of questions you must ask to be guaranteed to discover which path to take? To keep the problem mathematically formal, questions should be able to be expressed as Boolean logic expressions, which the guards will then answer with true or false, depending on their dispositions. You solve the puzzle when you can use the guards' answers to know which path to take. You can decide which questions to ask depending on the responses you get, but if an approach has an upper and lower bound for how many questions you must ask, you want to minimize the upper bound.

Also, the guards know how to evaluate the statement $H(G)$, which is true if guard $G$ is honest, and $I(P)$, which is true if the path $P$ takes you to your destination. If you can think of other statements that make sense for the context of the puzzle, feel free to use them.

Improve this question
$\endgroup$
1
  • $\begingroup$ Hint: what is the answer when $n=2$? $\endgroup$
    – Kevin
    Commented Nov 20, 2014 at 15:33

4 Answers 4

Reset to default
8
$\begingroup$

$1$ question will suffice - for whatever $n$ (given the other constraints). Take guard 1, $g_1$, given that we have $2$ paths $p_1 ,p_2$ and we disregard the way we came from.

Ask $g_1$ "(you are a liar $\land$ $p_1$ leads to the cat shelter) $\lor$ (you are a truthteller $\land$ $p_1$ leads to the pasta party)?"

Explanation:
There are 4 possible conditions:
Case 1: $g_1$ is a liar AND $p_1$ leads to the cat shelter. You will get the answer: FALSE
Case 2: $g_1$ is a truthteller AND $p_1$ leads to the cat shelter. You will get the answer: FALSE.
Case 3: $g_1$ is a liar AND $p_1$ leads to the pasta party. You will get the answer: TRUE
Case 4: $g_1$ is a truthteller AND $p_1$ leads to the pasta party. You will get the answer: TRUE

Thus, if you get the answer TRUE you take $p_2$, if you get FALSE, you take $p_1$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @AeJey But he's a liar... so he'll say FALSE $\endgroup$
    – d'alar'cop
    Commented Nov 20, 2014 at 8:46
  • $\begingroup$ Ya ya. Now got it :) $\endgroup$
    – AeJey
    Commented Nov 20, 2014 at 8:47
  • $\begingroup$ @AeJey Awesome :D $\endgroup$
    – d'alar'cop
    Commented Nov 20, 2014 at 8:47
6
$\begingroup$

The classic 1-guard solution works for any number of guards. Pick a guard $G$, and ask him $H(G) \iff I(P_1)$: "Are you honest XNOR is path 1 good?" Then, take path 1 if he says "True" and path 2 if he says "False".

Liars lying and honest guards not lying is equivalent to every guard $G$ XNORing the answers to questions with $H(G)$. By building an XNOR with $H(G)$ into the question we ask, we cancel this out, and the answer we get will always be $I(P_1)$.

Improve this answer
$\endgroup$
12
  • $\begingroup$ isn't xoring two questions together still two questions? I mean, you are asking "Are you honest" (which, btw, both knaves and knights will answer yes) and then xoring that value with "is path one good". Technically it is two questions, and technically the first question will always be true. So you are indeed asking "is path 1 not good". $\endgroup$
    – vero
    Commented Nov 20, 2014 at 8:05
  • 1
    $\begingroup$ @Rodolvertice: No. I'm not asking the guard two questions and XORing the results; I'm asking the guard to compute the value of a single boolean expression and give me a single true/false answer. $\endgroup$
    – user2357112
    Commented Nov 20, 2014 at 8:43
  • $\begingroup$ @user is correct. The XOR statement can be expressed in a single Boolean expression, so by the rules of the puzzle, it counts as a single question. If you had to ask two guards, or ask the guard a different question depending on the results of a first question, that would count as a second question. $\endgroup$
    – Kevin
    Commented Nov 20, 2014 at 15:56
  • $\begingroup$ Am I misunderstanding how this works? In the case that p1 is good, the liar will say (yes XOR no) = true, but the honest will say (yes XOR yes) = false, so it doesn't tell you anything. $\endgroup$
    – Nattgew
    Commented Nov 20, 2014 at 16:55
  • 1
    $\begingroup$ @Nattgew: The liar doesn't lie about both halves separately and XOR the lies; he lies about the question as a whole. In other words, he computes "not (no XOR yes)", not "(yes XOR no)". (If he did XOR two lies, you could instead ask "Is the sky blue XOR is path 1 good".) $\endgroup$
    – user2357112
    Commented Nov 20, 2014 at 17:35
1
$\begingroup$

The minimum number of questions required is 3.

Ask the first guard "If I ask you and the second guard which is the correct path, will your answers be the same?", then go to the second guard and ask him "If I ask you and the first guard which is the correct path, will your answers be the same?"

If the responses by both the guards are different, you can confirm that one of them is a truth telling guard (knight) and other is a liar (knave). Now you can ask the normal knight/knave question to get the right path:

Ask either of them, "If I ask the other guard which path will lead to the cat shelter, which path will he show me?"

Then go down the other path than the one the guard pointed to.

Now if both the guards answered the same, check what they have answered.

If they both answered yes, they both are knights. If they both answered no, both of them are knaves.

Now if both are knights, ask one of them which is the path to cat shelter and go down the path he points to. If both are knaves, ask one of the which is the path to cat shelter take the other path.

Still 3 questions.

So the final answer is that whatever the value of n may be, the total number of questions needed to find the right path will be 3.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm excited to see your explanation! $\endgroup$
    – Kevin
    Commented Nov 20, 2014 at 5:48
  • $\begingroup$ I would like to point out that there's a trivial case when $n=2$: that's the standard version of the problem, for which you only need one question. Are you sure that doesn't affect your solution for small values of $n$? $\endgroup$
    – Kevin
    Commented Nov 20, 2014 at 5:52
  • $\begingroup$ No it won't, even if there is just 2 guards, we need to figure out whether they both are knight, or both are knave or one is knight and the other is knave $\endgroup$
    – AeJey
    Commented Nov 20, 2014 at 6:00
  • $\begingroup$ I have updated the answer to 3 since I haven't included the normal single question used to find the path in knight knave problem. $\endgroup$
    – AeJey
    Commented Nov 20, 2014 at 6:01
  • 5
    $\begingroup$ You don't need to figure out anything about which guards tell the truth or lie; you can just ask questions that truth-tellers and liars will give the same answers to. $\endgroup$
    – user2357112
    Commented Nov 20, 2014 at 6:17
-2
$\begingroup$

You only have to ask one question.

Ask either Guard "If I were to ask the other Guard which is the best path to take what would be his answer?"

You then follow the opposite path.

The logic is one lies one tells the truth. So if you ask the question to the liar he will tell you the opposite of the true answer from the other guard, and if you ask the true guard he will tell you the answer from the liar which will be the wrong path.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ But what if n>2 ? $\endgroup$
    – A E
    Commented Nov 20, 2014 at 15:09

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