Advertisement
Friday, Jan 28, 2022
Outlook.com
Outlook.com
Opinion

Fractal Logic

What is the minimum number of bounces that must be taken to figure out the height from which eggs must be dropped to break?

Fractal Logic
Fractal Logic
outlookindia.com
2016-02-16T12:41:54+05:30

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.

Advertisement

Outlook Newsletters

Advertisement
Advertisement
Advertisement

Read More from Outlook

Lament Of Separation: Songs Of Habba Khatun, Last Queen Of Kashmir, Still Echo In Valley

Lament Of Separation: Songs Of Habba Khatun, Last Queen Of Kashmir, Still Echo In Valley

In happy times and sad, Habba Khatun’s sensuous songs make both young and old emotional. With the never-ending conflict bringing tragedies to every doorstep, Habba’s lyrics of separation amplify their mourning.

How Indian Laws Govern People’s Right To Love And Live

How Indian Laws Govern People’s Right To Love And Live

In India, only those relationships between a man and a woman are considered to be legitimate when there is a marriage between the two.

Kohli Quits Test Captaincy, Leaves Leadership Vacuum

Kohli Quits Test Captaincy, Leaves Leadership Vacuum

Virat Kohli, 33, had recently stepped down as India's T20I captain and was subsequently removed as the ODI captain.

UP Elections 2022: How Congress Is Harnessing Power Of 'Persecuted' Women To Counter BJP

UP Elections 2022: How Congress Is Harnessing Power Of 'Persecuted' Women To Counter BJP

A Mahila Congress leader, who is the face of the ‘Ladki Hoon, Lad Sakti Hoon’ campaign, however, has accused the party of anti-women bias after she was denied a ticket.

Advertisement