1
$\begingroup$

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?

$\endgroup$
6
  • 6
    $\begingroup$ Google on "egg drop problem". $\endgroup$ Jan 26, 2021 at 18:34
  • $\begingroup$ What precisely do you mean by "most efficient"? $\endgroup$ Jan 26, 2021 at 18:35
  • $\begingroup$ So, to verify, the only way to know what the answer is will be to get a result of "too high" immediately above a result of "too low"? You never answer "correct" but rather "too low" or "too high"? $\endgroup$
    – abiessu
    Jan 26, 2021 at 18:37
  • $\begingroup$ egg drop problem is perfect! Had no idea what to google. In response to the other comment, in the egg drop scenario, you don't have a "correct" you are just looking for the largest integer where the egg doesn't drop $\endgroup$
    – djones
    Jan 26, 2021 at 18:49
  • 1
    $\begingroup$ Your strategy minimizes the worst case number of drops. For minimizing the expected number of drops, see math.stackexchange.com/questions/3060542/… $\endgroup$ Jan 26, 2021 at 19:40

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Sorry, for the very late reply. You're right its not quite what I was looking for, but in any case this one of the most beautiful examples of mathematical elegance I have ever seen! Thanks very much! $\endgroup$
    – djones
    Jan 30, 2021 at 22:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .