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^{2} and (k+1)^{2}. Then guess k^{2}+1, k^{2}+2, k^{2}+3 and so on. On the whole, this requires O(√n) steps.

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

© Copyright 2008—2017, Gurmeet Manku.