• 0

i am thinking of a number...

Question

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites

5 answers to this question

  • 0

Posted · Report post

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

1

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

  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?

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.