Can you solve the egg drop riddle? - Yossi Elran

譯者: chenching teng 審譯者: Helen Chang

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.

但她不能確定 蛋從 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

從 1 樓開始摔它

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.

這代表最多只要 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,

方法是依序從 4 樓

seven,

7 樓

and nine.

和 9 樓丟下第一顆蛋

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,

如果在 9 樓破了

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 等於 2 代入 式子看起來會像這樣

If we plug in three, we get this.

如果代入 3 ，我們得到這個

So we can find the first n to pass 100

所以我們可以藉由增加更多項

by adding more terms until we get to our answer,

直到超過 100 也就是我們需要的答案

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.

而最多只需要丟十四次

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

就像俗話所說的 不破雞蛋 焉得打劫？