4
$\begingroup$

Much like this other time, you are lost in town and come across a line of $j$ jokers and $k$ knights. You don't know who is who, but they all know the identities of each other. A knight always tells the truth to a yes-no question, while a joker can say either yes or no (and will say one of the two). Your goal is to identify one knight by asking one yes-no question to each of the first $j$ people in the line. (Note the first $j$ people in the line is a unknown combination of knights and jokers.)

As you might guess, it is easier to identify a knight if there are more knights; so your task is easier for larger values of $k$. For a given $j$, what is the smallest value of $k$ that allows you to identify a knight?

(Make sure you don't ask a question that might be impossible for the person to answer.)

(There are lots of similar questions, but from what I can tell this is a new one.)

$\endgroup$
  • $\begingroup$ is it assumed that the first $j$ people contains at least one knight? $\endgroup$ – Bob Jul 13 '15 at 19:42
  • $\begingroup$ @Bob: No; you could be asking your questions to all jokers. $\endgroup$ – Tyler Seacrest Jul 13 '15 at 19:45
  • $\begingroup$ So it might be impossible to obtain any reliable information. $\endgroup$ – Bob Jul 13 '15 at 19:47
  • 1
    $\begingroup$ Yeah, that does seem like a problem. That's part of the reason for the link "Much like this other time", which seems impossible but has a good discussion about why it actually is possible. $\endgroup$ – Tyler Seacrest Jul 13 '15 at 19:51
  • 1
    $\begingroup$ @Taemyr no reliable answer would be more accurate wouldn't it? $\endgroup$ – Bob Jul 14 '15 at 8:41
3
$\begingroup$

celtschk's solution is optimal.

We will show that if $k<2^j$, you cannot always successfully select a knight.

First of all, as other commenters have pointed out, the first $j$ people in line could be all $j$ jokers, and give you any answers they want. Therefore, you can never safely select one of the first $j$ people. So, you must always select one of the other $k$ people.

Also, since you must succeed with 100% probability, there is no point in using a randomized strategy. Therefore, we can consider your selection strategy to be a function which inputs a sequence of $j$ answers (e.g. (yes, no, ..., yes)), and outputs your selection of one of the last $k$ people in the line.

Suppose $k < 2^j$. Then by Pigeonhole there are two sequences of answers $s_1, s_2$ which cause you to select the same person $p$.

The jokers will now confound you, as follows. They will place a joker at spot $p$. Among the first $j$ people will be the remaining $j-1$ jokers, as well as one knight at the first spot where $s_1$ and $s_2$ differ.

The jokers will then answer your questions so that you hear either $s_1$ or $s_2$ depending on how the knight answers. This causes you to incorrectly select person $p$ as a knight.

Since the jokers can pull this trick, if $k < 2^j$, you cannot be sure of always selecting a knight. Therefore, celtschk's solution with $k=2^j$ is optimal.

$\endgroup$
  • $\begingroup$ I had a hard time deciding which answer to accept between yours and celtschk's, but as celtschk's half of the answer did have a minor error (albeit one that celtschk could easily fix I'm sure), I decided to go with yours. $\endgroup$ – Tyler Seacrest Jul 15 '15 at 4:12
5
$\begingroup$

OK, I think I've found the solution:

We need $k=2^j$ knights.
For $j=1$, you ask whether the second person is a knight. If the answer is "Yes", the second person is a knight, if the answer is "no", you know the third person is a knight. If the first person is a knight, he says the truth, and thus the choice mentioned before is evidently right. But if the first person is a joker, both remaining persons must be knights, especially the selected one.
For $j=2$, you ask person 1 if both person 3 and person 4 are knights, and person 2 if both person 3 and person 5 are knights. If both say "yes", you chose person 3, if the first says "yes" and the second "no" you chose person "4", if the first says "no" and the second says "yes" you choose person 5, and if both say "no", you chose person 6. For the general case, you ask each of the first $j$ persons whether a selection of $2^{j-1}$ of the remaining $2^j$ persons consists of all knights. Those sets are selected in a way that any two of the remaining $2^j$ persons are asked about to a different set of the first $j$ people (basically, you numerate them in binary, and select whom to ask about them based on which bits are $1$). Then based on the answers, you select that one where everyone where he was included in the set has answered "yes", and everyone else has answered "no".
Example: $j=3$, $k=2^3=8$.
Ask 1: "Are 4,5,6,7 all knights?"
Ask 2: "Are 4,5,8,9 all knights?"
Ask 3: "Are 4,6,8,10 all knights?"
Answers:
Yes, Yes, Yes $\implies$ 4 is knight
Yes, Yes, No $\implies$ 5 is knight
Yes, No, Yes $\implies$ 6 is knight
Yes, No, No $\implies$ 7 is knight
No, Yes, Yes $\implies$ 8 is knight
No, Yes, No $\implies$ 9 is knight
No, No, Yes $\implies$ 10 is knight
No, No, No $\implies$ 11 is knight

$\endgroup$
  • $\begingroup$ This is very close! However, I think your method needs a little tweaking (in your example, what if 4, 5 and 11 are all jokers?). I would also like to see an argument why it cannot be done with a smaller value of $k$. $\endgroup$ – Tyler Seacrest Jul 13 '15 at 22:12
  • 1
    $\begingroup$ @Tyler you only need 4 and 11. In fact you only need for the knight that is in all sets and the knight that is in no sets to be jokers for the approach as written to fail. (In the j=2 case, you get the wrong result if person 3 and person 6 are jokers) $\endgroup$ – Taemyr Jul 14 '15 at 7:32
  • $\begingroup$ Taemyr is right, this answer doesn't work.... so the accepted answer only gives us a lower bound without presenting a working strategy!!! $\endgroup$ – Falco Jul 15 '15 at 11:48
0
$\begingroup$

Misread the question at first, so had to edit it later. I hope that's correct:

When you ask someone "Is it true that only if you're lying/you're just going to lie, then [insert given bunch of guys] are all jokers?", you get an informative answer whether he's telling the truth or not. If he says yes, that means at least one of them must be a Knight. If he says no then they're all jokers. Since you can eliminate any group of people you want that way and are allowed to ask a limited amount of questions, it's more efficient to use binary search. Basically, $j >= log2(j+k), 2^j >= j+k$ and $2^j - j >= k$.

$\endgroup$
  • 1
    $\begingroup$ I appreciate your post -- this is probably the best solution assuming jokers are compelled to lie or tell the truth. But my jokers "can say yes or no", even if doing so creates a statement with no truth value. Thus you can't get any information from a joker even by your question. $\endgroup$ – Tyler Seacrest Jul 14 '15 at 3:35
  • $\begingroup$ That would mean it could be impossible to identify a knight if all the first $j$ people were jokers that could combine "yes" and "no" any way they want to cheat their way out of any question. $\endgroup$ – Nautilus Jul 14 '15 at 13:08
  • 1
    $\begingroup$ In hindsight, $k > j$, so we can always guarantee there's a knight among the remaining $k$ people and start our binary search with them. That makes $k = 2^j$. $\endgroup$ – Nautilus Jul 14 '15 at 15:45

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.