Minimum money needed for the worst case to guess the right number

Question

You are going to guess a number from $0$ to $100$. If your guess is smaller, you are told and you need to pay $x$; if your guess is larger, you are told and you need to pay $y$. The game stops when your guess is right.

Question: what is the minimum money you need to prepare to have the right guess when:

1. x = 2, y =1

2. x = 1.5, y =1

Answer 1

My answers are:

9 and 7.5

The way I arrive at these answers is:

Let F(x) be the range of numbers you can search with money x. Consider the first problem where prices are 1 and 2.

F(0) = 1 because if there is only one number you can always guess it correctly without paying. F(1) = 2 because you can pick the higher number and pay 1 if you are wrong, and pick the other number after.
F(2) = 4 because you can pick 3 first out of the range 1-4. If you pick too low, you pay 2 and pick 4 next. If you pick too high, you pick 2 then 1 next.

If you think about how F(2) was derived, it comes from this recurrence relationship:

F(x) = F(x-1) + 1 + F(x-2)

because suppose you pick a number. There are three outcomes:

a) You picked too high, in which case you pay 1, leaving x-1 money. You can then search a range of size F(x-1) below your guess.
b) You picked the number exactly right. (The +1 in the middle)
c) You picked too low, paying 2 and you can search a range of size F(x-2) above your guess.

Given the above formula, the rest of the F(x) are:

F(3) = 7
F(4) = 12
F(5) = 20
F(6) = 33
F(7) = 54
F(8) = 88
F(9) = 143

So with 9 money, you can search a range of size 143. If the range were 1..143, you would start by picking 89. This would either leave a range of 88 below with 8 money or a range of 54 above with 7 money. You would then search the subrange using the same technique.

For the second problem, the recurrence relation is:

F(x) = F(x-1) + 1 + F(x-1.5)

and the values are:

F(0.0) = 1
F(0.5) = 1
F(1.0) = 2
F(1.5) = 3
F(2.0) = 4
F(2.5) = 6
F(3.0) = 8
F(3.5) = 11
F(4.0) = 15
F(4.5) = 20
F(5.0) = 27
F(5.5) = 36
F(6.0) = 48
F(6.5) = 64
F(7.0) = 85
F(7.5) = 113

So with 7.5 money, you can search a range of size 113, picking 65 first. This would either leave you with a range of 64 below and 6.5 money, or a range of 48 above with 6.0 money. Again, you search the subranges in the same fashion.

Answer 2

My answer is:

You do a binary search.

Doing so,

You need at most ceil(log2(101))=7 guesses.

The maximum amount you need to pay would be

max(x,y)*6+min(x,y)

because

In the worst case, you keep guessing 6 times till a choice between two remains. There, guess the one which would cost you less if you are wrong.

So, for case 1, it is

13

For case 2, it is

10

Answer 3

I got the same answers as @JS1, but by a different approach.

Let $f(n)$ be the worst-case cost of guessing from $n$ numbers, e.g., $0\dots n-1$.  Trivially, $f(1)=0$, because if there’s only one number to choose from, so you’re certain to get it on the first guess (and incur no cost/penalty).  Let’s try to find $f(n+1)$ inductively/recursively, assuming that we know $f(n)$ (and all values before that).

Let $f(n+1,m)$ be the worst-case cost of guessing from $n$ numbers, e.g., $0\dots n$, given that your first guess is $m$ ($0 \le m \le n$). $f(n+1,m)=\begin{cases}x+f(n-m)&\text{if you guess low}\quad\text{(cost for guessing low} +\\&\qquad\qquad\text{cost for guessing from $(m+1)\dots n$)}\\0&\text{if you guess right}\\y+f(m)&\text{if you guess high}\quad\text{(cost for guessing high}+\\&\qquad\qquad\text{cost for guessing from $0\dots(m-1)~$)}\end{cases}$

Note that $m=0$ and $m=n$ are special, boundary cases.  If $m=0$, you can’t have guessed high, and if $m=n$, you can’t have guessed low.  To handle these cases, I notationally declare $f(0)$ (which is logically undefined) to be $-\infty$, to make the corresponding cases in the $f(n+1,m)=$ formula (above) drop out.  Well, since $f(n+1,m)$ is the worst case, it’s the maximum of the above: $\max (x+f(n-m),~~y+f(m))$.  But now the question of strategy arises: we can minimize $f(n+1)$ by choosing $m$ that gives us the lowest $f(n+1,m)$.  (Intuitively, if $x=y$, then the ideal $m$ is $\big\lfloor{n \over 2}\big\rfloor$.  If $x>y$, then the best $m$ is somewhat higher.  If $x \gg y$, then the optimum $m$ is much higher.)  So $f(n+1)$ is $\min_{(0 \le m \le n)}f(n+1,m)$.

Unfortunately, I couldn’t figure out how to reduce the above algebraically. But I was able to develop an Excel spreadsheet to calculate $f$, and it gave me these results: $\qquad f(101)=\begin{cases}9&\text{if $x=2~~~$ and $y=1$}\\7.5&\text{if $x=1.5$ and $y=1$}\end{cases}$

matching JS1’s answer.