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):
- 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)).
- All islanders know the identities of each other.
- Groups cannot be subdivided (the "second-type" question always refer to the whole set).