Jump to content
BrainDen.com - Brain Teasers
  • 0

i am thinking of a number...


BMAD
 Share

Question

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 by BMAD
Link to comment
Share on other sites

5 answers to this question

Recommended Posts

  • 0

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).

  • Upvote 1
Link to comment
Share on other sites

  • 0

There's 2

7 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 27 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.
Link to comment
Share on other sites

  • 0

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).

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...