Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Number Guessing Game

Puzzle

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?

Source

Heard from Ovidiu Gheorghioiu at Google in 2007.

Solution

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

Followup

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

Previous Puzzle: Two Eggs and a Building

With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped? Followup: What if the number of floors of the building is unknown?

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?

12 Sep 2010
© Copyright 2008—2017, Gurmeet Manku.