Finding a knight with predetermined questions

The basic setting for the knights and spies problem has a room of $n$ 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 $k$ knights are present, where $n/2 < k < n$. In this joint paper with John R. Britnell, we showed that the minimum number of questions needed to find a knight is $2(n-k)-B(n-k)$, where $B(r)$ is the number of $1$s in the binary expansion of $r \in \mathbb{N}$. This generalizes an earlier result of Saks and Werman for the case $n=2k-1$, 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 $n=2k-1$ it is even possible to finish off by finding all identities in the optimal number of $n-1$ questions.

Predetermined 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 $K^p_L(n,k)$ be the minimum number of predetermined questions needed to find a knight when spies always lie. Aigner proves in his Theorem 5(b) that $K^p_L(n,k) = 2(n-k) - 1$ for all permitted $n$ and $k$. Here is an outline of an alternative (but very similar) proof. Let $s = n-k$ be the maximum number of spies in the room.

Upper bound

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 $s$ 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 $2s-1$ questions means a modified version is still effective: simply ask Persons $1$ up to $2s-1$ about Person $2s$. If he is supported $s$ times then he is a knight. If there are exactly $s-1$ supports and $s$ accusations then all $s$ spies have been involved in proceedings so far and Person $2s+1$ is a knight. If there are at least $s+1$ accusations then Person $2s$ is a spy (since $s+1$ people who act in the same way must all be knights); then any accuser of Person $2s$ is a knight. Hence $K^p_L(n,k) \le 2s-1$.

Lower bound

Any list of questions determines a graph on $\{1,\ldots, n\}$ in which there is an edge $\{i,j\}$ if and only if either Person $i$ is asked about Person $j$ 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 $C$ of the graph is completely determined (for our purposes) by its unique partition $C = A \cup B$ into people of opposite types. Choosing the parts so that $|A| \ge |B|$, we define the weight of $C$ by $w(C) = |A|-|B|$.

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 $C_1, \ldots, C_t$, where $C_i$ has size $c_i$, and we assign weight $w_i$ to component $C_i$. Then at least $(c_i - w_i)/2$ of the people in $C_i$ are spies, so if $n = 2s + e$ we need $\sum_{i=1}^t (c_i-w_i)/2 \le s$, or equivalently $\sum_{i=1}^t w_i \ge n-2s=e$. Hence $\sum_{i=1}^t w_i = 2s' + e$ for some $s' \in \mathbb{N}_0$.

We can assume that at most $2s-2$ questions are asked, so we have $t \ge n - (2s-2) = e+2$. So the final condition above will always hold provided $w_i \in \mathbb{N}$ for each $i$. Also for each $i$ we must have

1. $w_i \in \{c_i,c_i-2,\ldots \}$ and $w_i \ge 0$;
2. $w_i \le s'$ (else the people in the larger part of $C_i$ have to be knights)

The obvious greedy approach is to take $w_i \in \{1,2\}$ (depending on the parity of $c_i$) for each $i$. If exactly $\alpha$ of the components $C_i$ have even weight, this gives

$\sum_{i=1}^t w_i = 2 \alpha + (t-\alpha) = t + \alpha$

hence

$s' = (t+\alpha-e)/2 \ge (e+2+\alpha-e)/2 = 1 + \alpha.$

If $\alpha \ge 1$ then $s' \ge 2$ and so (2) holds, otherwise $w_i = 1$ for all $i$ so again (2) holds.

Open problems

Finding a knight

The results already mentioned leave one case open. Let $K^p_S(n,k)$ 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 $K^p_S(n,k) \le \lfloor s^2 \rfloor + s$ where $s = n-k$, and remarks that it is ‘quite plausible’ that equality holds for all $n$ and $k$. Problem. Prove or disprove that

$K^p_S(n,k) = \lfloor s^2 \rfloor + s$

where $s = n-k$.

Finding all identities

Let $A_L(n,k)$ and $A_S(n,k)$ be the minimum number of questions needed to find all identities when spies always lie, or are unconstrained, respectively. Let $A^p_L(n,k)$ and $A^p_S(n,k)$ be the corresponding quantities for predetermined questions. Let $s = n -k$. The following results are known.

1. If $n = q(s+1) + r$ where $r \in \{0,\ldots, s\}$ then $A_L(n,k) = n - q + \epsilon_{(n,k)}$ where $\epsilon_{(n,k)} \in \{0,1\}$: see Theorem 4 in Aigner’s paper. If $r \in \{0,1\}$ then $\epsilon_{(n,k)} = 1$ and if $r = s$ then $\epsilon_{(n,k)} = 0$.
2. $A_S(n,k) = n + (n-k) -1$. This was first proved by Blecher, and later (independently) by me.
3. $A^p_L(n,k) = \lceil 2sn/(2s+1) \rceil$: see Theorem 5(c) in Aigner’s paper. The proof is similar to the proof that $K^p_L(n,k) = 2s-1$.
4. $A^p_S(n,k) = (n-k)n$: see Theorem 9 in Aigner’s paper. The proof starts by showing that any vertex of in degree $< n-k$ in the question graph is ambiguous; then choosing questions so that $\{i,i+1,\ldots, i+n-k\}$ is a directed tournament for each $i$ (wrapping around modulo $n$) reveals all identities against any combination of answers.

Determining the true values of $\epsilon_{(n,k)}$ 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.