Can you solve the egg drop riddle? - Yossi Elran

Fordító: Andi Vida Lektor: Maria Ruzsane Cseresnyes

The city has just opened its one-of-a-kind Fabergé Egg Museum

Alig hogy megnyílt a városban egy különleges Fabergé Tojásmúzeum,

with a single egg displayed on each floor of a 100-story building.

a százszintes épület minden egyes emeletén egy-egy tojással,

And the world's most notorious jewel thief already has her eyes on the prize.

a világ leghírhedtebb ékszertolvaja máris szemet vetett a prédára.

Because security is tight and the eggs are so large,

Mivel szigorúan őrizték, és nagyok voltak a tojások,

she'll only get the chance to steal one

csak úgy volt esélye ellopni egyet,

by dropping it out the window into her waiting truck

hogy kidobja az ablakon egy ott várakozó teherautóba,

and repelling down before the police can arrive.

és utánaereszkedik, mielőtt kiérkezik a rendőrség.

All eggs are identical in weight and construction,

Minden tojás egyforma súlyú és felépítésű volt,

but each floor's egg is more rare and valuable than the one below it.

de felfelé haladva egyre értékesebbek és különlegesebbek voltak a tojások.

While the thief would naturally like to take the priceless egg at the top,

A tolvaj természesen a legértékesebb tojást vinné el a legfelső szintről,

she suspects it won't survive a 100-story drop.

ugyanakkor kétségei vannak, az kibírná-e a százemeletes zuhanást.

Being pragmatic, she decides to settle for the most expensive egg she can get.

Úgy dönt, meghatározza, melyik a legdrágább tojás, amit meg tud szerezni.

In the museum's gift shop, she finds two souvenir eggs,

A múzeum ajándékboltjában talál két tojást,

perfect replicas that are perfectly worthless.

teljesen értéktelen, ám tökéletes másolatokat.

The plan is to test drop them

Az a terve, hogy próbadobásokkal

to find the highest floor at which an egg will survive the fall

meghatározza, melyik az a legmagasabb emelet, ahonnan ledobva

without breaking.

még nem törnek össze.

Of course, the experiment can only be repeated

A kísérletet persze csak addig ismételheti,

until both replica eggs are smashed.

míg mindkét másolat össze nem törik.

And throwing souvenirs out the window too many times

És valószínűleg felkelti az őrök figyelmét,

is probably going to draw the guards' attention.

ha túl sokszor dobál ki ajándéktárgyakat az ablakból.

What's the least number of tries it would take

Legalább hány próbálkozásra van szüksége ahhoz,

to guarantee that she find the right floor?

hogy mindenképp megtalálja a megfelelő emeletet?

Pause here if you want to figure it out for yourself!

Itt most ne folytassa, aki saját maga akarja megoldani a feladatot!

Answer in: 3

Jön a válasz: 3...

Answer in: 2

2...

Answer in: 1

1...

If you're having trouble getting started on the solution,

Aki nehezen fog hozzá a megoldáshoz,

it might help to start with a simpler scenario.

annak segíthet egy egyszerű forgatókönyv.

Imagine our thief only had one replica egg.

Képzeljék el, hogy a tolvajnál csak egy tojásmásolat van.

She'd have a single option:

Egy választási lehetősége van:

To start by dropping it from the first floor

Először az első emeletről dobja ki,

and go up one by one until it breaks.

majd egyesével megy felfelé, míg a tojás össze nem törik.

Then she'd know that the floor below that

Akkor megtudja, hogy az előző emelet az,

is the one she needs to target for the real heist.

ahol le kell bonyolítania az igazi rablást.

But this could require as many as 100 tries.

De lehet, hogy ez száz próbálkozást igényelne.

Having an additional replica egg gives the thief a better option.

Ha van még egy másolat a birtokában, jobbak a lehetőségei.

She can drop the first egg from different floors at larger intervals

Az első tojás ledobásakor kihagyhat emeleteket,

in order to narrow down the range where the critical floor can be found.

hogy kevebbet próbálkozzon a megfelelő emelet megtalálásához.

And once the first breaks,

Amikor az első összetörik,

she can use the second egg to explore that interval floor by floor.

már csak az utolsó kihagyott intervallum emeleteit kell végigjárnia a másodikkal.

Large floor intervals don't work great.

Nem jó, ha túl nagy közöket hagy ki az egyes emeletek között.

In the worst case scenario, they require many tests with the second egg.

Rossz esetben így túl sok kísérlet jut a második tojásra.

Smaller intervals work much better.

Előnyösebb kis kihagyásokkal dolgozni.

For example, if she starts by dropping the first egg from every 10th floor,

Ha például az első tojást minden tizedik emeletről dobja ki,

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

mikor összetörik, csak az alatta lévő kilenc emeletet kell végigjárnia.

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

Vagyis összesen maximum 19 próbából eltalálja, melyik a megfelelő szint.

But can she do even better?

De lehet-e még vajon ezen javítani?

After all, there's no reason every interval has to be the same size.

Végül is, nem muszáj egyforma kihagyásokkal dolgozni.

Let's say there were only ten floors.

Tegyük fel, hogy csak tíz szint van.

The thief could test this whole building with just four total throws

A tolvajnak négy dobás is elég arra, hogy az egész épületet bevizsgálja úgy,

by dropping the first egg at floors four,

hogy az első tojást a negyediken, a hetediken

seven,

és a kilencediken

and nine.

dobja ki.

If it broke at floor four, it would take up to three throws of the second egg

Ha a negyediken összetörik, marad három dobása a második tojással,

to find the exact floor.

hogy megtalálja azt a bizonyos emeletet.

If it broke at seven,

Ha a hetediken törik el,

it would take up to two throws with the second egg.

még két dobásra lehet szüksége,

And if it broke at floor nine,

Ha pedig a kilencediken,

it would take just one more throw of the second egg.

akkor egy dobásra a második tojással.

Intuitively, what we're trying to do here is divide the building into sections

Intuitíven: azzal próbálkozunk, hogy részekre osztjuk az épületet, úgy,

where no matter which floor is correct,

hogy függetlenül attól, melyik szint az igazi,

it takes up to the same number of throws to find it.

mindenképp ugyanannyi próbálkozásra legyen szükségünk.

We want each interval to be one floor smaller than the last.

Minden kihagyott intervallum legyen egy emelettel rövidebb az előzőnél.

This equation can help us solve for the first floor we need to start with

Ez az egyenlet segíthet meghatározni, hogy a százszintes épület

in the 100 floor building.

melyik szintjén kezdjük a próbálkozást.

There are several ways to solve this equation,

Többféleképp megoldható ez az egyenlet. Próbálkozások és tévedések is

including trial and error.

beleférnek.

If we plug in two for n, that equation would look like this.

Ha n-et 2-nek vesszük, egyenletünk így fog kinézni.

If we plug in three, we get this.

ha 3-mal helyettesítjük be, ezt kapjuk.

So we can find the first n to pass 100

Így eljutunk az első n-hez, ami eléri a 100-at,

by adding more terms until we get to our answer,

mindig több tagot adva hozzá, addig, míg meg nem kapjuk az eredményt,

which is 14.

ami 14.

And so our thief starts on the 14th floor,

Így tolvajunk a 14. emeleten kezd,

moving up to the 27th,

onnan felmegy a 27-re,

the 39th,

onnan a 39-re,

and so on,

és így tovább,

for a maximum of 14 drops.

a legfeljebb 14 dobásért.

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

A régi szólást idézve: aki rabolni akar, az törjön fel néhány tojást.