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.
Answer
$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$.
No comments:
Post a Comment