4
$\begingroup$

Standard knights and knaves problem. There are 10 people in a room, you know that each person will either always tell the truth or always lie, but you don't know who is a truth teller or liar.

You are in a room with 5 doors. Four of the doors lead to horrible hazards like an endless pit, a fiery inferno, or being forced to visit your in-laws (the horror!), one of the doors leads to freedom.

What is the fewest number of questions you may ask to guarantee that you get out to freedom? What process would you use? It is assumed that all of the 10 people have knowledge of which door leads to freedom.

Improve this question
$\endgroup$
5
$\begingroup$

A) In this case I suppose you are allowed to ask only yes-or-no questions.
In this case 2 questions allows you to chose only between 2x2=4 options, so you need at least 3 questions.
It is very easy to formulate them. Just ask each time "What would you answer if I ask you blabla" and you will know the truth about blabla. Let's use WWYA shortcut for all these words. Then 3 questions you will need to ask:
1. WWYA is a freedom-door among first 4?
2. WWYA is a freedom-door among 1 and 2? (or just go to the 5th, if you've just got No)
3. WWYA is a freedom-door the 1st? (or "the 3rd", if you've just got No)

B) It is much more interesting to find a question when you are allowed to ask any questions. You can not ask "What you would answer if you are asked, which door leads to freedom?", since liar would answer the wrong door number and then it would lie about this number, but here he can use another wrong number, fortunately for him he has 3 more bad doors left.

But I think "What you can not answer because of your nature when you are asked, which door leads to hazards?" will do the job. To "Which door leads to hazards?" liar must answer the freedom-door. Then to "What you can not answer ...?" he would have the only one wrong answer to tell: the freedom-door. Meanwhile truthteller can answer to "Which door leads to hazards?" any door out of 4 bad-doors, therefore to "What you can not answer ...?" truthteller have also only one answer possible: the freedom-door.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I had intended for the B answer, I intentionally didn't constrain the questions to leave things a little more interesting then the standard questions. Still, I like both answers :) $\endgroup$ – dsollen Oct 11 '14 at 21:13
  • $\begingroup$ You didn't even specify that we can only ever ask one person at once. Just let 5 People stand in front of one door each and ask WWYA the door to freedom, only one will say yes :-) (Or you can formulate the question so all of them have to remain silent and only the one in front of the right door can speak) $\endgroup$ – Falco Oct 13 '14 at 9:23
  • $\begingroup$ @klm123 The Knave could also answer "none" or "all of them" when asked "Which door leads to hazards?" $\endgroup$ – Falco Oct 13 '14 at 9:26
  • $\begingroup$ @Falco, may be. this makes such type of problem not really correctly formulated. Thats why usually we have only yes-no-questions allowed, or it is formulated explicitly that guys can answer number of people, or id of a man, etc. $\endgroup$ – klm123 Oct 13 '14 at 9:31

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.