Can you solve the egg drop riddle? - Yossi Elran

Translator: Pavlina Koleva Reviewer: Anton Hikov

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.

с по едно единствено яйце изложено на всеки етаж от 100 етажната сграда.

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.

тя предполага, че то няма да издържи на падане от 100-тния етаж.

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

Отговор след: 3

Answer in: 2

Отговор след: 2

Answer in: 1

Отговор след: 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.

Но това би отнело до 100 опита.

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,

Примерно, ако започне с пускането на първото яйце на всеки 10 етажа,

once it breaks, she'll only have to test the nine floors below.

щом се счупи, ще трябва да изтества само 9-те етажа надолу.

That means it'll take at most 19 tries to find the right floor.

Което значи, че ще са нужни най-много 19 опита, за да открие правилния етаж.

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

Крадлата може да изтества цялата сграда само с 4 хвърляния сумарно

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

Ако се счупи на етаж 4, ще отнеме до три хвърляния на второто яйце,

to find the exact floor.

за да намери точния етаж.

If it broke at seven,

Ако се счупи на 7,

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.

от 100 етажната сграда.

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.

Ако сложим n да бъде 2, уравнението ще изглежда така.

If we plug in three, we get this.

Ако изберем 3, получаваме това.

So we can find the first n to pass 100

Така можем да намерим първото n, което надминава 100,

by adding more terms until we get to our answer,

добавяйки още докато не получим отговор,

which is 14.

който е 14.

And so our thief starts on the 14th floor,

И така нашата крадла започва от 14-тия етаж,

moving up to the 27th,

преминава към 27-мия,

the 39th,

39-тия

and so on,

и така нататък

for a maximum of 14 drops.

за максикум 14 хвърляния.

Like the old saying goes, you can't pull a heist without breaking a few eggs.

Както казва поговорката,

не можеш да направиш обир без да счупиш няколко яйца.