Island of Knights, Knaves and Spies

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).
• I assume you are looking for a strategy that guarantees that you will know the identity of every islander with fewer than 2N questions even in the worst case. Correct? – Hugh Meyers Apr 25 '19 at 13:22
• ... and if so, then I suppose the worst case has to be that everyone is a knave thus making the second question valueless. – Hugh Meyers Apr 25 '19 at 13:27

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.

• It seems like there is a bit of a flaw: If we identify a spy, then we can't simply find which of the k are type X in k questions by asking the spy "is A_i of type X?" because we will get lies every other time. We are not allowed to ask "or" questions. – Bolton Bailey Apr 26 '19 at 7:57
• @BoltonBailey We know the truth/lie pattern, so we can just negate the lies. – noedne Apr 26 '19 at 8:17
• You can't just negate the lies. You are only allowed to ask questions of the given forms, not their negations. – Bolton Bailey Apr 26 '19 at 8:20
• @BoltonBailey Negate the answer, not the question. – noedne Apr 26 '19 at 8:21
• Yep. That works. – Bolton Bailey Apr 26 '19 at 8:22

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.

• Could you elaborate on your last paragraph? I'm not convinced that a binary search is possible under the restrictions of the questions - how would it be done? – hexomino Apr 25 '19 at 19:55
• That being said, this answer is pretty useful as I think it provides a lower bound. It's pretty close to noedne's answer which makes me think that is the best that could be achieved. – hexomino Apr 25 '19 at 20:00
• @hexomino We know both the biggest and smallest possible N-digit trinary numbers: N^3-1 and 0. Take the halfway point, ask if the number I described in my answer is greater or lesser than, then repeat on the reduced range. – Vincent B. Lortie Apr 26 '19 at 2:17
• It's not clear to me that this question about the trinary number can be asked in the form of one of the two questions types allowed. – Bolton Bailey Apr 26 '19 at 8:34
• @VincentB.Lortie Yes, I agree with what Bolton Bailey says, you are only permitted to ask either "Is A_i a knight/knave/spy?" or "How many among you are knights/knaves/spies?" You are not permitted to ask questions about a trinary number. – hexomino Apr 26 '19 at 9:03

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$$

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

• I think if #1 is a knight we still need 2N-2 questions because you can only ask questions like "Is A_j a knight?" not "What is A_j?" meaning that in the worst case you would still need two questions to determine each one, right? – hexomino Apr 25 '19 at 14:02
• oh, damn, I misread the question. You're right; we don't get to ask "what is X?" questions at all. – Gareth McCaughan Apr 25 '19 at 14:03

The minimum number of questions needed is

2, but only if you're lucky

How?