I pick a whole number from 1 to 1000. You ask adaptive yes or no questions and I answer, but I am allowed to lie at most once. What is the least number of questions that always determines my number?

I pick a whole number from 1 to 1000. You ask adaptive yes or no questions and I answer, but I am allowed to lie at most once. What is the least number of questions that always determines my number?

Approach: Count the states that must remain separable, remembering that a candidate can be alive either with the lie unused or with the lie already spent at any one of the answers so far.

14. After q questions a candidate is described by the number itself plus which answer, if any, was the lie, so the answer strings must separate 1000 * (q + 1) states, giving 2^q >= 1000 * (q + 1). At q = 13 that reads 8192 >= 14000 and fails, at q = 14 it reads 16384 >= 15000 and holds, so 14 is the information bound. It is achievable by the weight strategy: give each surviving candidate weight 2^{-r} where r counts how many of the remaining questions it can still afford to have answered wrongly, and ask a question that halves the total weight as evenly as possible. With no lie allowed the answer is 10, so one lie costs 4 extra questions. The same inequality is the Hamming bound for a one error correcting code, with adaptive questions replacing a fixed codebook.

Follow-up: How many questions are needed for 1 to 1000 when I am allowed to lie twice?

Key concepts: information bound, adaptive questions, error correcting code, hamming bound.