The basic setting for the knights and spies problem has a room of numbered people, each of whom is either a knight (who always tells the truth), or a spy (who may lie). We suppose that at least knights are present, where . In this joint paper with John R. Britnell, we showed that the minimum number of questions needed to find a knight is , where is the number of s in the binary expansion of . This generalizes an earlier result of Saks and Werman for the case , when all that is known is that knights are in the majority. Our result applies both to unconstrained spies (who answer as they see fit) and spies who always lie.
I recently finished writing another paper that determines the minimum number of questions to either find a spy, or correctly claim that no spy is present. This paper also solves a number of related problems. One result (see Theorem 4) is that when spies always lie, there is a questioning strategy that simultaneously solves each of the following searching games:
- Find at least one person’s identity;
- Find a knight;
- Find the identity of any nominated person;
- Find a spy (playing mole-hunter rules, when a spy is known to be present);
- Find a spy or correctly claim that no spies are present;
using the minimum possible number of questions for each game in isolation. In the case it is even possible to finish off by finding all identities in the optimal number of questions.
All the results so far are in the adaptive model in which each question may be chosen in the light of previous answers. An interesting paper by Aigner also considers predetermined questions, which must all be submitted in advance. Let be the minimum number of predetermined questions needed to find a knight when spies always lie. Aigner proves in his Theorem 5(b) that for all permitted and . Here is an outline of an alternative (but very similar) proof. Let be the maximum number of spies in the room.
In the adaptive model, a standard technique for finding a knight in an efficient way is to pick a candidate, and ask people about the candidate until either he is supported by people (and so must be a knight), or he is accused strictly more times than he is supported, in which case at least half the people involved in questions so far are spies. In the latter case ignoring all the people involved so far leads to an inductive situation.
In the predetermined model this strategy cannot be used because we do not know when to give up on a candidate. But the more relaxed target of questions means a modified version is still effective: simply ask Persons up to about Person . If he is supported times then he is a knight. If there are exactly supports and accusations then all spies have been involved in proceedings so far and Person is a knight. If there are at least accusations then Person is a spy (since people who act in the same way must all be knights); then any accuser of Person is a knight. Hence .
Any list of questions determines a graph on in which there is an edge if and only if either Person is asked about Person or vice versa. When spies always lie, one person supports another if and only if they are of the same type. So a connected component of the graph is completely determined (for our purposes) by its unique partition into people of opposite types. Choosing the parts so that , we define the weight of by .
Given a list of predetermined questions, the only relevant data are the sizes of the connected components it forces in the question graph, and the only decision to make is what weights to assign to these components. Suppose the components are , where has size , and we assign weight to component . Then at least of the people in are spies, so if we need , or equivalently . Hence for some .
We can assume that at most questions are asked, so we have . So the final condition above will always hold provided for each . Also for each we must have
- and ;
- (else the people in the larger part of have to be knights)
The obvious greedy approach is to take (depending on the parity of ) for each . If exactly of the components have even weight, this gives
If then and so (2) holds, otherwise for all so again (2) holds.
Finding a knight
The results already mentioned leave one case open. Let be the minimum number of predetermined questions needed to find a knight when spies are unconstrained. In Theorem 8 of Aigner’s paper, Aigner proves that where , and remarks that it is ‘quite plausible’ that equality holds for all and . Problem. Prove or disprove that
Finding all identities
Let and be the minimum number of questions needed to find all identities when spies always lie, or are unconstrained, respectively. Let and be the corresponding quantities for predetermined questions. Let . The following results are known.
- If where then where : see Theorem 4 in Aigner’s paper. If then and if then .
- . This was first proved by Blecher, and later (independently) by me.
- : see Theorem 5(c) in Aigner’s paper. The proof is similar to the proof that .
- : see Theorem 9 in Aigner’s paper. The proof starts by showing that any vertex of in degree in the question graph is ambiguous; then choosing questions so that is a directed tournament for each (wrapping around modulo ) reveals all identities against any combination of answers.
Determining the true values of in the remaining cases in (1) seems to be a tricky problem: see Section 8.1 in my paper for some discussion and computer data.