Is it possible to guess a number from an infinite range with yes or no questions

infinityprobabilitypuzzle

(I hope this qualifies as a math question; it might just be a puzzle.)

I've had a thought experiment a few days ago: Assume you have a machine that randomly picks a whole number from 1 to infinity, and you can ask that machine as many yes or no question about the number it picked as you need; can you find out what number it picked?

Edit (comments): to clarify, it has to be a whole number, it cannot pick infinity itself.

Examples questions could be "is the number larger/smaller than x?", "is the nth digit x?", "is the number prime?", etc.

My questions are:

  • Is it possible to find out what number it picked (at all)?
  • Is it possible in a finite amount of time?
  • If yes, what could be the most efficient strategy to find out? (asking for "higher than x", going through every single digit one by one, or something else entirely?)

My intuition tells me that it's not possible to find out what number it picked, because no matter how large I make "x" (to ask "is the number larger than x?"), there are always infinitely many more larger numbers the machine could've picked from. So the chances of me ever finding the upper bound of that number should be basically 0, since it's infinitely more likely to have picked a larger number?

Best Answer

If you put no bound on the number of guesses, you will always be able to find the number. Simply go through them one-by-one: Is the number $1$? Is the number $2$? … Because the number is fixed after the machine has picked it, at some point, you will find it. It might take an incredibly long time, of course.

For the second question, imagine that you ask $2$ questions (for now). Then, you can divide all numbers into $4$ groups:

  • Those where both answers would be “no”,
  • those where the first answer would be “yes” and the second “no”,
  • those where the first answer would be “no” and the second “yes” and
  • those where both answers would be “yes”.

If you ask your questions, you know which group the number comes from. This tells you the secret number, provided the group contains only one number. However, as there are infinitely many numbers, at least one of these groups will contain more than one number. Therefore, you cannot guarantee that you will know the number after $2$ questions. More generally, for any fixed finite number of questions, the same will be true. If you ask $n$ questions, you get $2^n$ groups which is only finitely many, so at least one of these groups will contain infinitely many numbers still. Therefore, you can’t put a bound on the number of questions needed.

For your last question, there is a subtle problem alluded to in the comments: Saying “pick a number at random” is not a well-defined thing you can do. What you would need to do is assign a probability for picking each number. (Together, these give you a “probability measure”.) These probabilities would necessarily not be all equal. The optimal strategy depends on the chosen probability measure. In general, you would try to “half” the search-space with each step where “half” would be defined in term of this probability measure.

Related Question