Probability Strategy over many games - 5 chance to guess a number between 1 ... 100 (inclusive) Hi All Maths / Probability Strategists,
I play a guessing game over a number of plays.
Rules:

*

*You must make a bet (fake coins) when you play - between 1 and 240

*Objective to guess a number between 1 and 100 (inclusive)

*You get 5 guesses

*Response is... correct, higher or lower

*If you lose, you lose your bet

*If you win, you keep your bet and win the same amount

*If you get right the first time - your winning is x10s your bet.

You play multiple times over a long period.
Obvious Strategy

*

*First guess 50

*Then 25 (+/- based on lower higher)

*Then 12 (+/- based on lower higher)

*Then 6 (+/- based on lower higher)

*Then pick a random number between the last 2.

Question

*

*Is there a more efficient strategy over time?

*Aka. If my first guess was 25; and it said lower - I've massively increased my chance of winning; higher obviously a different story.

*Or perhaps 1/3 is better, aka. 33 is the best first guess.

Feedback
Would love to hear, what strategies people would employ.
Thanks
 A: Suppose there are $n$ numbers and we are allowed $k$ guesses.  If $n\leq2^k-1$, then binary search will certainly succeed, so we assume $n\geq2^k$.  I claim that no method can give a success probability greater than $$\frac{2^k-1}n$$
When $k=1$, this is certainly true, because we can do no better than guess a number uniformly at random.  Suppose that the statement is true for $k$.  We shall prove it is also true for $k+1$, establishing the theorem by induction.  Let us choose a number that divides the domain into sets of $m$ smaller numbers and $n-m-1$ larger numbers, and suppose first that $m\geq2^k,\ n-m-1\geq2^k$.  There are $3$ ways we can succeed:

*

*The number we chose could be the secret number (probability
$\frac1n$).

*The number could be in the small domain (probability $\frac mn$) and we could guess it (probability $\frac{2^k-1}{m}$)

*The number could be in the large domain (probability $\frac{n-m-1}n$) and we could guess it (probability $\frac{2^k-1}{n-m-1}$)

This gives a total probability of $$\frac1n+\frac{2^k-1}n+\frac{2^k-1}n=\frac{2^{k+1}-1}n$$
Suppose instead that we choose a number so that one of the domains, say the small one has fewer than $2^k$ elements.  Then if the secret number lie in the small domain, we are certain to find it, and a computation like the one above shows that the probability of success is $$\frac1n+\frac mn+\frac{2^k-1}{m}\frac{m+2^k}n\leq\frac{2^{k+1}-1}n$$ since $m\leq2^k-1$.
So, how does binary search in the given problem compare to this optimum?  There are $15$ numbers we might choose as one of the first four guesses: $1$ possibility for the first, $2$ for the second, $3$ for the third, and $4$ for the fourth.  If none of these is the secret number, then the remaining $85$ intervals lie in $16$ intervals between the possible guesses, $11$ of length $5$ and $5$ of length $6$.  The probability of success in this case is $$\frac{55}{100}\frac15+\frac{30}{100}\frac16=\frac{16}{100}$$  Added to the probability that one of the guesses is the secret number, this gives $$\frac{31}{100},$$ the theoretical maximum.
EDIT
In an earlier version of this I had arrived at a probability of success of $\frac{30}{100}$ because I had miscounted the number of intervals of lengths $5$ and $6$.  But I've got it right now.  If $m$ is the number of intervals of length $5$, then $$5m+6(16-m)=85\implies m=11$$
A: Let's first consider pure strategies: strategies with no random element, where each guess can depend on nothing except the outcomes of previous guesses.
Any pure strategy with $5$ guesses has at most a $\frac{31}{100}$ chance of winning against a uniformly random number, because there can only be $31$ different numbers it can say:

*

*The first number must always be the same.

*The second number can depend only on the outcome of the first guess: higher or lower (because if it were correct, there's no point guessing anything else), so it can only have two values.

*The third number can depend only on the outcome of the first two guesses: (higher, higher) through (lower,lower). So it can only have four values.

*And so on. There are $2^k$ possible values the pure strategy can say after the first $k$ outcomes are known, for $1 + 2 + 4 + 8 + 16 = 31$ numbers total.

Since no pure strategy can do better, no mixed strategy (that makes random decisions at some point) can do better, because a mixed strategy is equivalent to somehow randomly choosing between one of several pure strategies.
There are many strategies that achieve the bound of $\frac{31}{100}$. For example, we can pick any $31$ elements of $\{1,2,\dots,100\}$, assume the correct number is one of those elements, and perform binary search on them.
