One Lie in a Thousand

A responder secretly picks an integer from 1 to 1000. A questioner asks yes/no questions, each of the form "Is your number in the set S?" for any set S of the questioner's choice, chosen adaptively after hearing earlier answers. The responder answers each question, but may lie at most once in the entire game (possibly never), and may choose adversarially which answer, if any, to falsify. At the end the questioner must name the number with certainty. What is the minimum number of questions that suffices in the worst case?

• combinations
• combinatorial games

Source: The Renyi-Ulam searching game with a lie, studied by Berlekamp, Pelc and others; the volume bound is standard. Statement written for AxiomIQ.