1
$\begingroup$

If the island of knights and knaves got together and there were n people, including a joker, how many questions would it take for all of the knights and knaves found the joker?

Nobody knows who each other is. When the knight finds the joker, he/she may tell the others, if a knave finds a knight/another knave the knave will do so. Only 1 person asks a question at once. The knave can not always exclaim he/she found a joker when they find a knight/knave. Let's assume a 50-50 chance of telling the others.

What's the least amount of questions needed to guarantee everybody knows who the joker is for sure?

The joker don't just randomly tell truth/lie. He can also exclaim that he found the joker himself.

Standard rules apply, nobody had any knowledge about eachother, or what they would have answered. You can not silence them, if you do they will kill you (very violent knights and knaves huh?)

$\endgroup$
  • $\begingroup$ n IS finite by the way. $\endgroup$ – warspyking Nov 15 '14 at 19:08
  • $\begingroup$ When someone finds out that someone else is a knight or a knave, can he/she tell the others? $\endgroup$ – Victor Stafusa Nov 15 '14 at 19:14
  • $\begingroup$ @Victor No the knights can't. Only when found the joker. Although the liars can. $\endgroup$ – warspyking Nov 15 '14 at 19:15
  • $\begingroup$ Can the knave give away his identity with something like "Joe is the joker and 1+1=3" to say that someone is not the joker? $\endgroup$ – Victor Stafusa Nov 15 '14 at 19:17
  • 1
    $\begingroup$ I've read the question a few times and I do not have a clear idea what the model is for who asks questions of whom or for what restrictions there are on non-question communication. $\endgroup$ – Peter Taylor Nov 25 '14 at 18:37
5
$\begingroup$

First, I am not trying to find the smallest number of questions. Let's just find an answer and then try to optimize it.

If you ask to each person the question "Are you the joker?", the knights would answer "no" and the knaves would answer "yes". This easily separates them, but leaves the joker in any of the two groups.

Lets suppose that the joker answered "no", so he is in the knights group. Since he does not want to be caught and is presumably smart, he would pose himself as a knight, always giving the answers that a knight would give.

Now, lets suppose that the joker answered "yes", so he is in the knaves group. Since he does not want to be caught and is presumably smart, he would pose himself as a knave, always giving the answers that a knave would give.

Since nobody (except the joker himself) knows if somebody else is or is not the joker and nobody can give a proof that he is not the joker, we have a situation that if the joker answered "yes", he can't be distinguished from a knight. If he answered "no", he can't be distinguished from a knave.

Asking a knight "Do you know who is the joker", he would answer "No". The knave would answer "Yes". The joker would follow saying what a knight or a knave would say accordingly to his previous answers. No information is gained here.

Asking a knight if somebody else is or is not the joker would produce the answer "I don't know" or something similar. If you ask this to a knave, he could not answer "yes", "no" or "I don't know", so he would answer "I know the answer, but I can't tell you" or something similar. The joker would follow the answers from the group he chose. This is essentially the same as the previous question, so again, no information is gained here.

If the question is changed to "Is the joker among/not among that X group?" the same "I don't know" and "I know the answer, but I can't tell you" answers will follow from the same people for any arbitrary definition of group X, and no information gain would be produced. There is an exception for trivial cases where X is an empty group, a group with everybody or a group with everybody except who is being asked, which would not produce any information gain either.

If you change the question to "what would the person X answer if I asks him if person Y is the joker?", the pattern gets a bit more complicated, but this would not produce any information gain either.

So, in all the ways, except if the joker blunders by producing an incoherent answer somewhere, it is impossible to solve the puzzle only with the provided information, even if we knew what the joker answered to the "are you the joker?" question (and yet, we don't).

But I have a lateral thinking answer: To not be caught, when the joker decides to pose himself definitely either as a knight or a knave, he essentially becomes a knight or a knave, so we have no joker anymore, and thus the puzzle is solved: Nobody is the joker and the least amount of questions is zero!

$\endgroup$
1
$\begingroup$

Original post:

The joker don't just randomly tell truth/lie. He can also exclaim that he found the joker himself.

A comment on the OP:

He will random lie/truth when asked questions, and will randomly pick to lie and say someone is the joker.

If the joker acts like above and will "random[ly] lie/truth[-tell] when asked questions" (as OP clarifies in comments on the OP) then you can't define any optimal strategy as the joker may contradict himself after $2$ questions, or after $2+n$ questions.

Furthermore, if he can be consistent and choose to answer like a knight, you can never tell the difference between a joker and a knight (similar result if he always pretends to be a knave).

There have been several questions like this, with Ks and Ks, then a Joker which you have to identify - you can never tell who the Joker is if he is able to consistently act like Knight or Knave, and if he can't, you can't determine how long it'll take to out him.

$\endgroup$

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