10
$\begingroup$

In a high/low guess game, the "true" number is one of $\{1,\cdots,1000\}$. You'll be told if your guess is $<,>$ or $=$ the true number for each guess you make, and the game terminates when you guess out the true number. Suppose the following three scenarios:

  1. If your guess is either lower or higher, you pay $\$1$ in both cases. If your guess is correct, you pay nothing and the game ends.

  2. If your guess is higher, you pay $\$1$; if your guess is lower you pay $\$2$. If your guess is correct, you pay nothing and the game ends.

  3. If your guess is higher, you pay $\$1$; if your guess is lower you pay $\$1.5$. If your guess is correct, you pay nothing and the game ends.

In these three scenarios, what is, respectively, the minimum number of $\$$ you must have to make sure you can find the true number?

Formally, define a space of all guess strategies $\Sigma$. We can then identify the cost $C$ as a function $$C:\Sigma\times \{1,\cdots,1000\}\to\Bbb N_+,\quad v\mapsto C(S,v)$$ that maps the pair $(S,v)$ (where $v$ is the "true" number) to the cost it's going to take under this arrangement. Our problem is then to find $$\min_{S} \max_{v} C(S,v).$$

Can this min-max problem be analytically solved? What would be the corresponding optimal strategy then?

For scenario 1, my intuition is to use bisection search, which, at worst, costs $\$10$ ($2^{10}=1024$). But I cannot prove this is indeed optimal. For the second scenario, since making an under-guess means a higher cost, maybe it's more optimal to use a "right-skewed" bisection, i.e. you keep making guesses at the $2/3$-quantile point. But this is just (rather wild) intuition, not anything close to a proof.

$\endgroup$
14
$\begingroup$

For this game, the most natural representation of a strategy is a rooted binary tree, with vertices labeled by guesses (i.e. numbers from $\{1, \ldots, N=1000\}$), and each vertex having at most two edges (connecting it to the guess to make next, for "lower" and "higher" cases).

Let the penalties you pay for "lower/higher" cases be $L$ and $H$, respectively. Now consider an arbitrary $N$, and consider an optimal tree $T(N)$ (that reaches the minimum worst-case total penalty). Its root is labeled with some guess $R$, $1\leqslant R\leqslant N$, its left subtree can be chosen to be [isomorphic to] $T(R-1)$, and its right subtree isomorphic to $T(N-R)$ (assuming $T(0)$ is empty).

