Skip to main content

Guess a number (Find the floor in building that breaks egg)


I have a integer number M in my mind, a number between 1 and N where N is a big number. Chances for M to be any integer between 1 and N are the same. A friend tries to guess this number by asking me to compare M with another number, and I'll answer "your number is bigger", "smaller" or "correct". Another constraint is, his number can be bigger than or equal to M for up to 2 times. What is the strategy to figure out M with least questions?

A variation of this question is, in a N stories building, with 2 eggs, find the lowest floor from where egg breaks when it drops to ground.

Example answers

  • With only one egg, I can try the 1st floor, the 2nd, 3rd ... until the egg break. This strategy works but it's the worst.
  • Improved answer is, try 2, 4, 6, 8...until one egg breaks. Then use the other egg figure out answer.
  • Or, try 10, 20, 30, 40.... If egg breaks on 60, try 51, 52, 53... This is slightly better than previous answer, but might not be the best.

Follow this idea, assume the first egg is tried every X stories, then the total number of attempts is:

f(X) = N/2X + X/2.

When f(x) is minimized, df(x)/dx = 0. Which means: 1 - N/(X^2) = 0, therefore X=N^(1/2).

Enhance difficulty

What if there are 3 eggs? Assume the 1st egg is tried for every y stories, seconds is tried every x stories, and y=g(x), then the total number of attempts is:

f(x) = (N/g(x) + g(x)/x + x)/2.

When f(x) is minimized, its differential expression should be 0, which means:

1 + g'(x)/x - (g(x))^2/(x^2) - N * g'(x) / (g(x) ^ 2) = 0

When g(x) = x ^ 2 and N = x ^ 3, the equation stands. Therefore the answer is N^(2/3) stories for the first egg, N^(1/3) stories for the second egg and every story for the third one.

Next question

On top of what we found, what if we also what the worse case to be as good as possible? In previous analysis, the worse cases are 2 * N^(1/2) for two eggs and 3 * N^(1/3) for 3 eggs. The average number of guess can't be improved any more, since already made the differential result 0. But with some small adjustment, the worst case can be improved dramatically.


Popular posts from this blog

Spring, Angular and other reasons I like and hate Bazel at the same time

For several weeks I've been trying to put together an Angular application served Java Spring MVC web server in Bazel. I've seen the Java, Angular combination works well in Google, and given the popularity of Java, I want get it to work with open source. How hard can it be to run arguably the best JS framework on a server in probably the most popular server-side language with  the mono-repo of planet-scale ? The rest of this post walks through the headaches and nightmares I had to get things to work but if you are just here to look for a working example, github/jiaqi/angular-on-java is all you need. Java web application with Appengine rule Surprisingly there isn't an official way of building Java web application in Bazel, the closest thing is the Appengine rule  and Spring MVC seems to work well with it. 3 Java classes, a JSP and an appengine.xml was all I need. At this point, the server starts well but I got "No

Project Euler problem 220 - Heighway Dragon

This document goes through a Java solution for Project Euler problem 220 . If you want to achieve the pleasure of solving the unfamiliarity and you don't have a solution yet, PLEASE STOP READING UNTIL YOU FIND A SOLUTION. Problem 220 is to tell the coordinate after a given large number of steps in a Dragon Curve . The first thing came to my mind, is to DFS traverse a 50 level tree by 10^12 steps, during which it keeps track of a direction and a coordinate. Roughly estimate, this solution takes a 50 level recursion, which isn't horrible, and 10^12 switch/case calls. Written by a lazy and irresponsible Java engineer, this solution vaguely looks like: Traveler traveler = new Traveler(new Coordinate(0, 0), Direction.UP); void main() { try { traverse("Fa", 0); } catch (TerminationSignal signal) { print signal; } } void traverse(String plan, int level) { foreach(char c:plan) { switch(c) { case 'F': traveler.stepForward(); break; ca

Wreck-it Ralph is from Chicago?

Hotel Felix in Chicago   The building of Fix-it Felix Jr.