8
$\begingroup$

You find yourself in the usual situation with three locals whose answering is highly restricted. First, they can only answer yes or no questions. Second, one will always answer truthfully, one will always lie (answer the opposite of the truth), and one gives answers that are completely unconstrained - might be random, always yes, alternate truth and lie, alternate yes and no, or anything else (with one exception, below.)

Unlike other KKJ scenarios, these three are teenagers and as such lack true self awareness or awareness of the inner nature or motivations of others. Simply put, you cannot ask them questions about the structure of the puzzle (their life) such as "does Steve ever lie?" or "are you the one who always tells the truth?" These questions are unanswerable for them, and as such will gain you only a sulky teenage stare, from which you learn nothing. Asking the truth teller "will you answer this question Yes?" gets you the same sulky stare as the paradoxical "will you answer this question No?" even through the first should be answerable. They can't answer anything about how the others will answer a hypothetical future question, or how they themselves will answer, and they are unaware of the labels Knight, Knave, and Joker, or even of these categories of behaviour.

They can answer questions about past events: "when I asked you how many red balls I had in my hand, did you reply truthfully?" or "Has Steve ever lied to me?"

Since they don't know the labels, there is no difference between a "Joker whose strategy is to always respond truthfully" and a Knight, nor between a "Joker whose strategy is to always respond with a lie" and a Knave, therefore this Joker will not choose either of those strategies. However, Jokers won't sulk at a question that Knight or Knave would answer, or answer one they would sulk at.

Is there a way, given any number of questions, the usual props of the genre (coloured balls, coins, scales etc) about which you can ask questions, and plenty of time, for you to establish conclusively who is Knight, Knave, and Joker? What strategy does so in the fewest questions?

Edit: split the scenarios into two:

  • the teenagers have been answering questions from other visitors before your arrival and have learned enough information that if they provided all the information to you, you would be able to label them, even though it doesn't occur to them to label each other
  • the teenagers have never heard each other answer any questions yet, or have heard only questions in which the Joker happens to have always answered the truth or always a lie, and therefore cannot yet be distinguished from whoever they are agreeing with.

In the first scenario you can distinguish them quickly, without waiting for the Joker to diverge from a pattern. In the second, is there any strategy other than waiting while asking questions with known answers?

$\endgroup$
  • $\begingroup$ Does asking them each the same question count as 1 or 3 questions? $\endgroup$ – warspyking Oct 21 '14 at 15:47
  • 1
    $\begingroup$ The joker could ALWAYS mimic both the truth or lies. Making this impossible. $\endgroup$ – warspyking Oct 21 '14 at 15:51
  • $\begingroup$ @warspyking read the second to last paragraph again. They could almost always mimic a knight or knave and that is the basis for my answer. $\endgroup$ – kaine Oct 21 '14 at 17:02
  • $\begingroup$ @kaine They may not have a strategy to do so, but they may randomly reply the truth every time, making your answer take theoretically, forever, to finish executing. $\endgroup$ – warspyking Oct 21 '14 at 17:25
  • $\begingroup$ Unless I'm missing something, a Joker could behave like a Knight or Knave with an arbitrarily small difference. Perhaps she only lies one time in a million, and nobody has ever seen her lie yet. Is there some definite restriction on the rate of the Joker behaving in a Knight/Knave way? $\endgroup$ – Jason Patterson Oct 22 '14 at 19:09
8
$\begingroup$

Ask all three "Do I have a ball?" while holding up a ball. If the first two agree, let the third leave.

If the dissenter said yes, he is a knight. If he said no he is a knave. The other two are obviously the other two.

Ask the leaving knight or knave if each of the remaining two ever behaved differently from the knight/knave behavior you have left. This lets you use his/her previous interactions to try and find the Joker. If he doesn't know which is which from previous behavior, just let him leave.

If you haven't learnt who they are from the identifed individual, tell the remaining two that they may leave when they disagree.

Repeatedly ask them in random order different questions with obvious answers. The first one to change his behavior is a Joker. The remaining one is the remaining class.

Unfortunately, we have to assume that the Joker will behave almost exactly like a Knight or Knave except for one in a billion cases. This means that this is the best strategy for an unknown strategy. It will take a minimum of 3 and a maximum without an upper bound to determine who is who. Fortunately, being a teenager, the Joker will likely want to leave and stop being annoyed so will let you know who he is quickly.

