I'm thinking of a number between 1 and 2000.

First ask Walter 11 questions, one for each bit of the binary
representation of the number:

1. "In the binary representation of your number, is the 1024s bit 1?"
2. "In the binary representation of your number, is the 512s bit 1?"
...
10. "In the binary representation of your number, is the 2s bit 1?"
11. "In the binary representation of your number, is the units bit 1?"

Now ask four "checksum" questions:

12. "In the binary representation of your number, is the sum of the
     1s,   4s,8s,16s,32s,64s, and 128s bits odd?"
13. "In the binary representation of your number, is the sum of the
     1s,2s,   8s,16s,32s,         256s, and 512s bits odd?"
14. "In the binary representation of your number, is the sum of the
     1s,2s,4s,   16s,    64s,     256s,      and 1024s bits odd?"
15. "In the binary representation of your number, is the sum of the
     1s,2s,4s,8s,            128s,     512s, and 1024s bits odd?"

The yes/no responses to these questions will be either true or false
---there are no tricky self-referential questions in this lot.
Now there are three cases to consider:

C1: Walter doesn't lie to any of your questions.  Then the answers to
    questions 12-15 will be exactly what you'd expect based on the
    answers to questions 1-11.

C2: Walter lies to one of the questions 12-15.  Then the answer to
    this question won't be consistent with responses 1-11.  But the
    other three checksum responses *will* be consistent with responses
    1-11, because all those 14 responses were true.

C3: Walter lies to one of the questions 1-11.  Then any checksum
    response that concerns the same bit as the falsely answered
    question will be inconsistent with responses 1-11, because those
    responses imply a false checksum but responses 12-15 are true.
    Each bit is mentioned in at least two different checksums, so at
    least two of those responses will be inconsistent.

Now compare each checksum response to the answer you'd deduce assuming
that responses 1-11 were all true.  If all checksums are consistent,
or only one is inconsistent, you know you're in case C1 or C2, and you
can simply read Walter's number (in binary) from responses 1-11,
translating the yeses and nos into 1s and 0s.

If two or more checksums are inconsistent, you know you're in case C3
[Editor: "C2" in the original].  But since no two bits are mentioned in
exactly the same set of checksums, you can identify the false reponse:
it's the response to the unique bit that was mentioned in the
inconsistent checksums and no others.  Again, you can read the bits
from the first 11 responses, but flip the bit (read 0 for "yes" and 1
for "no") for the known incorrect response.

ObPuzzle1: Why can't you find Walter's number with certainty in just
14 (more cleverly devised) questions?

ObPuzzle2: Suppose Walter's range of numbers is 1-4000.  How many
questions must you ask to find it with certainty?

ObPuzzle2: The method described above used 4 "extra" questions (15
questions to deduce an 11-bit binary number).  Suppose you're allowed
one question for each bit of Walter's number, plus 5 extra questions.
How big can Walter's range of numbers be and still allow you to guess
the number with certainty?  (I.e., he says, "My number is an integer
in the range 1 to ___."  How large a number can be written in the
blank?)

ObPuzzle3: Suppose you're allowed k "extra" questions, how big a
range of numbers can you cover?

ObPuzzle4: Suppose Walter is allowed to lie up to two times.  How many
questions does it take to find his number if the number is in the
range 1-2000?  If you're allowed k "extra" questions, how big a range
of numbers can you cover?

-- David A. Karr <karr@cs.cornell.edu>

[ Editor: no answers to the follow-up ObPuzzles were found in the
collected postings. ]