Least cost to guess a number between 0~100

Question

Here is the problem. There is a number randomly chosen between 1~100. The player tries to guess that. If the guess is larger than true value, the player is punished by 'a' dollar. If the guess is smaller than true value, the player is punished by 'b' dollar. How much money the play should prepare in order to hit the number in the worst case? 1) a = 1, b = 1; 2) a = 2, b = 1; 3) a = 1.5, b = 1;

Here is where I am so far. For the first sub-question, the player would use binary tree and the worst case would be 7 guessing times (6 wrong and 1 right). Hence, the punish money would be 6*1 = 6 dollars. For the second sub-question, instead of separating the range by half, the player will separate the range according to the weight given by a and b, i.e. in this case the player would choose 33 for the first guess instead of 50. In this strategy, the worst case would cost the player 11 dollars(according to my calculation), while the binary method would cost the player 12 dollars. For the third question, the methodology is the same as second one.

My doubt is: is there another method which is better? The doubt comes from this fact: my method applied same to sub-question 2 and sub-question 3, which means the existence of sub-question 3 is meaningless. Clearly an author of a problem would not put that kind of sub-question.

appendix: I am not sure the problem in the link below would provide some hint, but they have something in common. http://datagenetics.com/blog/july22012/index.html

Answer 1

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.

Answer 2

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$