Say that I choose an integer between 1 and 100 with uniform probability. Your goal is to determine the number I have chosen by guessing. Once you guess, I will tell you if that guess is too high or too low. You may make as many guesses as you wish, but may only guess too high twice.
What is the most efficient way to beat this game, and how do I prove that this method is the most efficient?
An obvious strategy is to guess 1, then 2, then 3, then ... until the nth guess is too high. Then n is the number.
A better strategy would be to guess 10, 20, 30, ... until you get a number too high (e.g. 30 is too high), then guess 21, 22, 23, ... until you are too high again, giving the answer.
Apparently, the best approach is to use the fact that 105 is the first triangular number over 100, and then guess 14, 14+13, 14+13+12, ..., until too high. This guarantees that in the worst possible case you make 14 guesses to win.
However, I can't prove to myself why this is the best approach.
My idea was to count how many guesses it would take to reach every number between 1 and 100 with a given strategy. The optimal strategy is then the strategy which minimizes the sum of all the guesses.
Eg with the triangular number setup:
| n | Number of guesses to guess n |
|---|---|
| 1 | 3 |
| 2 | 4 |
| 3 | 5 |
| ... | ... |
| 12 | 14 |
| 13 | 14 |
| 14 | 3 |
| ... | ... |
You can show quite easily that 14 is maximum number of trials you will have to run here.
Anyone know the name of this game? It's quite practical, e.g. minimise the number of trials to find the wattage that blows a lightbulb, you only have 2 lightbulbs to test with.
Even better, can anyone prove why a certain strategy is best?
EDIT: I know realize now you wanted to optimize the average number of drops, not worst case, so this answer is not relevant.
Here is a slick proof of optimality I got from this answer on Puzzling stack exchange.
Suppose you have a strategy which allows you to succeed in $n$ guesses. When you apply this strategy to a given chosen number, you will be told a sequence of $n$ responses which are all "too high" (H) or "too low" (L), where there are at most two H's. Furthermore, the collection of all possible response sequences must be distinct; if there were two chosen numbers which caused the same response sequence, then your strategy could not distinguish those two numbers.
Therefore, we need the number of possible response sequences to be at least $100$, one for each possible unknown number. The number of possible response sequences with $n$ guesses is $$ 1+n+\binom{n}2, $$ corresponding to the cases where there are zero, one, and two responses which are H. You can then check that the smallest value of $n$ for which that quantity is at least $100$ is $n=14$.
The same logic applies to when you can hear "too high" at most $k$ times, in which case you would instead have $1+n+\binom{n}2+\dots+\binom{n}k$ for the quantity which must meet or exceed the number of unknown numbers.