Island of Knights, Knaves and Spies

Question

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

Update (some clarifications):

1. As usual, the question is about the worst case (i.e. a strategy that guarantees the identifying after specified number of questions (with 100% probability)).
2. All islanders know the identities of each other.
3. Groups cannot be subdivided (the "second-type" question always refer to the whole set).

Answer 1

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.

Answer 2

Assuming inhabitants know the identity of other inhabitants and a bit of math, for N inhabitants, I believe you could find the identity of every inhabitant with a number of questions approximately equal to

$3 + \frac{(N - 1) * log(3)}{log(2)}$

Here's how:

Take aside one inhabitant and figure out, using the 2 questions in the question to determine whether the inhabitant is a knight, a knave or a spy.

.

If faced with a spy, ask, as a third question, whether or not he or she is a spy. This will tell you which "phase" the spy is in, allowing you to determine the truth value of future answers. If the spy says he is not a spy, then that is a lie, and his next answer will be the truth. If the spy admits to being a spy, his next answer will be a lie, and so on.

.

You now have one person you can use to find out the true answer to any question. (Taking the negation if you have a knave) Let's hope this person is patient and knows a bit of math. You will be asking him a series of questions.

.

You will line up all of the other N-1 inhabitants and ask the inhabitant whose identity has been determined to compute a trinary number where each trinary digit corresponds to one of the other N-1 inhabitants: 0 if the inhabitant is a knight, 1 if a knave and 2 if a spy. For a trinary number with N-1 digits, there are $3^{N-1}$ possibilities. A binary search will then allow you to eliminate half of these possibilities with a single question, repeating until there is only one option.

Answer 3

Some upper bounds on the number of questions needed have been provided. Here is a lower bound:

Based on information theory. Suppose that $N = 3k$ and that before our interrogation, we are told that the true number of knights, knaves and spies are each $k$. Thus, asking questions of the second kind is equivalent to querying whether a individual is telling the truth this round. This imparts 1 bit of information. Similarly, questions of the first kind impart 1 bit of information, because they are Yes/No questions. Since the total number of possibilities is $\binom{3k}{k,k,k} \ge (3k/k)^k(2k/k)^k = 6^k$, we will still need $\log_2 6^k = k \log_2 6 = N \frac{1}{3} \log_2 6 \approx N * 0.86$

Answer 4

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 $\left\lceil\frac{N-2}3\right\rceil$ groups of at most 3, and use 4 questions for each group, for a total of $\left\lceil\frac{N-2}3\right\rceil+5$ questions. I make no claim that this is optimal, though.

Answer 5

The minimum number of questions needed is

2, but only if you're lucky

How?

You ask the first person:
"Are you a spy?"
"No."
"How many knights are there?"
"N"

After the first question, they're either a knight or a lying spy. Either way, the next answer will be truthful. And since that truthful answer indicated that everyone is a knight, clearly they're also a knight. And you're done! They're all knights!