i am thinking of a number...

[BMAD]

I am thinking of an integer n with 0 <= n <= 15. To figure out what number I'm thinking of, you can ask me 7 yes-or-no questions --questions that can only be answered with either "yes" or "no". The questions must be independent of each other, their answers, and the order in which they are answered. (So you can't ask a question like, "if the answer to the previous question was "yes", then is n larger than 10, otherwise is n even?") When you ask me your seven questions, I am allowed to LIE about at most one of the answers. What seven questions can you ask to determine n?

Edited August 8, 2013 by BMAD

[witzar]

Let's work in binary.

Let n=abcd be a 4-digit number.
Let e be the parity of abc.
Let f be the parity of abd.
Let g be the parity of acd.
(Parity of sequence of bits is 1 if the sequence contains odd number of 1's, and 0 otherwise.)

Let's ask 7 questions (about a trough g), obtaining 7 digit vector abcdefg, in response.
Now we can check if e, f, and g in the response match the parity of appropriate bits in response.

If BMAD decides to lie about a, then we'll notice errors in e,f,g.
If BMAD decides to lie about b, then we'll notice errors in e,f.
If BMAD decides to lie about c, then we'll notice errors in e,g.
If BMAD decides to lie about d, then we'll notice errors in f,g.
If BMAD decides to lie about e, f or g, then we'll notice a single error in e or f or g respectively.
If BMAD decides not to lie at all, we'll notice no error.

Observe that no mater what he does, the set of noticed errors will be unique,
thus letting us know what did BMAD lie about (if at all)
and letting us restore true values of abcd(efg).

[gavinksong]

There's 2

⁷ distinct sets of answers that could be given to the seven questions. To avoid ambiguity, each number between 0 to 15 must map to 8 unique sets of answers, which means exactly all 2⁷ possible sets of answers must be uniquely mapped to. We also have to consider the fact that the 8 sets to which each of the numbers between 0 and 15 correspond are related: seven of the sets must differ from the first by exactly one answer. So the problem is equivalent to selecting 16 points on an 7-dimensional hypercube with exactly 3 degrees of separation from each other. No more, no less. I don't think it's possible, but I could be wrong.

[Rainman]

Question 1: is the number larger than 7?

Question 2: is the number in the set {0, 1, 4, 5, 10, 11, 13, 14}?

Question 3: is the number in the set {0, 1, 6, 7, 8, 9, 13, 14}?

Question 4: is the number in the set {0, 2, 4, 7, 9, 10, 12, 14}?

Question 5: is the number in the set {0, 2, 5, 6, 8, 11, 12, 14}?

Question 6: is the number in the set {0, 3, 4, 6, 9, 11, 12, 13}?

Question 7: is the number in the set {0, 3, 5, 7, 8, 10, 12, 13}?

These are the answers if you answer truthfully on all questions.

0: NYYYYYY

1: NYYNNNN

2: NNNYYNN

3: NNNNNYY

4: NYNYNYN

5: NYNNYNY

6: NNYNYYN

7: NNYYNNY

8: YNYNYNY

9: YNYYNYN

10: YYNYNNY

11: YYNNYYN

12: YNNYYYY

13: YYYNNYY

14: YYYYYNN

15: YNNNNNN

For any two of these "true answers", they differ from each other on at least 3 questions. However, your answer can only differ from its matching true answer on 1 question. So for any given answer, say YNYNNNY, there can be only one matching true answer (in this case YNYNYNY), and thus we can uniquely determine the number you were thinking of (in this case 8).

[gcgardner]

1. does the number have 2 digits?
2. is the number a prime number?
3. is the sun of the digits greater than 3?
4. is the number divisible by 3?
5. is the number a factor of 2?
6. is the number greater than 6?
7. is the number 0?

[brob26]

http://en.wikipedia.org/wiki/Hamming(7,4)

Edited August 14, 2013 by brob26