7
$\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.)

Improve this question
$\endgroup$
9
  • $\begingroup$ is it assumed that the first $j$ people contains at least one knight? $\endgroup$
    – Bob
    Commented Jul 13, 2015 at 19:42
  • 1
    $\begingroup$ @Bob: No; you could be asking your questions to all jokers. $\endgroup$
    – Tyler Seacrest
    Commented Jul 13, 2015 at 19:45
  • $\begingroup$ So it might be impossible to obtain any reliable information. $\endgroup$
    – Bob
    Commented Jul 13, 2015 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
    Commented Jul 13, 2015 at 19:51
  • 1
    $\begingroup$ @Taemyr no reliable answer would be more accurate wouldn't it? $\endgroup$
    – Bob
    Commented Jul 14, 2015 at 8:41

4 Answers 4

Reset to default
5
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 15, 2015 at 4:12
6
$\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

Improve this answer
$\endgroup$
9
  • $\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
    Commented Jul 13, 2015 at 22:12
  • 3
    $\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
    Commented Jul 14, 2015 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
    Commented Jul 15, 2015 at 11:48
  • $\begingroup$ @Taemyr , can you provide a correct solution ? Please also explain the logic behind your solution . $\endgroup$
    – Hemant Agarwal
    Commented Jan 15, 2023 at 5:03
  • 1
    $\begingroup$ @HemantAgarwal: I don't see an easy fix to this answer. When you ask a knight if a bunch of people are knights and he says no you get very little information. I think that is the real source of the problem and a different approach is needed. $\endgroup$
    – Ross Millikan
    Commented Jan 15, 2023 at 16:25
6
$\begingroup$

Lopsy has given a proof of the lower bound for $k$.

celtschk gave a method to achieve this bound but, as shown in the comments, it is flawed (even in the case $j=2$).

Here is an inductive method to achieve the bound

$k=2^j$

Base step

As shown by celtschk, if $j=1$ and $k=2$, we may simply ask the first person if the second person is a knight. If person 1 says "yes" then person 2 is a knight. If person 1 says "no" then person 3 is a knight.

Inductive step

Now let us assume we have a method to identify a knight amongst a group of $j-1$ jokers and $2^{j-1}$ knights by asking "yes/no" questions of the first $j-1$ members of this group.

Now suppose we have a group of $j$ jokers and $2^j$ knights. Let us call the group of $j$ people to which we ask questions as group $J$ and the remainder of the people as group $K$. Divide group $K$ into two groups of equal size, $K_1$ and $K_2$.

Ask the first person in group $J$, "Are there more knights in group $K_1$ than in group $K_2$?".

If they say "yes" then the remainder of the group $J$ combined with $K_1$ contains at most $j-1$ jokers.
If this person says "no" then the remainder of the group $J$ combined with $K_2$ contains at most $j-1$ jokers.

In either case, we produce a group of size $2^{j-1} + j-1$ with, at most, $j-1$ jokers. By the assumption, we know how to identify a knight in this group, as any method which will work for $j-1$ jokers will also work for fewer.

Example $j=2$

Here $K_1$ would contain persons 3 and 4, while $K_2$ contains persons 5 and 6.

We ask person 1 if there are more knights in $K_1$ than in $K_2$.

If they say "yes", then we ask person 2 if person 3 is a knight. "yes" would imply person 3 is a knight, "no" would imply person 4 is a knight.

If person 1 says "no", then we ask person 2 if person 5 is a knight. "yes" would imply person 5 is a knight, "no" would imply person 6 is a knight.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you soo much. I understood it as well. Two questions 1) Is there a way to solve this by fixing Celtschk's answer ? The OP had commented under Lopsy's answer that Celtschk has made a minor mistake that can be easily fixed. 2) Is there a way to solve this without induction ( using binary numbers or something else ) ? Thanks again. $\endgroup$
    – Hemant Agarwal
    Commented Jan 16, 2023 at 11:13
  • 1
    $\begingroup$ @HemantAgarwal Unfortunately, I don't know what the simple fix would be for Celtschk. I think the answer is aiming to map each person to a binary number which will correspond to a set of questions but this is trickier in this case than it first looks. I thought about it for a while but so far I haven't come up with a fix. $\endgroup$
    – hexomino
    Commented Jan 16, 2023 at 11:21
  • 1
    $\begingroup$ I have spent quite some time trying to solve this question but failed and felt frustrated. Really appreciate this answer of yours. If other methods of solving this question strike you, then do please consider sharing. Thanks again. $\endgroup$
    – Hemant Agarwal
    Commented Jan 16, 2023 at 17:27
  • 1
    $\begingroup$ @HemantAgarwal hexomino's strategy can work without induction as well. Note that every time a Knight is questioned we eliminate at least one Joker from the pool (unless there are none left) and that for every Joker that starts in the pool we will have a Knight to question. Thus we are guarenteed to have eliminated every Joker when we are done with our questions. $\endgroup$
    – GoblinGuide
    Commented Jan 17, 2023 at 4:42
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$.

Improve this answer
$\endgroup$
3
  • 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
    Commented Jul 14, 2015 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
    Commented Jul 14, 2015 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
    Commented Jul 14, 2015 at 15:45

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.