Original problem:
Alice chooses a positive integer $x\in[1,100]$ and Bob tries to guess it.
Each turn Bob can guess a number $y$ and pay $y$ dollor(s) to Alice.
If $y=x$ game stops, otherwise Alice will tell Bob $y>x$ or $y<x$.
What's the minimum expectation payment for Bob to know the random number $n$.
I tried to find the answer of general case.
My rough Attempts:
Let $\mathrm{E}(n)$ be the total payment under the optimal strategy, define $\mathrm{cost}(m,n)$ as the minimum price when $m\leq x\leq n$, so $\mathrm{E}(n)=\mathrm{cost}(1,100)$.
Then we can write the recurrence equation.
$$ \begin{aligned} \mathrm{cost}(m,n)&=\ 0 \quad \texttt{when}\ m\geq n,\ \texttt{otherwise:}\\ \mathrm{cost}(m,n)&= \min_{m\leq l\leq n} \left(l + \frac{l-m}{n-m+1} \mathrm{cost}(m,l-1) + \frac{n-l}{n-m+1} \mathrm{cost}(l+1,n)\right) \end{aligned} $$
Then I use some Mathematica codes to get the answer.
cost[m_, n_] := 0 /; m >= n;
cost[m_, n_] := cost[m, n] =
Min@Table[l + (l - m) cost[m, l - 1]/(n - m + 1)
+ (n - l) cost[l + 1, n]/(n - m + 1), {l, m, n}]
cost[1, 100]
Table[cost[1, i], {i, 1, 10}]*Range[10]
$$\begin{array}{c|cc} \text{n} & 1&2&3&4&5&6&7&8&9&10&100 \\ \hline \mathrm{E}(n)&\cfrac{0}{1}&\cfrac{2}{2}&\cfrac{6}{3}&\cfrac{13}{4}&\cfrac{22}{5}&\cfrac{35}{6}&\cfrac{52}{7}&\cfrac{72}{8}&\cfrac{96}{9}&\cfrac{123}{10}&\cfrac{26190}{100}\\ \end{array}\\$$
I have no idea about this sequence.
Can we find a close form of $\mathrm{E}(n)$?