0
$\begingroup$

In the classical number guessing game, you guess the number from 1 to 100. The answers, if you do not get the correct number, state whether your guess is higher or lower. In this setup, using optimal binary search strategy, you need at maximum 7 tries to guess the number (the last try is the try stating the correct number).

What do I ask is how do I compute the number of necessary tries for games with different range of possible numbers. In the original game, we have 100 different numbers (N=100) and 7 tries is enough in the worst case (X=7).

How do I compute X for any N?

My guess using some simple logic (I am not a mathematician) is something like X=log2(N), rounded up, but it fails for e.g. N = 2, because the result is 1, but I need 2 tries to get the number if I am not lucky.

What is the correct formula?

$\endgroup$
1
  • $\begingroup$ log2 seems right ... maybe add or subtract 1 somewhere? Combined with rounding down rather than rounding up? Just try some more numbers (3,4,5 ..) and see where the boundaries are. $\endgroup$
    – Bram28
    Commented Apr 16, 2018 at 17:49

1 Answer 1

1
$\begingroup$

It might be easier to flip this around and ask: What's the largest range you can solve using $X$ questions? It's straightforward to see that, using a bisection strategy, the maximum value of $N$ where you can win is $N = 2^{X} - 1$.

So, for a given $N$, the number of questions you need is the integer $X$ satisfying: $$2^{X - 1} - 1 < N \leq 2^{X} - 1$$

$$X - 1 < \log_{2}(N + 1) \leq X$$

Meaning:

$$X = \text{ceil}(\log_2(N + 1))$$

$\endgroup$

You must log in to answer this question.

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