$\endgroup$
  • 1
    $\begingroup$ this is kind of brute-force, though. Can you not use your knowledge of the leaver being a knight or knave to speed this up? $\endgroup$ – Kate Gregory Oct 21 '14 at 15:28
  • $\begingroup$ My assumption is that the Joker behaves very simularly to a Knight or a Knave either by strategy or random chance. This means the only way to improve upon this is to ask questions that predict the difference in his strategy. You cannot ask questions they do not know the answer to as they will just Sulk. You can't always ask the same question in case his responses are related to the question. You can't always ask different questions in case his strategy is alternative between Knave and Knight every 100 questions. I am probably missing something... don't know what yet. $\endgroup$ – kaine Oct 21 '14 at 15:37
  • 1
    $\begingroup$ Actually, are you implying i could ask about past events during which i was not present. aka ask the leaving Knave, "has Bob ever lied to you?" and "has Sally ever lied to you?". If he answers no to one, he/she is your Joker? $\endgroup$ – kaine Oct 21 '14 at 15:40
  • $\begingroup$ @kaine My thinking on this was that you could ask a question of the type you suggest, but there is still a problem. Bob and Sally have only interacted a finite number of times, so if Sally were a Joker who took an "almost always tell the truth" strategy, Bob might not know that she lied sometimes. Basically this allows us to shorten the number of questions that might end with our answer, but it does not guarantee that we will find the Joker. If there were some definite limits on how the Joker deviated from Knight/Knave, then there would be an answer, but I think we have to brute force it. $\endgroup$ – Jason Patterson Oct 22 '14 at 19:05
  • $\begingroup$ @JasonPatterson I agree which is why when I included this in the answer above, i kept the brute force method in place afterwards. $\endgroup$ – kaine Oct 22 '14 at 19:08
3
$\begingroup$

The answer to the question is in the question itself.

Let Alice, Bob and Charles represent each person respectively.

