2
$\begingroup$

This is purely a theoretical question, but I was wondering how unique one number is from another number. And please Internet don't blast me for asking if you think it's a stupid question, I have reasons for asking. (And I don't know what to Tag this with).

If I played a game of 20 questions (Yes/No answers only), and was trying to guess what number you were thinking of, would I be able to find the number you're thinking of within $20$ questions?

Lets set a few parameters because if we're talking about an infinite set of numbers, then no I don't think there would be a solution. So Lets say $2^{20}$ numbers. That's a number between $0$ and $1,048,575$ (if zero based, I think)

I know that every number in that range can be uniquely defined within $20$ questions, something like, is the number even or odd $= \text{first bit}$, is it a multiple of $2 = \text{second bit}$, is it a multiple of $4 = \text{third bit}$. so on and so forth.

But is there a way of guessing without trying to define every 'bit' in the number? Could I guess the correct number with $15$ questions? $10$ questions? Could I get down to $5$ questions?

Pretty much, how unique is a number, can one number be differentiated from another number within a given range, without asking $\displaystyle\sqrt{\text{Number}}$ questions about the number?

$\endgroup$
4
  • 2
    $\begingroup$ You can at most eliminate half at each step. $\endgroup$ – Eff Apr 24 '17 at 22:34
  • 1
    $\begingroup$ The count of questions is roughly $\log_2 n$ (not square root). But other than that, assuming "yes" and "no" questions, you cannot really do better than eliminating half the potential answers at each step. If you were allowed to ask what remainder a number had when divided by some test values, you could get even large numbers fairly quickly. $\endgroup$ – Joffan Apr 24 '17 at 22:38
  • 2
    $\begingroup$ @Joffan in that case though (being able to ask for remainders and have the answer not be a yes/no), if we were looking at numbers in the range of say... $\{1,\dots,2^{10}\}$, we could ask the question of "what is the remainder of the number when divided by $2^{10}+1$ and figure out the number within a single question, kind of trivializing the whole process. $\endgroup$ – JMoravitz Apr 24 '17 at 22:41
  • $\begingroup$ @JMoravitz Yes, agreed... need to have some sort of penalty effect to make it interesting - like, you're not allowed to ask about divisibility for a number greater than say 100. $\endgroup$ – Joffan Apr 24 '17 at 22:43
3
$\begingroup$

If you were capable of always finding a natural number in the range $[0, n-1]$ in fewer than $\log_2(n)$ yes/no questions, then you would have found a compression algorithm which violated the pigeonhole principle.

$\endgroup$
3
$\begingroup$

It really depends on what questions are allowed.

When using questions with two options you can't really do better than determining one bit at a time like in your example. If we put it a little more mathematically: we can determine one digit in the base 2 representation of the number.

And that gives the general idea of how to do it if you're allowed to ask questions that have $n$ possible answers, simply ask questions to determine one digit in the base $n$ representation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.