Vrftsjtryk

There is an island with $N$ inhabitants (for example $A_1, A_2, dots, A_N$), each of them is either a knight, a knave, or a spy. As usual:

• 
  knights will always tell the truth upon answering a question,


• 
  knaves will always lie,


• and spies can do both (however they always alternate the truth value of their answers, i.e. if they lied they definitely will tell the truth upon the next answer, and vice versa).

You must determine the correct identities of all $A_i$'s by asking questions, which have to be of one of the following forms:

• Is $A_j$ a knight/knave/spy? (It includes the $i=j$ case, so you particularly can ask "Are you a knight/knave/spy?") The answer will be either "yes" or "no".


• How many knights/knaves/spies are among you? The answer will be an integer between $0$ and $N$, inclusively (so, for example for $N=20$, even a knave wouldn't answer $25$, $-3$, or $8.5$).

It's very easy to construct a solution with $2N$ questions, namely asking each islander twice: "Are you a spy?", because

• a knight will say "no" at both times (since knights never lie, and a knight is indeed not a spy),


• a knave will say "yes" both times (vice versa, a knave always lies, and still isn't a spy),


• and a spy will give different answers each time (because spies never lie or tell the truth twice in a row).

So, after 2 questions we can reveal the identity of one given islander.

The question to this puzzle is: Can the number of questions be less than $2N$, and if it can, what's the minimum number of questions needed? (In the solution above, the second type of questions was not even used.)

It takes

at most about $5N/3$ questions.

Suppose

we know a knight or spy and want to find the identities of $k$ islanders. We can find the division of $k$ into knights, knaves, or spies by asking the knight/spy at most five questions of the second type. Suppose the most represented type is X. Then we ask the knight/spy whether each of the $k$ is X. This determines exactly which of them is X, so we can determine the remainder by asking the knight/spy whether each of them is one of the remaining types. In the worst case, each of the classes is equally represented among the $k$, so that this takes about $5k/3$ questions.

Now

our strategy is to find a knight/spy. First we use the known two question strategy to determine the identity of an islander. If they are a knave, we keep asking them whether other islanders are knaves. Each knave discovered in this way requires only one question, so in the worst case we quickly discover a knight/spy, and we use about $5N/3$ questions in total.

Wrong answer

[EDITED to add:] Oops, the following is all wrong; thanks to @hexomino for pointing out in comments that I misinterpreted the question. I'm leaving this here rather than deleting it because (1) it's possible that some idea in it is salvageable and (2) I don't believe in making myself look better by deleting my mistakes :-). (I might delete it later to reduce clutter.)

The minimal number of questions

is less than $2N$, at least when $N$ is not too small. In fact, it's never more than $frac43N$ plus a few.

Here's why.

First, use two "are you a spy?" questions to establish what #1 is, and also (if they're a spy) which way around their truth-telling and lying answers are. We now have three cases. If #1 is a knight then we can just ask them about everyone else, and we're done in $N+1$ questions. If #1 is a spy then we ask them about everyone else -- once, asking "what is X?", when they are telling the truth, and twice, asking binary questions, when they are lying. Every 4 questions we find out about 3 people, so we take approximately $frac43N$ questions.

The hardest case is when #1 is a knave. Here's one way to proceed. Ask them "is X a knave?" about each other person in turn. If they say "no" then we have correctly identified that X is a knave, and if that's all that ever happens then again we're done in $N+1$ questions. If at some point they say "yes" then we have found a non-knave. We can then ask that person two questions to figure out exactly what they are and (if they're a spy) what their "phase" is, and then proceed as above, asking them about everyone else in turn.

In the worst case: we take two questions to establish that #1 is a knave; we take one more question to establish that #2 is knot a knave; we take two questions to establish that #2 is a spy and phind his phase; we then have $N-2$ people to figure out, divide them into $leftlceilfrac{N-2}3rightrceil$ groups of at most 3, and use 4 questions for each group, for a total of $leftlceilfrac{N-2}3rightrceil+5$ questions. I make no claim that this is optimal, though.