A Special Type Of Guess The Number Game

Question

There is Guess Number game like this: In this game, the player must find a hidden positive number by at most $T$ guesses (or turns). The parameter $T$ together with a health parameter $H$ is determined at the beginning of the game. In each turn, the player must say a number. If the number is equal to the hidden number, he wins provided that $H≥0$. If the number is bigger than the hidden number, $H$ is decreased by $1$ unit of health. Otherwise, $H$ remains unchanged. When $H$ becomes negative or $T$ reaches $0$, the player definitely loses. The player can see the remaining turns and units of health after each turn.

How can I find the smallest $M$ for which at least a number from $1$ through $M$ as the hidden number can’t be guessed for the given $T$ and $H$. For example, there is not any ways for finding all positive integers not greater than $M=3$ by $2$ turns and $0$ units of health. Another example: $H = 1$, $T = 3$ So the answer is $M = 7$

Answer 1

Let's call $M(H,T)$ the maximal number that can still be guessed with fixed $H$ and $T$, i.e. there is a strategy for the player, if the guessing intereval is $\{1,\dots,M\}$.

It is clear that $M(0,T)=T$: the player has to try all numbers $1,2,3,\dots,M$ in this order.

Now let's look at $M(1,T)$. The optimal strategy is to play the first guess on $T$, then if it's too big, we have $T-1$ guesses to try all numbers up to $T$ (excluded), which is possible. If it's too small, we play the second guess on $T+(T-1)$, so that we only have the interval $[T+1,T-2]$ to search with the $T-2$ remaining guesses. Continuing this reasoning brings us to $$M(1,T)=T+(T-1)+(T-2)+\dots+1=\sum_{i=1}^T i=\frac{T(T+1)}{2}.$$

Notice that this agrees with your example: this formula gives $M(1,3)=6$ as maximal winning number, so $M=7$ is the smallest where the player can lose.

More generally, we can apply this reasoning at any level, because when we lose one health point, we have to search the remaining interval with $H-1$ health points. So we get the induction formula: $$M(H,T)=\sum_{i=1}^T (M(H-1,i-1)+1)=T+\sum_{i=2}^T M(H-1,i-1)$$

This gives a way to compute the wanted function, but I don't know of any closed formula that would be a solution for this induction relation.

ADDED

This problem is in fact the same as the one known as the Egg Dropping problem. An extensive discussion is present on the Wikipedia page on Dynamic Programming, which is a good reason to think there is no closed formula.

Answer 2

A game state of this game is a triple $(H,T,M)$ where $H$, $T$ are as you describe and $M$ is the number of possible hidden numbers $a_1<a_1<\ldots <a_M$. If I make a guess $a_m$ in this state (where $H\ge 0$ and $T>0$) then the following can happen:

• $a_m$ is the hidden number and I win
• If the hidden number is smaller, I continue with $(H-1,T-1, m-1)$ (which may mean I lost)
• if the hidden number is larger, I continue with $(H,T-1,M-m)$ (which may mean I lost)

The question is: What states $(H,T,M)$ allow a winning strategy? It is quite clear that there exists a function $M(H,T)$ such that $(H,T,M)$ is winnable iff $M\le M(H,T)$. We have $$M(H,1)=\begin{cases}1&\text{if }H\ge 0\\0&\text{if }H<0\end{cases}$$ because either the first guess must be correct or we don't even have a chance. We find a recursion by $T$ from the above case distinction: $$\tag1 M(H,T)= M(H-1,T-1)+M(H,T-1)+1\qquad\text{if }H\ge 0, T>0$$ By induction one sees that for fixed $H\ge 0$ the map $T\mapsto M(H,T)$ is a polynomial of degree $H+1$ for $T\ge 0$ and $0$ for $T<0$. Also, we find $$\tag 2 M(H,T) = 2^T-1\qquad\text{if }0\le T\le H+1.$$ Indeed this again follows by induction with the case $T=0$ being clear and otherwise from $(2)$ $$ M(H,T)=(2^{T-1}-1)+(2^{T-1}-1)+1=2^T-1.$$ Therfore, to compute $M(H,T)$, let $f_H$ be the polynomial of degree $H+1$ that is uniquely determined by the $\deg f_H+1$ values $(2)$; then $M(H,T)=f_H(T)$.

The first few polynomials can easily be found, I am still lookingfor a general closed formula:

$$\begin{align}M(0,T) &= T\\ M(1,T) &= \tfrac12T(T+1)\\ M(2,T) &=\tfrac16T(T^2+5)\\ M(3,T)&= \tfrac1{24}T(T+1)(T^2-3T+14)\\ M(4,T) &=\tfrac1{120}T(T^4-5T^3+25T^2+5T+94)\end{align} $$

The linear coefficient seems to be $\frac1{(H+1)!}\cdot $A024167.