One Lie in a Thousand

Worked solution

The answer is 14. Lower bound (Berlekamp's volume argument). Fix a strategy with q questions. If the secret is x, the sequence of answers the questioner hears can be the truthful one or any of the q sequences with a single answer flipped: q + 1 sequences in all. Sequences arising from different secrets must be different, otherwise the questioner could not tell them apart. There are only 2^q answer sequences, so 1000(q + 1) ≤ 2^q. For q = 13 this reads 14000 ≤ 8192, false, while for q = 14 it reads 15000 ≤ 16384, true. So at least 14 questions are needed. Upper bound. Describe the game by a state (a, b): a candidates consistent with no lie so far and b candidates consistent with exactly one lie so far. Asking about a set S containing x of the first group and y of the second turns the state into (x, y + a − x) on a "yes" and (a − x, b − y + x) on a "no". The questioner wins when a + b ≤ 1. A dynamic program over all states, computing for each number q of remaining questions the largest solvable b for each a, shows that the start state (1000, 0) is winnable in 14 questions; in fact with 14 questions the state (1000, b) is winnable for every b up to 1384 = 16384 − 15000, exactly the slack in the volume bound. Hence the answer is 14. The volume bound is not always attained: it fails for some odd starting sizes (for example 585, which needs 14 questions although the bound allows 13), but Pelc proved that for an even number of candidates it is always tight, consistent with the computation for 1000.