3
$\begingroup$

Let player A and player B are playing number-guessing game, which is:

  1. Player A draws one natural number $X$ in $1,2,\cdots,N$ at random.

  2. Player B guesses a number $Y$ in $1,2,\cdots, N$.

  3. Player A says "ok" if the guessed number $Y$ equals $X$. If $X > Y$, player A says "up". If $X<Y$, player A says "down".

  4. Player B keeps on guessing until player B gets the right number.

Now let $M$ be the number of trials that player B needed to take until player A says "ok". Player B earns $X \cdot r^M$ points. Here $r$ is pre-determined real number in $(0,1)$.

I want to give an optimal strategy for player B which maximizes an expectation of points earned.

I defined an array $a$, where $a(i,j)$ means the optimal guess when $i\leq X \leq j$ is guaranteed. What makes the problem hard is that the game is not translation-invariant: i.e. if $i>j$, $a(i,i+k)$ need not be equal to $a(j,j+k)+i-j$. This happens because the points earned when the game is over is proportional to $X$.

What I want to prove is the following inequality: if $i>j$, $$a(i,i+k) \leq a(j,j+k) + i-j $$

This seems intuitively clear because the smaller the $I$ is, the more benefit player B gets if he/she guesses a larger number.

I am stuck with coming up with a rigorous proof.

Thank you for any form of help, hint, or solution.

$\endgroup$
4
  • 2
    $\begingroup$ One strategy would be a modified bisection search, where instead of the midpoint you choose a point higher up in the interval (e.g. $a+0.75*(b-a)$), to gamble on faster convergence for higher values yielding better points on average. $\endgroup$
    – Tony Mathew
    Commented Jan 18 at 8:41
  • 1
    $\begingroup$ You are over-thinking the Issue. Here $r$ is not controllable. When B makes the guess , $X$ is already fixed. Hence Expectation depends only on $M$. Minimize $M$ to Maximize Expectation. Use Binary Search. $\endgroup$
    – Prem
    Commented Jan 18 at 8:42
  • 2
    $\begingroup$ This is a really interesting question. I observe that the optimal guess function in general depends on the discount rate $r$, and it would seem that as $r$ approches zero, $a(i,j) = j$. Also I would conjecture that as $i$ increases, eventually $a(i,i+k) = i+\lceil{k/2}\rceil$. $\endgroup$
    – 3rdMoment
    Commented Jan 19 at 18:06
  • 1
    $\begingroup$ @3rdMoment That looks natural, but doesn't hold even for $k = 4$, where $a(i, i + 4) = i + 3$ for $i \ge \frac 1r$ $\endgroup$
    – Smylic
    Commented Jan 23 at 18:29

0

Reset to default

You must log in to answer this question.