In the old days, navy officers were sometimes called "two-egg men". They used to get a ration of two eggs a day, one more than the ordinary able-bodied seaman. Nowadays, IT geeks often refer to the "two egg problem". This is an old programming problem which has been asked in many variations at job interviews.
Here's how it goes. A programmer is given two specially toughened, identical eggs and let loose in a building with a staircase of 100 stairs, where all the steps are of exactly the same height. The eggs will not break unless they are dropped from a certain minimum height. The "eggman" (who may of course, be an egg-woman) must bounce the eggs standing on the stairs, to figure out what that height is.
What is the minimum number of bounces that must be taken to figure out the height from which eggs must be dropped to break? This is a clever programming problem.
If there was only one egg, the egg would have to be bounced, starting at step 1. if it did not break at step 1, it would be bounced from step 2. Then, step 3, etc. , until it broke. This is very laborious.
However. with two eggs, the programmer can start at say, step 10. If the egg does not break, he can go to step 20. For example. If the egg broke when bounced at step 10, he could take the second egg and bounce it on every step starting at step 1. If it broke at step 9, it would take 10 bounces to find out.
If the egg broke when bounced at step 20, he takes the second egg and bounces it on step 11, step 12, etc. If the egg broke on step 19, this process takes 11 bounces. If the egg broke on step 29, it would take 12 bounces; if it broke on 99, it would take 19 bounces.
This is a two-stage process. First, figure out the range (1-10, 11-20, 21-30) within which the egg breaks. Then work out exactly where it breaks.
As we see above, the higher we go, the more bounces it takes. Is there any way to "average" out to a minimum number of bounces, no matter where the egg breaks?
There is. As we see above, if we go up by the same number of bounces on each range (10 steps each time here), the process may lengthen by 1 bounce for successively higher ranges.
Suppose we did not go up by the same number of steps on each range?
We could try to even it out by shortening ranges by taking one less step each time. If we bounce an egg on step 10 for example, and it does not break, try bouncing it on step 19 next time. That way if it does break at 19, we will need a maximum of 10 bounces to figure out the exact number of steps. if it does not break on 19, bounce it on step 27 next. Again a maximum of 10 bounces are required. However, a little calculation shows that, if you start by bouncing it from step 10, you will be walking up only 1 step by step 55 (assuming it does not break before that). Then you must repeat the whole formula and that is very inefficient.
Still, we're getting somewhere. What is the most efficient way to set the first initial range using a "diminishing" formula? Think algebraically. Say, the first range is set at "x ", The second range is x-1, the third is x-2. The final range must be 1 step. the sum must be 100 or as near 100 as possible.
Let's invert this range for convenient thought. We are now thinking of a series like 1,2,3, ... (x-2), (x-1), x. where the sum of the series is equal to (or slightly greater than) 100 and each term is 1 higher than the previous term. if you remember school algebra, this arithmetic progression is easy.
In case you don't remember, note that the first term (1) and last term (x) of the series will add up to x+1. So will the second (2) and second-last term (x-1) and the third (3) and third-last (x-2) term. if the total number of terms is N, the sum of the series will be (x+1)*N/2.
As we know from above, with 10 terms, the sum of the first and last terms is 11 and the series sums to 55. Given 12 terms, the sum of the first and last terms is 13, and the series sum is 78. With 14 terms, the sum is 105 and it's 91 with 13 terms. So, let's set x at 14.
The first range could be step 14, then step 27, 3, 50, 60, 69, 77, 84, 90, 95, 99. In this case, it will take a maximum of 14 bounces to locate the height at which the egg breaks. So 14 is the most efficient answer.
