BTW, this problem is known as the Ulam(-Renyi) liar problem or Ulam's searching game (or just "playing Twenty Questions with a liar"), and has an extensive literature. The following is a survey as of 2002:

• Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2^q/(q+1), which for n=1000 is indeed 14. There are alternative solutions to the one-lie game in more recent papers like this and this. As observed by Peter Shor in a comment above, the general adaptive strategy when multiple lies are allowed does not look like Hamming codes.

Edit: Since this has been bumped up, I may as well mention a nice result in the more general setting, proved by Joel Spencer and Peter Winkler in their paper Three Thresholds for a Liar.

It is traditional to name the two players Paul and Carole, where Paul (named after Paul Erdős) is the one who asks the questions, and Carole (an anagram of oracle) is the one who answers them. Paul asks $q$ questions in all, and Carole is allowed to lie a fraction $r$ of the time. We will consider three progressively harder (for Paul) versions of this what means. In Version A, Carole is allowed to lie at most $\lfloor ri\rfloor$ times to the first $i$ questions, for all $i$. In Version B, Carole is only required to lie at most $\lfloor rq \rfloor$ times in total — she can choose to exhaust all her lies at the beginning, for instance. In Version C (nonadaptive), Paul must ask all his questions in one batch, and Carole can choose up to $\lfloor rq \rfloor$ ones to lie to.

Note that if no lies are allowed ($r = 0$), the number of questions needed is exactly $\lceil \log_2 n\rceil$, and that, intuitively, if $r$ is too large, Paul cannot guess correctly at all. Specifically, they show that:

• In version A, Paul wins with $\Theta(\log n)$ questions if $r < 1/2$, but Carole wins if $r \ge 1/2$.
• In version B, Paul wins with $\Theta(\log n)$ questions if $r < 1/3$, but Carole wins if $r \ge 1/3$.
• In version C, Paul wins with $\Theta(\log n)$ questions if $r < 1/4$, Carole wins if $r > 1/4$, and if $r = 1/4$, Paul wins but needs $\Theta(n)$ questions.

BTW, this problem is known as the Ulam(-Renyi) liar problem or Ulam's searching game (or just "playing Twenty Questions with a liar"), and has an extensive literature. The following is a survey as of 2002:

• Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2^q/(q+1), which for n=1000 is indeed 14. There are alternative solutions to the one-lie game in more recent papers like this and this. As observed by Peter Shor in a comment above, the general adaptive strategy when multiple lies are allowed does not look like Hamming codes.

Edit: Since this has been bumped up, I may as well mention a nice result in the more general setting, proved by Joel Spencer and Peter Winkler in their paper Three Thresholds for a Liar.

It is traditional to name the two players Paul and Carole, where Paul (named after Paul Erdős) is the one who asks the questions, and Carole (an anagram of oracle) is the one who answers them. Paul asks $q$ questions in all, and Carole is allowed to lie a fraction $r$ of the time. We will consider three progressively harder (for Paul) versions of what this means. In Version A, Carole is allowed to lie at most $\lfloor ri\rfloor$ times to the first $i$ questions, for all $i$. In Version B, Carole is only required to lie at most $\lfloor rq \rfloor$ times in total — she can choose to exhaust all her lies at the beginning, for instance. In Version C (nonadaptive), Paul must ask all his questions in one batch, and Carole can choose up to $\lfloor rq \rfloor$ ones to lie to.

Note that if no lies are allowed ($r = 0$), the number of questions needed is exactly $\lceil \log_2 n\rceil$, and that, intuitively, if $r$ is too large, Paul cannot guess correctly at all. Specifically, they show that:

• In version A, Paul wins with $\Theta(\log n)$ questions if $r < 1/2$, but Carole wins if $r \ge 1/2$.
• In version B, Paul wins with $\Theta(\log n)$ questions if $r < 1/3$, but Carole wins if $r \ge 1/3$.
• In version C, Paul wins with $\Theta(\log n)$ questions if $r < 1/4$, Carole wins if $r > 1/4$, and if $r = 1/4$, Paul wins but needs $\Theta(n)$ questions.

BTW, this problem is known as the Ulam(-Renyi) problem or Ulam's searching game, and has an extensive literature (with which I'm not familiar) — the following is a survey as of 2002:

• Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2^q/(q+1), which for n=1000 is indeed 14.

This paper seems to have a "simple solution", but maybe others more familiar with the topic can find better references.

BTW, this problem is known as the Ulam(-Renyi) liar problem or Ulam's searching game (or just "playing Twenty Questions with a liar"), and has an extensive literature. The following is a survey as of 2002:

• Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2^q/(q+1), which for n=1000 is indeed 14. There are alternative solutions to the one-lie game in more recent papers like this and this. As observed by Peter Shor in a comment above, the general adaptive strategy when multiple lies are allowed does not look like Hamming codes.

Edit: Since this has been bumped up, I may as well mention a nice result in the more general setting, proved by Joel Spencer and Peter Winkler in their paper Three Thresholds for a Liar.

It is traditional to name the two players Paul and Carole, where Paul (named after Paul Erdős) is the one who asks the questions, and Carole (an anagram of oracle) is the one who answers them. Paul asks $q$ questions in all, and Carole is allowed to lie a fraction $r$ of the time. We will consider three progressively harder (for Paul) versions of this what means. In Version A, Carole is allowed to lie at most $\lfloor ri\rfloor$ times to the first $i$ questions, for all $i$. In Version B, Carole is only required to lie at most $\lfloor rq \rfloor$ times in total — she can choose to exhaust all her lies at the beginning, for instance. In Version C (nonadaptive), Paul must ask all his questions in one batch, and Carole can choose up to $\lfloor rq \rfloor$ ones to lie to.

Note that if no lies are allowed ($r = 0$), the number of questions needed is exactly $\lceil \log_2 n\rceil$, and that, intuitively, if $r$ is too large, Paul cannot guess correctly at all. Specifically, they show that:

• In version A, Paul wins with $\Theta(\log n)$ questions if $r < 1/2$, but Carole wins if $r \ge 1/2$.
• In version B, Paul wins with $\Theta(\log n)$ questions if $r < 1/3$, but Carole wins if $r \ge 1/3$.
• In version C, Paul wins with $\Theta(\log n)$ questions if $r < 1/4$, Carole wins if $r > 1/4$, and if $r = 1/4$, Paul wins but needs $\Theta(n)$ questions.