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 1s 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: