Sniff Out the Traitorous Generals

You command $N$ generals. More than half are loyal and the rest are traitors. You may ask any general about the loyalty of any other: a loyal general always answers truthfully, but a traitor may answer however he likes. You want to name one general you are certain is loyal, while asking as few questions as possible. What is the fewest questions that guarantees success, in terms of $N$, and what strategy achieves it?

The Riddler, FiveThirtyEight(original post)

Solution

The idea that cracks it is a chain of forced conclusions. Suppose general $B$, asked about general $A$, answers “$A$ is loyal.” If $B$ were loyal he would be telling the truth, so the only way that answer can be a lie is if $B$ is himself a traitor. In other words, a single “loyal” answer buys the implication $$A \text{ is a traitor} \;\Longrightarrow\; B \text{ is a traitor}.$$ Stack enough of these and you can corner a loyal general. Here is the strategy, due to the puzzle’s submitter, Django Wexler.

Keep a counter $K$, started at $\lfloor N/2\rfloor$. Because loyalists are a strict majority, the number of traitors is at most $\lfloor N/2\rfloor$, so $K$ is an honest ceiling on how many traitors can still be hiding in the pool. Hold a candidate general $A$ and grow a chain behind him.

Take a fresh general $G$ from the pool and ask him about the current end of the chain.

• If $G$ says “loyal,” the implication above extends the chain: if the chain’s end is a traitor then $G$ is a traitor, and following the links back, if $A$ is a traitor then every general in the chain, now including $G$, is a traitor. Append $G$ and continue.

• If $G$ says “traitor,” then at least one of $G$ and the chain’s end is a traitor (a loyal $G$ would be telling the truth, and a lying $G$ is himself the traitor). Discard both, and drop $K$ by one, since you have removed at least one traitor from the pool. The chain loses its end; if it empties, start a new candidate from the pool.

Two things can happen, and both finish the job.

• The chain grows longer than $K$. Then “$A$ is a traitor” would force more than $K$ traitors, which is more than can exist. So $A$ is loyal.

• The counter $K$ reaches zero. Every traitor has been thrown out in a discarded pair, and since loyalists were a majority the pool is not empty; whoever is left is loyal.

Now count the questions. Each “traitor” answer removes two generals using one question; each “loyal” answer brings one new general into the chain using one question. Either way, a question is spent only when a fresh general is drawn from the pool, every general is drawn at most once, and the general you finally certify is never the one you had to ask. So you spend at most $$\boxed{N-1}$$ questions, and this is also the fewest possible. The reason you cannot do better is that each question ties together exactly two generals, and to end up certain about one general every general must be linked into a single connected web of questions; joining $N$ generals into one connected web takes at least $N-1$ ties. With fewer, some group of generals is never linked to the rest, and an adversary is free to make that group’s answers consistent with its members being traitors, leaving no one you can name for certain.

The computation

Encode the rules and let an adversary fight back. Across every assignment of loyalties with a loyal majority, and many random traitor-answer strategies for each, run the algorithm and check two things: the general it names is genuinely loyal, and it asked at most $N-1$ questions.

1. Loyal generals answer with the truth; traitors answer arbitrarily.

2. Keep $K=\lfloor N/2\rfloor$ and a chain seeded with one general.

3. Ask a fresh general about the chain’s end; “loyal” extends the chain, “traitor” discards both and lowers $K$ (reseeding the chain if it empties).

4. Stop when the chain is longer than $K$, or the pool runs out; return the chain’s head.

import random, itertools, collections

def find_loyal(N, loyal, answer):
    pool = collections.deque(range(N))
    K = N // 2                       # safe ceiling on the traitor count
    chain = [pool.popleft()]         # head a traitor => whole chain traitors
    questions = 0
    while True:
        if len(chain) > K or not pool:
            return chain[0], questions
        g, tail = pool.popleft(), chain[-1]
        questions += 1
        if answer(g, tail):          # g calls the chain's end loyal
            chain.append(g)
        else:                        # discard both; one traitor removed
            chain.pop(); K -= 1
            if not chain:
                chain = [pool.popleft()]

def make_answer(loyal):
    def answer(asker, about):
        return loyal[about] if loyal[asker] else (random.random() < 0.5)
    return answer

random.seed(0)
for N in (3, 5, 7, 9):
    failures = 0
    for loyal in itertools.product([True, False], repeat=N):
        if sum(loyal) * 2 <= N:          # require a strict loyal majority
            continue
        for _ in range(200):             # adversarial traitor answers
            who, q = find_loyal(N, loyal, make_answer(loyal))
            if not loyal[who] or q > N - 1:
                failures += 1
    print(f"N={N}: failures={failures}")
# N=3: failures=0
# N=5: failures=0
# N=7: failures=0
# N=9: failures=0