Number Guessing Game II


Shankar chooses a number uniformly at random between 1 and 1000. 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. If Geeta's guess is larger than the number, Shankar replaces the number with another number chosen uniformly at random [1, 1000]. What should Geeta's strategy be?


Heard from Ovidiu Gheorghioiu at Google in 2007.


Geeta repeatedly guesses a fixed number n-p. When Shankar's number is greater than n-p, Geeta starts guessing n-p+1, n-p+2, and so on. Since Shankar chooses a number uniformly at random in [1, n] the probability that his number equals or exceeds n-p is p/n. So the expected number of guesses is n/p. Thereafter, Geeta has to guess p/2 numbers on average, sequentially. Minimizing the sum n/p + p/2 yields p = .

Previous Puzzle: Cutting a Cake with Icing

One day, grandma baked a cake with a square top and dimensions 30cm x 30cm x 10cm. What is a simple strategy for cutting the cake into 9 equal pieces? The next day, grandma baked another cake with the same dimensions. This time, she put a thin layer of icing on top and on all four sides but not on the bottom. What is a simple strategy for cutting such a cake into 9 pieces such that all pieces have the same amount of cake by volume and the same amount of icing by surface area?

How many cuts are necessary to cut an n x n x n cube into 1 x 1 x 1 cubes? Existing cuboids may be stacked together for cutting. So one cut may go through multiple existing cuboids.

16 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.