Super Strong Eggs-- I

Logic Level 3

You are given access to a 100-storey building and an infinite number of eggs. The eggs are identical.

The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

Adopting the best strategy, what is the absolute minimum number of egg drops that you need to reach the solution given any scenario (Including worst case)?

Details and Assumptions : - Issues related to terminal velocity, potential energy or wind resistance are immaterial.

You can solve Super Strong Eggs --- II here .

The answer is 7.

7 solutions

Satyen Nabar
Mar 19, 2014

First we go to floor $50$ and drop an egg. It either breaks, or it does not. The result of this drop reduces our problem in half.

If it breaks, we know the solution lies in the bottom half of the building viz floor $1 - 49$ . If it survives, we know the solution is in the top half of the building viz floor $51 - 100)$ . On each drop, we keep dividing the problem in half and half again until we get to our solution.

Number of drops required for this solution is $log2 n$ , where $n$ is the number of floors of the building.

Because this building does not have a number of floors equal to a round number power of two, we need to round up to number of drops to get seven $( log2 100 = 6.644)$ .

binary method!

vaibhav setia - 7 years, 2 months ago

Yes great vaibhav now try strong eggs 2

Satyen Nabar - 7 years, 2 months ago

Dear Fiso if the egg breaks its not available for dropping again!

Satyen Nabar - 7 years, 2 months ago

Technicality, but can you point out if I'm missing something? The worst case for a binary search is if the element is located at the very end of the series, ie. in this case the 100th floor for instance. In that case , you'd drop eggs from floor number 50, 75, 87, 93, 96, 98, 99 (which is the 7 drops coming from log(100,2). But we still don't know if the egg breaks from the 100th floor or not - so we need to do one more drop. That's why I feel the answer is 8 and not 7.

I also think the answer is sensitive to whether we round up or down while halving - of course this depends on whether the search element is located above or below the "current" floor.

Adithya MR - 7 years, 2 months ago

50 75 88 94 97 99 100

By binary method 2^7, you can check up to 128 floors with 7 drops

Satyen Nabar - 7 years, 2 months ago

Since the eggs are identical and other "issues" are not being considered, you could choose any single egg and drop it from the lowest story. If it didn't break, none of the other eggs would break either — but the experiment would still have to continue. If it did break, all the eggs would break, and you would have ascertained the minimum number of egg drops needed after just one attempt.

If you started by dropping an egg from the highest storey and it survived the fall without breaking, so would every other egg, and the experiment would likewise be over after just one attempt. If it broke, testing would have to continue.

So whether you start on the lowest or the highest story, if you're lucky, you would require just one egg drop.

HOWEVER ...

If the eggs are composed of some adamantine material that has been previously tested and accurately determined to be unbreakable — and no other issues are being considered — then you wouldn't need to drop a single egg. Logically, you can't assume this is not the case because the problem doesn't exclude that possibility. It says nothing about the physical composition of the eggs.

There is another logical problem: an infinite number of eggs of any material would be infinitely massive, and logically could not exist in the same reality as long as "you" — who are not an egg — also exist. They would occupy infinite space, leaving no room for a "you." Unless the problem stipulates that the eggs somehow have no mass, it is impossible to give a definitive answer. Further conditions would have to be established.

Joseph Ford - 4 years, 11 months ago

Gowtham Subramanian
Mar 26, 2014

Divide number of floors with 2, and try till it reach 1. So, The attempts we have made is possible solution. Here, 50,25,12,6,3,2,1 (.5 is consider as whole number) Hence, 7 tries for 100 floors. Simple :)

Ronq Vader
Mar 25, 2014

This one is very closely related to Binary Search which we employ in many Computer Science.The worst case scenario for such an algorithm is log2 100 =6.644 which in turn can be rounded up to 7

Utkarsh Bhatt
Jan 28, 2015

Use the method of tree based searches in computer programs.... Binarily. Drop an egg from 50 th floor... If it breaks then drop next from the floor in between 0 and 50 ie 25 floor...... Else from the floor from just between 100 and 50 keeping this on using exponential functions you get n such that 2^n is just >= 100. N comes 7.

Milly Choochoo
Mar 20, 2014

Just try to always cut everything in half. (e.g. start at 50, then you'll know which half [bottom of top] to go after next. If you repeat this process, you only need 7 drops)

You only need 7 drops because no matter which way you go after the initial half, every 'half' after that will be identical.

Milly Choochoo - 7 years, 2 months ago

A Former Brilliant Member
May 23, 2017

Use Binary Search Max. eggs = $\left \lceil \lg 100 \right \rceil$

Joseph Burns
Jun 23, 2016

I have used this method when looking at security camera footage to see when retail items went missing. I start at the most recent known time when the item is there, cut the time in half, see if the item is still there, and repeat. It let's me get through a whole day's worth of video in about 10 minutes.

Super Strong Eggs-- I

You can solve Super Strong Eggs --- II here .

The answer is 7.

7 solutions

0 pending reports