5
$\begingroup$

(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?

$\endgroup$
7
  • 4
    $\begingroup$ The last intuition is not true. Suppose that the machine has picked the positive integer number $n$ (so not infinity). Then we ask one by one, is it $1$? is it $2$? After finitely many steps we hear a "yes". $\endgroup$ Nov 16, 2021 at 10:14
  • $\begingroup$ The catch is that there is no way to pick a "random positive integer" in such a way that every positive integer has the same chance to be picked. $\endgroup$
    – Peter
    Nov 16, 2021 at 10:15
  • 1
    $\begingroup$ @Peter yes, I clarified it further; I thought since I mentioned a "whole number" has to be picked, infinity would be excluded in that. $\endgroup$
    – Katai
    Nov 16, 2021 at 10:26
  • 1
    $\begingroup$ "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?" On the contrary, the chances of you choosing an upper bound should be basically 1, since there are only finitely many numbers which are not upper bounds and infinitely many numbers which are upper bounds. $\endgroup$
    – Will R
    Nov 16, 2021 at 10:32
  • 1
    $\begingroup$ @WillR But we cannot ask the machine "is the number greater than $x$" for a number $x$ that is too large for us to be even described. Although Dietrich Burde's method finds the number in finite time in theory, in pratice we would not find it since at some point we would run out of reasonable descriptions. $\endgroup$
    – Peter
    Nov 16, 2021 at 10:40

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ This conclusion is not precise enough: 'you get $2^n$ groups which is only finitely many, so one of these groups will contain infinitely many numbers still.' Actually, at least one of these groups will contain infinitely many numbers. Consider questions 'Is the number a multiple of 2?' and 'Is it a multiple of 3?' $\endgroup$
    – CiaPan
    Nov 16, 2021 at 11:15
  • $\begingroup$ You’re right, I should have written “at least one” (because that’s what I meant). $\endgroup$ Nov 16, 2021 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .