5
$\begingroup$

You are at an impasse with 30 doors - 29 of them lead to endless wandering the depths of hell - and one of them leads to paradise. In front of them stand the typical trio of good friends, a Knight, a Knave and a Joker. A Knight always gives answers truthfully. A Knave always gives the answer opposite to what a Knight would give. A Joker answers in a random fashion - what he says may be true or not. They all look alike, and they can only answer "yes"/"no". (no paradoxes allowed!).

What is the fewest questions you can ask to find the right door?

Improve this question
$\endgroup$
6
  • $\begingroup$ well, it is obviously unsolvable in 1 question and easily solvable in 2 questions, since you can find nonJoker in 1. $\endgroup$
    – klm123
    Commented Oct 20, 2014 at 19:38
  • $\begingroup$ well, you'd still need to pick the good door $\endgroup$
    – d'alar'cop
    Commented Oct 20, 2014 at 19:38
  • $\begingroup$ I assume the joker speaks truth/lies randomly? $\endgroup$
    – frodoskywalker
    Commented Oct 20, 2014 at 19:46
  • $\begingroup$ @klm123, what query do you use to find the nonJokers? $\endgroup$
    – Kevin
    Commented Oct 20, 2014 at 19:47
  • $\begingroup$ @frodoskywalker Yep, totally random $\endgroup$
    – d'alar'cop
    Commented Oct 20, 2014 at 19:47

2 Answers 2

Reset to default
11
$\begingroup$

First, you find a nonjoker in a single question as in Knight, Knave and Joker puzzle

Then you ask the nonjoker questions of the form "If I were to ask the other nonjoker X, what would he reply?" This is the way around not knowing whether you are asking Knight or Knave and is the usual approach to eliminating the uncertainty - you should get back a lie whatever you ask. (See Two doors with two guards - one lies, one tells the truth for example.)

So the solution is then how many such questions can get you from 30 doors to just one. 5 questions should be able to get you from 32 to 1 - the first to eliminate half the possibilities, and each subsequent one half of what remains. Exactly what you ask depends on answers you get, but one pattern might be

  • is the safe door in the range 16-30? Yes. (Means the truth is No.)
  • is the safe door in the range 8-15? Yes. (Means the truth is No.)
  • is the safe door in the range 4-7? Yes. (Means the truth is No.)
  • is the safe door in the range 2-3? No. (Means the truth is Yes.)
  • is the safe door #2? No. (Means the truth is yes.)

You may get lucky on one less question sometimes because there are only 30 doors, not 32. But in general you need 6 questions.

If someone stipulates that you can't say "the other nonjoker" but have to name a specific other guard, then you can spend one extra question by asking your known nonjoker "are you the joker?" - a Knight will say no and a Knave will say yes. In this case you need one more question, and your remaining questions can be asked directly without the "if I asked the other" business.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's exactly what I had in mind. I don't think it's possible to beat that. Let's see though $\endgroup$
    – d'alar'cop
    Commented Oct 20, 2014 at 20:02
  • 1
    $\begingroup$ "The other non-joker" should be fine shouldn't it? let's keep it at 6 questions total. or $\lceil log2 (number\ of\ doors)\rceil + 1$ $\endgroup$
    – d'alar'cop
    Commented Oct 20, 2014 at 20:07
  • $\begingroup$ This does not work, the knave is not defined as always lying. He is defined as answering the opposite of what the knight would answer to the same question. So if the safe door is number 2 and you ask "If I was to ask the other non-joker if the safe door is in the range 16-30, would he answer yes?" The knight would answer Yes. So the knave would answer No. And you don't get any information. "are you the joker?" still works. $\endgroup$
    – Taemyr
    Commented Oct 21, 2014 at 14:08
  • $\begingroup$ I just realised that the solution to finding the joker in one question suffers from the same problem. But that is fixable, you need to ask person A the question "Given the two statements "A is the knight" and "B is the joker"; is exactly one of these statements true? $\endgroup$
    – Taemyr
    Commented Oct 21, 2014 at 14:10
  • $\begingroup$ "If someone stipulates that you can't say "the other nonjoker" but have to name a specific other guard, then you can spend one extra question " .. you don't need an extra question even then . You can just ask, " What would you have said if I had asked you whether the safe door is in the range 16-30?" Putting the question this way will make the knight and the knave, both give a truthful answer. I can explain why if needed. $\endgroup$
    – Hemant Agarwal
    Commented Jun 7, 2021 at 11:39
3
$\begingroup$

6 questions are enough

In one question you exclude the joker. If the people are A, B, C, ask to A:

"Is B a knave or C a knight".

If A says yes, continue with B. If A says no, continue with C.

With the selected person you can find the correct door with a binary search by asking:

"If I'd ask you whether the door to parasise is among 1-15, would you say yes?"

and halving the range appropriately with each question. In total, you need 1 question to identify a non-joker and 5 to identify the door.

6 questions are necessary

You need to identify 1 possibility among 29.

You could in principle halve the number of possibilities of the worst case with each questions and identify the door in 5 questions.

But if the first question goes to the joker, you won't learn anything. The joker can reply yes or no to any question regardless of where the door is. If you think of it, he could reply randomly without even knowing which one is the right door. Therefore you cannot learn anything about the door from the joker.

So, in the worst case, your first question goes to the joker and you still have 29 doors to discriminate. And for this you need 5 more questions. The wost case requires 6 questions.

Improve this answer
$\endgroup$
4
  • $\begingroup$ lol.. good job anyway +1. Also include maybe this: $\lceil log2 (number\ of\ doors)\rceil + 1$?. Was it too easy by the way? $\endgroup$
    – d'alar'cop
    Commented Oct 20, 2014 at 20:11
  • 1
    $\begingroup$ The solution in 6 questions was easy. To convince myself that it is also minimal took longer. I somehow suspected there is a trick because 29 doors + 3 people = 32. $\endgroup$
    – Florian F
    Commented Oct 20, 2014 at 23:41
  • $\begingroup$ The questions you does not work with the way the knave is specified. The question "If I'd ask you whether the door to parasise is among 1-15, would you say yes?" needs to be (if stated to person B) "If I'd ask person B whether the door to parasise is among 1-15, would person B say yes?" $\endgroup$
    – Taemyr
    Commented Oct 21, 2014 at 14:18
  • $\begingroup$ Asking A what B would say doesn't work because if B is a joker, A doesn't know what he would say. If asking A about himself, he can tell reliablty what he would say, and for the joker it doesn't matter. $\endgroup$
    – Florian F
    Commented Oct 21, 2014 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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