Can you solve the egg drop riddle

你能解決雞蛋掉落之謎嗎

來源視頻

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.

這個城市剛剛開了一家?別具一格的俄羅斯彩蛋博物館，一棟每層只展出一個蛋?的100層建筑。

全世界最臭名昭著的珠寶大盜 已經(jīng)鎖定了她的目標。

因為安保很嚴，蛋又很大， 她只有一次得手的機會，把蛋丟到下面接應的卡車，然后在警察到來之前撤退。

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

每個蛋的重量和構(gòu)造都是一樣的，但是每一層的蛋都比 下面一層的更值錢。

大盜自然想拿最頂層的無價之蛋，她覺得這個蛋不會 在掉落一百層后還完好無損。

務實的她決定去偷 她能成功偷到的最貴的蛋。在博物館的禮品店， 她找到了兩個紀念蛋，完全不值錢但復制得很完美。

她的計劃是把它們從高處扔下來，看看它們能在最高的哪層掉落還能完好無損。

當然，兩個紀念蛋都碎了的時候就不能繼續(xù)試驗了。

而且從窗戶往外扔蛋太多次會引起保安的注意。

她最少實驗幾次就能保證她找到對的層數(shù)？

【如果你愿意的話， 暫停一下，自己想一想?！?/p>

【答案在三秒后出現(xiàn)，二秒，一秒?！?/p>

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.

如果你覺得無從下手的話，可以簡化一下情景。

想像一下如果大盜只有一個蛋。

她就只有一個選擇：從第一層開始，一層層上去，直到蛋碎了。

那她就知道下面那層就是她真正需要搶劫的目標。

但是要試一百次。

有第二個復制蛋 給了她更好的選擇。

她可以先用大間隔測試，以縮小實驗范圍。

第一個蛋碎了以后，她就可以用第二個蛋 在間隔內(nèi)一層層試了。

太大的間隔不太有效。

在最糟的情況下， 第二只蛋要試好多層。

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.

小間隔好用多了。

打個比方，如果她每十層丟一次，蛋碎了之后就只要試之下的九層。

這就意味著最多十九次 就能找到正確的層數(shù)。

但是她還能做得更好嗎？

畢竟，每一間隔不需要一樣大。

如果只有十層，大盜可以四下試完，從四層開始，七層，九層。

如果在第四層碎了， 就只要扔三次第二個蛋，就能找到準確層數(shù)。

如果在第七層碎了，就只要再扔兩次。

如果在第九層碎了，就只要再試一次。

實際上我們在試圖將建筑物分區(qū)，無論哪一層是對的，都可以用同樣的次數(shù)找到。

我們要每一個間隔 都比下面的少一層。這個公式能幫我們 找到一百層內(nèi)開始扔蛋的層數(shù)。

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.

這個式子有幾種解法，包括反復試驗。

如果我們代入 2，等式就是這樣。

如果我們代入 3，等式就是這樣。

因此我們通過增加 n 的值， 就可以找到讓左邊總和超過 100 的 最小的 n，也就是 14。

因此，我們的大盜 應該從第十四層開始，再到二十七層，三十九層，等等，最多十四下就可以找到正確的層數(shù)。

就像老話說的， 不打碎幾個蛋就搶不了劫。