Least cost to guess a number between 0~100

The strategy for large ranges must be to guess a number that is some proportion $p$ down from the top of the current range. For case $2,$ you would like to have the same range remaining after you spend $\$2,$ whether that comes from one high guess or two low ones. You guess low with probability $p$ and high with probability $1-p$. The chance of two low guesses in a row is $p^2.$ That means $p^2=1-p$, which says $p=\frac12(\sqrt 5-1) \approx 0.618$ so your first guess should be $100-0.618*99$ or $39$. I would have to think some more about how the granularity of the numbers impacts this, but if $39$ is too high the second guess seems like it should be $ 38 - 0.618\cdot 37$ which is close to $15$. Then $6, 3, 1$ gets you there for $\$9$ if the target is $2$. I leave the other cases to you to verify you don't spend more. For case $3$, the same logic says you shouldn't care if you get three lows or two highs, so $p^3=(1-p)^2$. Alpha solves this exactly, giving a mess that is about $0.57$, so your first guess should be $100-0.57*99$ or $44$

Given $n$ dollars, we can solve an interval only if we can make a guess such that the interval less than the guess is solvable with $n - a$ dollars and the interval greater than the guess is solvable with $n - b$ dollars. So, let $f(n)$ be the size of the largest interval solvable with $n$ dollars. Then we have

$$ f(n) = f(n - a) + f(n - b) + 1 $$

and the interval from $1$ to $f(n)$ can be solved with a guess of $f(n - a) + 1$. The base case is $f(n) = 0$ for $n < 0$. This can easily be solved by hand for the numbers in question, or a general technique for solving recurrences can be applied. In case 2, each $f(n)$ is one less than a Fibonacci number.