# Knight/Knave/Joker - impasse challenge

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?

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

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.

• That's exactly what I had in mind. I don't think it's possible to beat that. Let's see though – d'alar'cop Oct 20 '14 at 20:02
• "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$ – d'alar'cop Oct 20 '14 at 20:07
• 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. – Taemyr Oct 21 '14 at 14:08
• 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? – Taemyr Oct 21 '14 at 14:10

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.

• lol.. good job anyway +1. Also include maybe this: $\lceil log2 (number\ of\ doors)\rceil + 1$?. Was it too easy by the way? – d'alar'cop Oct 20 '14 at 20:11
• 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. – Florian F Oct 20 '14 at 23:41
• 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?" – Taemyr Oct 21 '14 at 14:18
• 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. – Florian F Oct 21 '14 at 14:35