2
$\begingroup$

I hope this question falls into the correct category. I'm sure the 2 paths , 1 liar and 1 truthful is common, however, is there a general strategy given:

  1. There are N-number of doors/paths/or destinations (you get the point). For simplicity sake, let's assume that N is an even integer greater than 2.
  2. There are N/2 'guards' who lie, and N/2 'guards' who tell the truth.
  3. There are N/2 'good destinations' and N/2 'bad destinations'.
  4. You can ask K-number of 'guards', only once. With K<=N

The objective is still the same: The player wants to be in the 'good destination'.

Is there a generalized strategy for this? Is there a way to minimize k while still achieving the objective?

Thanks!

$\endgroup$
2
$\begingroup$

It should actually be in this format: $N = 2^r; r\in\mathbb{Z}^+$ Assume that there are $8$ guards of which half speak the truth and half lie. Now, enter image description here

Since there are $4$ leaves at the bottom, we can now treat them individually as 2 guards and 1 correct destination problem. This also means that there is a chance that two liars and/or two truth tellers may end up in the same division. So, since the number of question $K\le N$, the question would suffice to find the correct destinations. That is, if both say the same answer it is no way possible to find if they are TT or L unless we can ask the other group. But the worst case is first two leaves are of one group (say TT) and the next two leaves are all L. So, it is useful to note the answers of all the people along with the path they were asked about in the first pass and if the worst case happens, first pass won't give any answer. So, rearrange them so that no answer matches. Now, since you have noted down the previous answers of the people along witht the answer they were asked about, you can now find all the TTs, Ls and the correct destinations. enter image description here

    TT = Truth teller
    L = Liar
    Y = Yes
    N = No
| improve this answer | |
$\endgroup$
  • $\begingroup$ thank you very much for your answer. However, I don't quite understand the point of making a combination table. Is your point headed towards 'an optimal state/scenario' or am I missing your point completely? Once again, really appreciate the answer. $\endgroup$ – Rashad May 25 at 14:08
  • $\begingroup$ It is just a logic to figure out on how to ask the question and what answer can be expected based on the identity of the persons interrogated. And, welcome, Rashad :) $\endgroup$ – John Brookfields May 25 at 14:55

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.