# Guessing a number game with a twist

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?

• What do you mean by optimal? – boboquack Sep 18 '17 at 7:08
• 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. – cnoob Sep 18 '17 at 7:19
• 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. – boboquack Sep 18 '17 at 7:28
• @cnoob You need to define "optimal strategy" here. Many ad-hoc algorithms may exist for the guessing game. – ABcDexter Sep 18 '17 at 7:37
• And I pick G(64,63) - 1. – Joshua Sep 18 '17 at 16:31

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

• 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. – boboquack Sep 18 '17 at 8:43
• @boboquack I'm working on a proof of optimality for that. – Lawrence Sep 18 '17 at 8:51
• @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. – Lawrence Sep 18 '17 at 9:30

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.
• 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. – cnoob Sep 18 '17 at 7:21
• @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. – ABcDexter Sep 18 '17 at 7:24
• @cnoob I've considered this in my answer. – Lawrence Sep 18 '17 at 9:30

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)