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

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

• Worst case would be maximum money needed – Beastly Gerbil Nov 19 '16 at 8:54
• @BeastlyGerbil Yes, however it wound exceed a certain number. – fizis Nov 19 '16 at 8:56

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.

• This is clearly the correct answer, it needs more upvote love – ffao Nov 19 '16 at 21:06

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

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}$