Guessing Game With Optimal Profit

Relevant wiki: Expected Value - Problem Solving

Veeery long solution.

First off, we notice that $1023 = 2^{10}-1$ , so now what? We know that the optimal algorithm for playing this game is choosing the median of the $1023$ numbers first, i.e. $512$ . Our friend tells us either lower or higher or correct, so in the first two cases we can eliminate $512$ of the numbers as possible candidates leaving us with $511$ remaining candidates. Notice that if we repeat this step again and again, we can see that every time we remove numbers from the possible candidates, the remaining numbers always have a median, or in other terms, the number of possible candidates is always odd.

Now, we have to calculate the expected value for the number of trials it will take us before we actually get the number our friend wants us to fin, following the algorithm. We know that there is a $\frac{1}{1023}$ probability that we get it right on our first try. But how about on the second try?

On the second try we will either choose $256$ or $768$ depending on the circumstances. So, if the number were to be one of these, we would get it right immediately on our second try. So, the expected number of moves for this case is $2 (\frac{2}{1023}) = \frac{4}{1023}$ .

How about on our third try? Using the same logic above, if the number were to be $128, 384, 640, 896$ , we would get it immediately on our third try. Now for this case the expected value is $3(\frac{4}{1023}) = \frac{12}{1023}$ .

Notice anything yet? The probability of getting the number right on the $nth$ term is $\large \frac{2^{n-1}}{1023}$ , so for any given case the expected value is $\large \frac{n2^{n-1}}{1023}$ . The expected value then becomes

$\large \displaystyle \sum_{n=1}^{10} \frac{n 2^{n-1}}{1023} = ( \sum_{n=1}^{10} n2^{n-1} )\frac{1} {1023}$ .

Now, this is an arithmetic-geometric progression . We evaluate it to be $\frac{9217}{1023}$ by the formula given on the page. Now, since $x*E=1023$ where E is the expected value (calculated from the given), we have

$\frac{9217x}{1023} = 1023$

Giving us $x = \frac{1023^2 }{9217} = 113.54$ . Therefore our answer is

$\huge \lfloor x \rfloor = \lfloor 113.54 \rfloor = \boxed{113}$ .

Its just like finding an element in a sorted array ranging from 1 to 1023 through binary search. If i had to guess a no. Between 1 and 1023, i would choose 512 which is the center of the range and procede as per my friend's response which is nothing but binary search.

We know, complexity of binary search is (log n) so (log 1023) = 9.99 I.e. Atleast 9 chances are needed for correct guess.

To balance the money to 0, 1023 = 9x , where x is the amount set. => x = ceil(1023/9) = ceil(113.66) = 113