Can you solve the egg drop riddle? – Yossi Elran

Can you solve the egg drop riddle? – Yossi Elran


The city has just opened its
one-of-a-kind Fabergé Egg Museum with a single egg displayed on each floor
of a 100-story building. And the world’s most notorious jewel thief
already has her eyes on the prize. Because security is tight
and the eggs are so large, she’ll only get the chance to steal one by dropping it out the window
into her waiting truck and repelling down
before the police can arrive. All eggs are identical in weight
and construction, but each floor’s egg is more rare
and valuable than the one below it. While the thief would naturally like
to take the priceless egg at the top, she suspects it won’t survive
a 100-story drop. Being pragmatic, she decides to settle
for the most expensive egg she can get. In the museum’s gift shop,
she finds two souvenir eggs, perfect replicas
that are perfectly worthless. The plan is to test drop them to find the highest floor
at which an egg will survive the fall without breaking. Of course, the experiment
can only be repeated until both replica eggs are smashed. And throwing souvenirs out the window
too many times is probably going to draw
the guards’ attention. What’s the least number of tries
it would take to guarantee that
she find the right floor? Pause here if you want
to figure it out for yourself! Answer in: 3 Answer in: 2 Answer in: 1 If you’re having trouble getting started
on the solution, it might help to start
with a simpler scenario. Imagine our thief only
had one replica egg. She’d have a single option: To start by dropping it
from the first floor and go up one by one until it breaks. Then she’d know that the floor below that is the one she needs
to target for the real heist. But this could require
as many as 100 tries. Having an additional replica egg
gives the thief a better option. She can drop the first egg from different
floors at larger intervals in order to narrow down the range
where the critical floor can be found. And once the first breaks, she can use the second egg to explore
that interval floor by floor. Large floor intervals don’t work great. In the worst case scenario, they require
many tests with the second egg. Smaller intervals work much better. For example, if she starts by dropping
the first egg from every 10th floor, once it breaks, she’ll only have to test
the nine floors below. That means it’ll take at most
19 tries to find the right floor. But can she do even better? After all, there’s no reason
every interval has to be the same size. Let’s say there were only ten floors. The thief could test this whole building
with just four total throws by dropping the first egg
at floors four, seven, and nine. If it broke at floor four, it would take
up to three throws of the second egg to find the exact floor. If it broke at seven, it would take up to two throws
with the second egg. And if it broke at floor nine, it would take just one more
throw of the second egg. Intuitively, what we’re trying to do here
is divide the building into sections where no matter which floor is correct, it takes up to the same number
of throws to find it. We want each interval to be one floor
smaller than the last. This equation can help us solve
for the first floor we need to start with in the 100 floor building. There are several ways
to solve this equation, including trial and error. If we plug in two for n,
that equation would look like this. If we plug in three, we get this. So we can find the first n to pass 100 by adding more terms
until we get to our answer, which is 14. And so our thief starts on the 14th floor, moving up to the 27th, the 39th, and so on, for a maximum of 14 drops. Like the old saying goes, you can’t
pull a heist without breaking a few eggs.

