Guessing number in set 1-100 with weighted questions.

Question

It is needed to guess number from 1 to 100. I can ask questions and get answers:"yes" or "no". For the "yes"-answer I must pay one dollar, for the "no"-answer - two dollars. How many dollars should I have to guess my number exactly?

The obvious decision is to product upper bound of $log_2 100$ on 2(we always divide our set on two equal parts and expect the worst case).

But I think that it is not an optimal algorithm, may be it is better to divide my set at an another ratio than one to one because of not equal costs of questions. May be at a ration two to one.

Help to find the best solution please. Thank you in advance.

Answer 1

A bit of formalisation, let's mark the questions by $A_{i}, 1\leq i\leq n$. Let's note $P(A_{i})=x_{i}$ - probability to get an "yes" for $A_{i}$. The mean is $1 \cdot x_{i} + 2 \cdot (1-x_{i})=2-x_{i}$. The total price is $2 \cdot n-\sum_{i=1}^{n}x_{i}$ - an optimisation problem of $x_{i}$ and $n$. Particularly, $x_{1}=x_{2}=...=x_{n}=x$, then the price is $n \cdot (2 - x)$.

By dividing the set (and subsequent sub-sets) in $M:K$ ratio, we have 2 extreme cases:

• assume each question is about $M$ side and we hit "yes" always, $(\frac{M}{M+K})^{n} \cdot 100 \approx 1$ or $n \approx -\log_{\frac{M}{M+K}}100$ and the price is $\approx -\log_{\frac{M}{M+K}}100$, (because $x=1$) which is ascending by $y=\frac{M}{M+K}$ on $(0,1)$ http://www.wolframalpha.com/input/?i=-log_%7Bx%7D%28100%29. I.e. we tend to reduce M and increase K, so that we hit "yes" for smaller sub-sets.
• assume each question is about $M$ and we hit "no" always (as if the number is not in that side), so we will continue with the other side always, aka $(1-\frac{M}{M+K})^{n} \cdot 100 \approx 1$ or $n \approx -\log_{\frac{K}{M+K}}100$ and the price is $\approx -2 \cdot\log_{\frac{K}{M+K}}100$, (because $x=0$) which is again ascending by $y=\frac{K}{M+K}$ in on $(0,1)$. I.e. we tend to reduce K and increase M, so that we hit "no" for larger sub-sets.

We end up with this "increase-reduce" $K$ and "increase-reduce" $M$ at the same time, which indicates (imho) 50:50 might be the best bet.