Can you solve the egg drop riddle? - Yossi Elran

Переводчик: Ola Królikowska Редактор: Yulia Kallistratova

[«Много людей боятся высоты. Но не я, я боюсь ширины» — Стивен Райт]

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

[Ответ через: 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,

Например, если начать сбрасывать яйцо с каждого десятого этажа,

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.

Это значит, что требуется до 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

Воровка могла бы протестировать целое здание всего за четыре сброса,

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.

Если вместо n подставить двойку, это уравнение будет выглядеть так.

If we plug in three, we get this.

Если подставим тройку, то получим вот это.

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.

Как говорится в старой поговорке, нельзя сделать омлет, не разбив пары яиц.