You have never met any of these teenagers or asked them any questions (otherwise, pick somebody who hasn't). However, they don't know that, as each person only knows their individual history with you. Therefore, you ask Alice, "Has Alice ever lied to me?"

If Alice responds "No", she is the truth teller (the Knight), as you have never met or talked before. If Alice responds "Yes", then she is the liar (the Knave).

If Alice is the Joker, she will not respond. This is because the joker is unwilling to answer any question the Knight Or the Knave would sulk at (they both would sulk, as they have no idea if Alice has ever lied to you and have no "awareness of the inner nature or motivations of others"). If Alice is the Joker, one more trivial question (e.g. "Does 1+1=2?") will differentiate Knave from Knight.

If Alice is either Knave of Knight, proceed to ask Bob, "Has Bob ever lied to me?". If Bob responds "No", he is the truth teller (Knight), if he responds "Yes", he is a liar (Knave), and if he doesnt respond, hes the joker!

$\endgroup$
  • 3
    $\begingroup$ I believe Alice would respond if she is the joker - I believe OP meant that a joker would only not respond if she had been a knight or knave and been asked the question. $\endgroup$ – Rob Watts Oct 21 '14 at 19:21
  • $\begingroup$ @RobWatts I am unsure how you came to that interpretation. The riddle literally says Jokers will not answer a question a Knight or Knave would sulk at, and that is exactly the case here. $\endgroup$ – n00b Oct 21 '14 at 19:26
  • 1
    $\begingroup$ The disgreement here is whether you are defining a Joker's behavior with regard to sulking with respect to Bob and Charles or with regard to the behavior of a Knight or Knave under the same situation. While I agree with Rob's interpretation because the tone of the entire paragraph is in that line, this is definitely a clever one. I don't think, however, that you know what they know about each other's past history with you. $\endgroup$ – kaine Oct 21 '14 at 19:44
  • 2
    $\begingroup$ I agree with Rob here. It's not that The Jester will sulk like The Knight or The Knave, but that any Jester will sulk as if they were a Knight or Knave. In this scenario there happens to be one of each, but the theme is that they're not aware of that! $\endgroup$ – TheRubberDuck Oct 21 '14 at 19:56
  • 1
    $\begingroup$ Alice is equally capable of answering all the "has X ever lied to me" questions by someone who has just arrived. She knows the real answer is "no" and can answer yes or no according to her internal rules. What she can't answer is "will Alice lie if I ask X" or the like. Further, the "won't sulk unless knight or knave sulks" isn't some special joker identifying rule - all three of them have the same rule about answering or not answering - a question one will answer all will answer. $\endgroup$ – Kate Gregory Oct 22 '14 at 1:34
3
$\begingroup$

Let's look at the two scenarios:

They know enough for you to figure it out

There's actually a little bit more information that needs to be provided to give a conclusive answer to this scenario. If each one of them knows enough information that, if you knew it, you could label them, you only need to ask three or four questions to get this. Otherwise, it gets a little bit more complicated.

If each one knows enough information, that means that there has been at least one question to which the joker has answered truthfully and one to which they have answered falsely.

In any case, the first two or three questions are used to figure out who the knave or knight is by asking them all the same question (such as @kaine's "Am I holding a ball right now?"). If the first two agree you don't need to ask the third - if they both lie you've found the knave and the joker, and if they both tell the truth you've found the knight and the joker. If they don't agree you have no information about who they are, so you do need to ask the third. Call the person who disagreed with the other two A.

So, knowing that A is the knight (or the knave), you just need to identify one of the other two. Simply ask A:

Has B ever answered a question truthfully?

If they say "yes" (or "no" from the knave), then B is the joker and C is the knave (or knight). Otherwise, C is the joker and B is the knave (or knight).

So what if their individual knowledge is not enough but their combined knowledge is? There's actually only one extra case here - the joker knows but the other two don't. This is because there's no way for the knight to know but the other two not to - if the knight knows the joker must have both told the truth and lied, so the joker will be remember both having told the truth and having lied, and the knave will have also heard the joker's answers and know as well.

So how do we handle the case where the joker knows, but the knave and knight don't? For example, suppose the joker is almost always identical to the knave, but there was one question asked of the knight or knave to which the joker would have told the truth. Because the joker was not asked the question, the knight and the knave never heard the joker answer truthfully, so they do not know the difference between the knave and the joker. In this case, if the knight is asked about the other two ever responding truthfully, the answer will be "no".

If the knight can't tell us that either of the other two has told the truth, we need to ask a question that can distinguish between the joker and the knave. In this case, we ask B:

Think back on the questions that have been asked and think about what you did or would have said to each. For the first question for which you did or would have answered truthfully, what did or would you have said?

If B is the knave, there is no such question - they always would have lied, so you'll simply get a sulky stare. If you ask the joker you'll get a response, and it doesn't matter whether it is 'yes' or 'no'.

The best strategy is not to ask the knight about the other two at all - the joker will always be able to answer the second question. So we ask B the second question, and B will answer if and only if they are the joker.

Summary:

Ask two of them if you're holding a ball:

If they disagree, ask the third if you're holding a ball

Call the two who agreed B and C.

  • If B and C both lied, ask B the joker-identifying question
    • If B sulks, A is the knight, B is the knave, and C is the joker
    • If B answers, A is the knight, B is the joker, and C is the knave
  • If B and C both told the truth, ask B the joker-identifying question (changed to asking if they ever had or would have lied)
    • If B sulks, A is the knave, B is the knight, and C is the joker
    • If B answers, A is the knave, B is the joker, and C is the knight

They don't know enough for you to figure it out

If you had a full transcript of every question they've answered so far with their answers and still wouldn't be able to tell who the joker is, we're out of luck. As the others mentioned, there's no way to predict what the joker's answering strategy is. For example, suppose the only question for which the joker will lie is "is $p!-1$ a prime number?" for some large prime number $p$. There are an infinite number of primes, so there are an infinite number of potential questions to check.

So without any constraints on the joker's answering strategy, there is no way to guarantee finding the question that will reveal the joker. It's possible that the joker has gone their entire life only ever telling the truth, and nobody will ever ask them one of the questions to which they will lie about. They might go their entire life thinking they are a knight, never realizing that they do have the power to lie. Mourn for this poor joker, forced to live a life that does not allow them to live up to their potential.

$\endgroup$
  • $\begingroup$ you are stretching the definition of "yes or no question" to ask "what would your answer have been / what was your answer?" expecting yes or no. But since I suppose "would have / was your answer yes ?" is almost equivalent, it's allowable. (If your answer would have been or was to not answer, you can say no to "was it yes?". You can get around that by first asking "did/could you answer?" and then asking if the answer was yes. $\endgroup$ – Kate Gregory Jul 15 '15 at 16:42

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.