Knights and jokers

Question

There are $N$ men. $K$ of them are knights, $M$ of them are jokers.

$N$ is known, $K$ and $M$ are unknown. You know that: $K + M = N$, $K \gt M$, $M \ge 1$, $N$ is odd.

Knights always tell the truth, jokers can tell whatever they want. All $N$ people know who is who. You go to anyone of them and ask him a yes-or-no question. You can repeat this procedure any number of times with the same man or with different men. It is not allowed to ask a question which the man is not able to answer with "Yes" or "No".

1. How to determine who is who if you can ask only $2N$ questions?
2. How to determine who is who with the minimum number of questions?

Explanations:

1. Each joker chooses what to tell according to unknown arbitrary algorithm. Examples of such algorithms: "Always tell Yes", "Throw a dice and tell Yes only if you throw a one, otherwise tell No.", "If it is raining tell Yes, otherwise tell No."

2. One question is asked to only one man and results in one answer (which provides 1 bit of information).

I do not know the author's solution. I have figured out a solution by my own, and now I would like to check whether it is correct. For this I need someone who figured out it independently. Also I don't have prove of optimality in b).

To show that the puzzle is "objective" and result is achievable, here is the solution for the case $N = 3$:

In this case there are 2 knights and 1 jokers.
1. Ask the first one "Is the second man a knight?". If he answers "Yes" then the 2nd is a knight. Indeed, let's suppose second is joker, then 1st is knight and he lied. If he answers "No" then 1st or 2nd is a joker and third is knight.
2. Ask the found knight "Is the first one a knight?" and you will identify one more person, the identity of the last one is derived from the fact that there is exactly one joker.
3. You need to identify 3 persons, which is 8 combination. $KKK, JJK, JKJ, KJJ, JJJ$ are discarded by condition $K \gt M, M \ge 1$, that leaves us with 3 combinations. So you can't do it in less than 2 questions - this is the minimum.

Answer 1

The minimum number of questions of the special form “Person $i$, is Person $j$ a knight?” that will guarantee to find everyone's identity is $3(N-1)/2$. This was first proved by P. Blecher in this paper.

Suppose we know for sure that at most $J$ jokers are present, where $J < N/2$. My paper on the problem shows that $N+J-1$ is the minimum number of questions that will guarantee to find everyone's identity. Taking $J$ to be $(N-1)/2$ recovers Blecher's result. My webpage on the problem gives an overview of the solution. These slides might also be of interest.

The easier part is to show that $N+J-1$ questions suffice. The strategy used in my paper and in Blecher's is the same. Set $T$ equal to $J$. Pick one person (call him a candidate), and ask other people about him until either

• for some $r$, the candidate has been accused $r$ times and supported $r-1$ times, or
• the candidate has been supported by at least $T$ people.

In the first case either the candidate is a knight, and he has been falsely accused by $r$ jokers, or the candidate is a joker, who has been rightly accused by $r-1$ people (who might be knights or jokers). Either way, at least $r$ of the $2r$ people involved are jokers. We may therefore ignore all these people, and repeat with a fresh candidate, replacing $T$ with $T-r$.

Eventually we end in the second case with a successful candidate, who must be a knight. Use this knight to identify the unsuccessful candidates (this will reveal some jokers), and finally use the knight to identify all the remaining people whose identity is still ambiguous.

Here is a special case of the argument that this strategy uses at most $N+J-1$ questions. Suppose that the first candidate is successful, after he is supported by $J$ people, and accused by $A$ people. These $A$ people must be jokers. We now ask the first candidate about the $N-J-A-1$ people not yet involved in proceedings, and the $J$ people who supported him. The total number of questions asked is $ J+A + (N-J-A-1) + J = N-1 +J $ as required.

The hard part is to show that no questioning strategy, no matter how clever, can guarantee to use fewer than $N+J-1$ questions. For this I like to this of the problem as a two player game: the Interrogator poses the questions, and the Spy Master (or Joker Master in this setting) decides on the answers. The job of the Spy Master is to arrange matters so that the Interrogator faces the worst-case scenario for his strategy. The Knight Hiding Strategy in my paper is an optimal strategy for the Spy Master that holds the Interrogator to the target of $N+J-1$ questions. Following this strategy, the first question is answered with an accusation, so at least one Joker is present.

More general questions. My guess is that allowing more general yes/no questions does not permit a quicker solution. But I do not have a proof of this.

Answer 2

Here is the solution I found. Please tell, if you see any mistakes.

