5
$\begingroup$

Most of us have come across the problem in which a player chooses a number within a range $1-n$ and we have to guess that number by asking minimum no. of questions.
That can be done by binary search(asking less than or greater than half). But what would be the appropriate approach if $n$ is unknown? Is there any optimal strategy which we can use?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by optimal? $\endgroup$ – boboquack Sep 18 '17 at 7:08
  • $\begingroup$ I'm not concerned with doing it in minimum number of steps as there is no upper bound. So I think optimal is not the correct word, I would say the best possible way to do it. $\endgroup$ – cnoob Sep 18 '17 at 7:19
  • $\begingroup$ The one that requires the least effort (if not time) is the one in my answer. But I'm not sure that's what you mean. Unfortunately, if you aren't specific in what you want, the question is likely to be closed as too broad. $\endgroup$ – boboquack Sep 18 '17 at 7:28
  • $\begingroup$ @cnoob You need to define "optimal strategy" here. Many ad-hoc algorithms may exist for the guessing game. $\endgroup$ – ABcDexter Sep 18 '17 at 7:37
  • $\begingroup$ And I pick G(64,63) - 1. $\endgroup$ – Joshua Sep 18 '17 at 16:31
5
$\begingroup$

You don't constrain your numbers to integers, so let's consider picking real numbers.

The real numbers form an uncountable set (e.g. see Cantor's diagonal argument). Any algorithm that involves checking each answer produces only a countable number of answers.

There is therefore no strategy that can be used to determine the hidden number exactly, and hence no optimal strategy to do so.


If your $n$ is known to be an integer, then you can proceed as follows:

  1. For any $b$, go up the progression $b^i$ for $i=0,1,2,...$ in turn until you find $k$ such that $b^k \geq n$. This takes $O(\log_b n)$ time.
  2. Find $n$ using a traditional binary search. This takes $O(\log_2 n)$ time and is optimal for step 2.

Suppose step 1 chose $b>2$ and terminated with $b^k$. If we had chosen $b=2$, it would have terminated with $2^{k' \log_2 b}$, where $k'$ is somewhere between $k-1$ and $k$ since $n$ is between $b^{k-1}$ and $b^k$. This takes takes $O(k' \log_2 b)$ time. Choosing the larger $b$ makes step 1 go faster by $O(k' \log_2 b - k)$, which we can write as $O((k'-\frac{k}{\log_2 b}) \log_2 b)$.

Finding $n$ in step 2 using $b>2$ would have taken $O(\log_2 b^k) = O(k \log_2 b)$ time. Had we chosen $b=2$, step 2 would have taken $O(k' \log_2 b)$ time. Choosing larger $b$ makes step 2 go slower by $O((k-k') \log_2 b)$.

Comparing the differences between steps 1 and 2 with $b>2$, it's clear that choosing $b>2$ (compared with choosing $b=2$) speeds up step 1 by less than it slows down step 2.

So unless $n$ is exactly $b^k$, which we can't know beforehand, choosing $b=2$ for step 1 produces an optimal algorithm for finding integer $n$.

$\endgroup$
  • 3
    $\begingroup$ Given the 'picking from 1 to n' part, I think it's safe to assume the questioner meant integers, even if they didn't say it. $\endgroup$ – boboquack Sep 18 '17 at 8:43
  • 1
    $\begingroup$ @boboquack I'm working on a proof of optimality for that. $\endgroup$ – Lawrence Sep 18 '17 at 8:51
  • $\begingroup$ @boboquack Ok, done, though it's more of a worst-case analysis than a rigorous every-case (or perhaps even an average-case) analysis, and it's limited to the format of the process chosen for step 1. $\endgroup$ – Lawrence Sep 18 '17 at 9:30
4
$\begingroup$

A binary search would do:

  1. Initialize the lower bound L as 1 and upper bound U as 2.
  2. Ask whether the number lies from L to U (including these).
  3. If yes, then bisect these numbers into two parts, L to L/2 and L/2+1 to U. Ask the step 2 for these two parts and repeat till you reach the number.
  4. If no, the increase the L to U+1 and U to 2*U. Repeat the step 2 till you reach the number.
$\endgroup$
  • 1
    $\begingroup$ What if I choose U as 10 and rather than taking 2*U I take U*U in subsequent steps. That would help me to get a range pretty fast. But I think it poses problem in further step of binary search. $\endgroup$ – cnoob Sep 18 '17 at 7:21
  • 1
    $\begingroup$ @cnoob Yes, precisely. The problem with choosing greater coefficient to multiply with U, poses the problem of wider search space when looking at the leaf node of the M-ary tree thus formed. $\endgroup$ – ABcDexter Sep 18 '17 at 7:24
  • $\begingroup$ @cnoob I've considered this in my answer. $\endgroup$ – Lawrence Sep 18 '17 at 9:30
3
$\begingroup$

Well...

You can't bound the number of moves, or even the average number of moves in all cases, so an 'optimal' strategy is difficult to define.

Since:

Suppose you ask about the numbers $a_1,a_2,...,a_m$. They could have chosen any number bigger than those and you wouldn't know what it was.

In terms of the easiest strategy:

i=1;print(1)
while input()<'o':i+=1;print(i)
Err... I mean just ask about every integer in turn.

$\endgroup$
  • $\begingroup$ In this case, with an actual person asking you, you can upper bound the number as being the longest number someone can pronounce from birth until death. Then you can "simply" binary search between 1 and that number. (Although you probably need your offspring to take over guessing for you at some point) $\endgroup$ – DrunkWolf Sep 18 '17 at 8:17
  • $\begingroup$ @DrunkWolf that's still astronomically large. You might want to look at this for how large numbers can get and still be pronounceable... sites.google.com/site/largenumbers/home. For that, binary searching would be on the same level of 'taking vastly way too long' as counting one by one $\endgroup$ – boboquack Sep 18 '17 at 8:34
  • $\begingroup$ @bobosquack oh I'm well aware it's astronomically large (far larger than that in fact), but bounded binary search (while taking basically forever), will still be way faster than counting one by one ;) but yeah, I basically agree with you that there's no proper strategy. Especially since normally we don't take human limitations into account when it comes to math $\endgroup$ – DrunkWolf Sep 18 '17 at 10:22
3
$\begingroup$

You'd first do a "reverse binary search" to find an upper bound. In pseudo-code:

$N = 1;
while (answer-to ("Is the number less than $N?") == "no") {
    $N = 2 * $N;
}

At the end of the loop, the number to guess is less than $N. This means that the number of questions you need to ask is roughly twice the log of the searched for number. (That's log with base 2).

$\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.