100 thoughts on “Can you solve the egg drop riddle? – Yossi Elran”

  1. Thank you so much to everyone who has supported our nonprofit mission on Patreon! You make this work possible. Want to learn more about how you can get involved? Check out our Patreon page: http://bit.ly/2zn58I6

  2. Well,you would need aim of Johnny Wick to get the egg in the truck from a height greater than 10 floors.Also,an alternative solution would be to put some really soft stuff in the truck,like a layer of hay,then one of pillows,then one of feathers and cover the egg in flex tape.

  3. Won't the 1st egg weaken when it is thrown so many times, since it weakens it may break faster, so it might break on a lower floor

  4. Why not start at 50th floor & divide the section into half each time. For example – if it doesn't break in floor 50, the upper half section has to be tested. We will then move to floor 75 and we will reduce our search by half again. In this way, the section size will go like – 50, 25, 12, 6, 3, 2, 1. That is, a maximum of 7 throughs is needed to find the floor.

  5. This is a very famous dynamic programming question, where we can find the minimum egg drops for any number of floors and eggs.

  6. Throw the egg from the middle of the building. If broke go to the middle of the middle below, else go to the middle of the middle above. Repeat until find the correct floor.

  7. I would use a goddang rope and jump off with the priceless because the staff isn’t suspicious about eggs falling from the sky,

  8. starting from ground floor > 50 25 12 6 3 1
    Sum or Subtract the numbers and you should be there with 6 eggs

    Survive = Sum
    Breaks = Subtract

  9. Or I could replase the Perfect replikas with there counter parts but First I Gota sadnuce the Guards with my legs and then knock em out

  10. But why don't you split the floors in half each time instead? That would only use 7 eggs.. That's what programmers use when writing a set of code that finds a specific number. Start with 50, if it broke at 50, you've narrowed it down to numbers less than 50. If it didn't break at 50, you've narrowed it down to numbers higher than 50. It only takes 7 tries to narrow the answer down to one floor by splitting the remaining group in half each time 😛

  11. ORR pretend to be pregnant then go to the most valueble egg and stuff it in your hollow styrofoam ball (half of the ball) and walk out so my question is
    WILL IT WORK

  12. I got 7 as an answer if there were more eggs in the gift shop because you can throw it at the 50th floor. If it breaks, you throw it at 25. If it breaks again, throw it at 13. If it breaks again, throw it at 7 and so on. It works for both ways even if it doesn't break because then you can just go in the opposite direction while still having halved the amount of floors that you have to try.

  13. 2 mistakes. One, if all are exactly the same, one can't be rarer and more valuable than another. Two, it should be "What's the least number of times it would take to guarantee that she finds the right floor," not FIND the right floor

  14. Beelzebub +297 Descended on PADX redirected me here.
    http://www.puzzledragonx.com/en/mission.asp?m=3435
    Comment section

  15. If there are many trials possible, and she can go down to collect the replica egg timely, Can't we make it more easier to just replace the top floor egg with replica and run away?? Just one trial needed.

  16. So how do you prove that with equal intervals of floors, 19 is the answer?
    Make x chunks of the total number of floors. So each chunk has 100/x floors in it.
    Suppose the egg breaks on floor 99 (because this will give us the maximum number of tries).
    First, we throw the first egg after each 100/x number of floors. So we end up trying the first egg x times until it breaks on floor 100.
    Next, we try the second egg 100/x – 1 times and it breaks on floor 99.
    So the goal is minimize: x + 100/x – 1
    take first derivative and equate to zero, we get x=10
    take second derivative, and we get it to be positive at x=10.
    therefore, at x=10, that equation has the minimum value.
    So total number of tries = 10 + 100/10 – 1 = 19

    Thank me if you want to. This is what I did before I heard him say that we don't need equal intervals of floors -_-

  17. Answer will be 7. Because it just like searching algo. With answer ceil(log 100).
    In 7th search any required floor will be found please like if u agree so that it will be in top….i hope computer science student will understand.

  18. Thief: throws 14 eggs
    Guard: oh well I guess you tried

    Also the police would have arrive already by throwing 14 eggs

  19. Thief: Repels down the building after dropping the egg using a rope. Drops 14 sample eggs to get the most valuable one.
    Also Thief: Can't carry a bag and simply repel down the rope with the egg on the 100th floor in her backpack easily and drive away.

  20. I can solve it in less time trying.
    First you will try from 50 if breaks then 25 if breaks then 13 if breaks then 7 if breaks then 4 if breaks then 2 and so on. This needs highest 6 try.

  21. i thought he said that he couldn’t get the egg after it’s dropped even if it doesn’t break and i was just so unbelievably lost

  22. Can't we do this with 7 times of tries?
    Using 50, 25, 12.5, 6.25, 2.125, 1.5625.
    Halve the floors, 1st try on 51 floor. If not crashed, go on to 76 floor and if crashed, go down to 26 floor.
    Guessing that the egg isn't break on lower floors. 3rd try on 88, 4th 94, 5th 97, 6th 99.
    If the 99 floor egg doesn't crash, we have to do 100 floor for the last 7th.
    The answer was 14 times, double of my answer. Maybe I missed something but not sure.

  23. It can be done with 7 eggs only:
    Egg 1: At (midpoint) 50th floor (Remaining left :50;either below or above this floor)
    Egg 2: At (midpoint) 25th (or 75th) floor (Remaining left :25;either below or above this floor)
    Egg 3: At (midpoint) 13th (87th) floor (Remaining left :13;either below or above this floor)
    Egg 4: At (midpoint) 7th (93rd) floor (Remaining left :7;either below or above this floor)
    Egg 5: At (midpoint) 4th (96th) floor (Remaining left :3;either below or above this floor)
    Egg 6: At (midpoint) 2nd (98th) floor (Remaining left :1;either below or above this floor)
    Egg 7: At 1st or 100th floor for the worst case.

  24. Ted ed, you make great vidoes. Explanation and animations are great. I love to watch these videos. Very interesting and knowledgeable. Can you make a video on HALTING PROBLEM in Turing maching and its proof by contradiction. It will be great.

  25. This is how to do it in 7 tries.. start with the 50th floor
    if egg survives, drop it from the 75th floor, otherwise drop another egg from the 25th floor
    then +13 floors if the egg survives or -13 floors if the egg breaks
    then +6 floors if the egg survives or -6 floors if the egg breaks
    then +3 floors if the egg survives or -3 floors if the egg breaks
    then +2 floors if the egg survives or -2 floors if the egg breaks
    then +1 floors if the egg survives or -1 floors if the egg breaks

  26. Start with 50.
    If it breaks, than try 25.
    If 25 breaks, steal 10.
    If 25 doesn’t break, then toss an egg out of each floor after 25 until you find the floor on which it breaks, steal egg on floor below.
    If 50 doesn’t break, try 75.
    If 75 breaks, then toss an egg out of each floor after 50 until you find the floor on which it breaks, steal egg on floor below.
    If 75 doesn’t break, then toss an egg out of each other floor after 75 until you find the floor on which it breaks, test the floor below it.
    If that floor doesn’t break the egg, then steal the egg on that floor.
    If that floor does break the egg, then steal the egg on the floor below that.

  27. This has nothing to do with the video but I just saw an ad by citi about the totally legitimate "wage gap" but the fact is wemon go into lasser paying jobs then expect to get paid more/equal for lesser work and wonder why they don't get it, now you can argue a point but that will prove mine so… have fun

  28. Did anybody notice that it said “What’s the least number of tries it would take to guarantee she FIND the right floor?”

  29. You can do it in 9, if you follow this:
    1) (2drops) Drop from 100 and 1, if it breaks at 1 then you have the answer, and if it is fine at 100 you have answer. If neither, then got to next step.

    2) (1 drop)If broken at 100, and safe at 1, then drop from floor 50. If it breaks, then you know that it is a floor between 1 and 50, if fine, then it is between 50 and 10.

    3) @TED-ED Continue this half pattern until you get to a floor at which the egg will not break. If you get to decimals, round DOWN regardless the decimals. (both 5.1 and 5.9 will round to 5). This in total, will lead to a maximum of 9 drops from start to finish. You are welcome.

  30. It's easy. Just go to the egg with a guitar image on it, smash it to see it contains a harp, go to the egg with a harp image, etc etc, confirm you have green eyes, insert a blue egg, and drop 5 units of fuel at 8 parsecs.

  31. Well, you can solve the riddle with just 6-7 drops … just keep cutting the number of floors in half while dropping the egg, until you find your sweet spot

  32. Wait but if the robber can slide down after dropping the egg in the heist, can she just, you know,

    slide down with the 100th-floor-egg instead of wasting 30 bucks and time?

  33. Or you coukd like calculate the energy your egg will gain because of its fall and its resistance and deduce the ideal height

  34. Wouldn't it be much easier to go the 50'th floor, and depending whether the egg breaks or not, to go to the 75'th or to the 25'th? Then divide by two each interval until it reaches to the desired floor?

Leave a Reply

Your email address will not be published. Required fields are marked *