Shankar chooses a number between 1 and 10,000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. The caveat is that Geeta loses the game if her guess is larger than Shankar's chosen number two or more times. (A) How many guesses are necessary? (B) What if Shankar is allowed to pick an arbitrarily large positive number?

Heard from Ovidiu Gheorghioiu at Google in 2007.

(A) When Shankar chooses a number between 1 and n, Geeta should start guessing √n, 2√n, 3√n, 4√n, and so on. The first time her guess exceeds Shankar's number, the range of numbers has been narrowed down to √n numbers; she then starts guessing sequentially in that range.

(B) If Shankar guesses an arbitrarily large number n, then Geeta may guess 1, 4, 9, 16, 25, and so on, to discover k such that Shankar's number lies between k² and (k+1)². Then guess k²+1, k²+2, k²+3 and so on. On the whole, this requires O(√n) steps.

The Egg Game by W Gasarch and S Fletcher, 2008.