So if $P(N,L,H)$ is the optimal penalty, then $$P(0,L,H)=P(1,L,H)=0,\\ P(N,L,H)=\min_{1\leqslant R\leqslant N}\max\begin{cases}L+P(N-R,L,H)\\ H+P(R-1,L,H)\end{cases}\quad(N>1)$$ which allows one to compute $$P(1000,1,1)=\color{red}{9},\quad P(1000,2,1)=14,\quad P(1000,1.5,1)=11.5$$ (note $9$ but not $10$ as you've suggested; the decision process is not just a bisection but has extra "$=$" outcomes). The trees can be computed along the way.

Regarding the asymptotic behavior (with $N\to\infty$), if we let $R(N,L,H)$ be the "argmin" (say, the smallest root of optimal trees), one can show that the limits $$\alpha=\alpha(L,H)=\lim_{N\to\infty}\frac{P(N,L,H)}{\ln N},\quad\beta=\beta(L,H)=\lim_{N\to\infty}\frac{R(N,L,H)}{N}$$ exist and satisfy $$H+\alpha\ln\beta=L+\alpha\ln(1-\beta)=0.$$ In particular, $\beta(2,1)=(\sqrt{5}-1)/2$, and $\beta(1.5,1)$ is the root of $\beta^3=(1-\beta)^2$.

$\endgroup$
  • $\begingroup$ Thanks. This makes sense. There seems to be no way to compute such a complicated recursion analytically though. Did you use DP for this? $\endgroup$ – Vim May 11 at 12:30
  • $\begingroup$ Yes, I did. Probably this still can be analyzed further, but I didn't do that. $\endgroup$ – metamorphy May 11 at 12:38
  • 2
    $\begingroup$ IIRC, your recursion also gives the optimal strategy when you keep track of the partitions chosen at each recursion node. $\endgroup$ – Vim May 11 at 13:41
5
$\begingroup$

For the (2,1) case, I found the worst-case cost increases by 1 at every Fibonacci number, so $P(F_n,2,1)=1+P(F_n-1,2,1)=1+P(F_{n-1},2,1)$. These key values $F_n$ increase by ratio $F_n/F_{n-1}\to\phi=(1+\sqrt{5})/2$.
They grow exponentially; conversely, the maximum cost for $P(N,2,1)$ grows logarithmically.

For (1.5,1) the worst-case cost increases by $0.5$ at these values: $$P(N,2,1)>P(N-1,1.5,1)\,if\, N=2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,\ldots$$

The recursion in this sequence is $a_{n+1}=a_{n-1}+a_{n-2}$. Their ratio, $a_{n+1}/a_n$, approaches 1.3246, which is the root of $P^3=P+1$, just as $\phi$ for the (2,1) case is the root of $P^2=P+1$.

$\endgroup$
  • $\begingroup$ Would you elaborate on how the ratios arise? $\endgroup$ – Vim May 11 at 12:32
  • $\begingroup$ For $(4/3,1)$, the recursion is $a_{n+1}=a_{n-2}+a_{n-3}$, and for $(5/3,1)$, the recursion is $a_{n+1}=a_{n-2}+a_{n-4}$ $\endgroup$ – Empy2 May 11 at 13:00
1
$\begingroup$

Here are some worked-out cases for smaller lists and variable penalties.

Suppose you pay $a$ for a guess that is too low and $b$ for a guess that is too high.

Given a list such as $\{1,\ldots,1000\}$, the cost $C$ of the optimal strategy is a function only of the number of items $n$ in the list. Without loss of generality, assume that $a\leq b$. (If you want the case $a\geq b$, just reverse the order of the list.)

We can determine the cost of the optimal strategy in a few simple cases:

  • $C(1) = 0$. There is only one guess, and it is correct.
  • $C(2) = a$. High guesses are penalized more, so guess the lower element.
  • $C(3) = b$. Guess the middle element. If you're wrong, you know what the correct element is and it costs at worst $b$ total.

For larger values of $C(n)$, consider what the optimal first move. Suppose there are $n$ elements in the list and you choose index $1\leq k\leq n$. In the worst case, you are wrong. If the true answer is lower, you must pay $b$ and search through a list of $k-1$ elements. If the true answer is higher, you must pay $a$ and search through a list of $n-k$ elements. So in the worst case, by choosing $k$ in the first round, you'll incur a cost of $$\max\left(b + C(k-1),\; a + C(n-k)\right).$$ We can search for an optimal $k$ which minimizes this cost in the first move, in which case the recursive solution tells us what the rest of the strategy (and its corresponding cost) is.

Note that the optimal strategy will never be in the latter half of the list. This is because $C$ is monotonic. When $k$ is in the right half of the list (so that $n-k \leq k-1$), we can always shrink the worst-case cost $\max(b+C(k-1), a+C(n-k))$ by exchanging $k-1$ and $n-k$, putting $k$ into the symmetric position on the left half of the list.

By this reasoning, we find:

  • $C(4) = \max(2a,b).$ Choose the second element. If you're too high, you'll pay a cost of $b$ but know the true answer. If you're too low, you'll pay a cost of $a$, then search through the remaining two elements for a worst-case cost of $C(2)=a$.

  • $C(5) = a+b$. You can choose either the second or third (middle) elements. In the worst case if you choose the middle element, it's too high so you pay $b+C(2) = a+b$ to search the two remaining. If you choose the second element, in the worst case it's too low so you pay $a+C(3) = a+b$ to search the three remaining.

  • $C(6) = a+b$. Choose the third element. In the worst case, it's either too high so you pay $b+C(2) = a+b$, or it's too low so you pay $a+C(3)=a+b$.

  • $C(7) = \min(a+C(4), b+C(3)).$ As with the case $n=4$, the optimal strategy depends on the relative magnitudes of $a$ and $b$. If $2b > 3a$, then choose the third element in the list. Otherwise, choose the fourth (middle).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.