Let's call $M'$ maximum number of jokers, which can be among group of chosen $N'$ man according to our knowledge.
Our start group will include all men, $N' = N$. Our knowledge is that $K+M=N, K>M$, therefore $M'= (N-1)/2$.

The goal is to find a chain from $(M'+1)$ men, such that each men in the chain tells about the next one that he is a knight. The last man in the chain will be a knight.
Indeed, there are only $M'$ jokers, therefore at least one man in the chain is a knight. If one man is a knight, then he doesn't lie and men next to him is knight too. Therefore all men after very first knight in the chain are knights.

To achieve this goal we take an arbitrary man, he will be first in the chain, and ask him about random man: "Is he a knight?". If answer is "Yes" we add that new man in the chain and continue.
If at some point the answer is "No" we take that new man and the asked man and exclude them from the chain and from our group. In this case we set $N'=N'-2$ and $M'=M'-1$, since at least one from the excluded two men is joker. [Note, that here we obtain exactly the same puzzle, but with less number of men].

With each question we need one less men to finish the chain, also we can lose one man in the chain in case the answer is "No". Therefore at most in $2\cdot(N-1)/2$ questions the chain will be completed and we will find a knight. [Even if $N'=1$ and $M'=0$, and the chain consists from only one man.]

Then we should ask the knight about all other men. This will take another $(N-1)$ questions. In total $2\cdot(N-1)$ questions.

---

Some kind of proof of optimality [This given for an old answer, which was $3/2\cdot(N-1)$ and appeared to be incorrect. I hope I will find more optimal strategy later.]:
1. Until we found a knight we can't get any concrete information.
2. There are $(N-1)/2$ jokers, therefore if we unlucky all very first $(N-1)/2$ questions can be asked to jokers and will not give us any information about who is knight and who is not. Therefore we need at least $(N-1)/2$ questions before we found a knight.
3. First $(N-1)/2$ questions haven't get us any concrete information and now to determine who is who we need at least one more question about other men: $(N-1)$ questions. 4. In total we need at least $3/2\cdot(N-1)$ questions. I understand that there is difference between "concrete" and "useful" information. And this is a week place in the prove, that's why I call it "kind of prove".

Answer 3

I've figured out how to solve it with no more than $2(N-1)$ questions.

To do a test, ask one man whether a second man is a Knight. Then ask the second man whether the first one is a Knight. This produces one of two results: They both say "Yes", or at least one says "No". We'll call this $Q(n)$, defined as "Ask men $n$ and $n+1$ about each other").

In the scenario where at least one says "No": At least one of the two is a Joker. We'll call this $D$.
In the scenario where both say "Yes": Either both are Knights or both are Jokers. We'll call this $B$.

For example, with $N=5$:

Test the following pairs, for a total of $2(5-1) = 8$ questions:

$$ Q(1) = 1 \leftrightarrow 2 \\ Q(2) = 2 \leftrightarrow 3 \\ Q(3) = 3 \leftrightarrow 4 \\ Q(4) = 4 \leftrightarrow 5 $$

This will produce a set of 4 scenarios, each of which is $B$ or $D$. At that point, each possible combination (except ${B,B,B,B}$) will map to one of the 15 possible combinations of 3-4 Knights and 1-2 Jokers.

For example: \begin{equation} \left. \left. \begin{aligned} Q(1) = B\\ Q(2) = B\\ Q(3) = D\\ Q(4) = D \end{aligned} \right\} = {K,K,K,J,K} \right.\quad\quad \left. \begin{aligned} Q(1) = D\\ Q(2) = B\\ Q(3) = D\\ Q(4) = D \end{aligned} \right\} = {J,K,K,J,K} \end{equation}

I'm sure there's a relationship between the results and where the Jokers are, but I'm not seeing it. However, the numbers work out: The number of potential combinations is ${{K,J} \choose N} = {2 \choose N} = 2^N$, and the number of invalid combinations is ${{2^N}\over2}+1$ (because half of the combinations have more jokers than knights, and one combination has no jokers at all). So $2^N-\left({{2^N}\over2}+1\right) = {(2^N)\over2}-1 = 2^{N-1}-1 $. This means that $N-1$ bits is enough to encode all possible cases (with one left over for the impossible "No jokers" case).

$D$ and $B$ each represent one bit of data, so we need $N-1$ trials to encode one set of Jokers and Knights.

This solution will scale up for any $N$ - you just need to start with $Q(1)$ and continue until you're asking $Q(N-1)$.