logical deduction - Knights and jokers

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

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.