Can you solve the egg drop riddle? - Yossi Elran

Tradutor: Margarida Ferreira Revisora: António Ribeiro

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

A cidade abriu o Museu dos fabulosos Ovos Fabergé,

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

com um único ovo exposto em cada piso num edifício de 100 andares.

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

A ladra de joias mais conhecida do mundo já tem os olhos postos na presa.

Because security is tight and the eggs are so large,

Como a segurança é apertada e os ovos são muito grandes,

she'll only get the chance to steal one

ela só pode roubar um deles

by dropping it out the window into her waiting truck

atirando-o pela janela para um camião que está lá em baixo à espera

and repelling down before the police can arrive.

e esgueirando-se antes de a polícia chegar.

All eggs are identical in weight and construction,

Os ovos são todos idênticos em peso e fabrico,

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

mas em cada piso, o ovo é mais raro e mais valioso do que o do piso de baixo.

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

Embora a ladra gostasse de levar o ovo sem preço do último piso,

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

calcula que ele não aguentaria cair do 100.º andar.

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

De modo pragmático, decide levar o ovo mais valioso que puder.

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

Na loja de recordações do museu descobre dois ovos

perfect replicas that are perfectly worthless.

que são réplicas perfeitas sem qualquer valor.

The plan is to test drop them

O plano é testar deixá-los cair

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

para descobrir qual o andar mais alto em que um ovo sobreviverá à queda,

without breaking.

sem se partir.

Of course, the experiment can only be repeated

Claro, a experiência só pode repetir-se

until both replica eggs are smashed.

enquanto os ovos réplica não se esmagarem.

And throwing souvenirs out the window too many times

E atirar recordações da janela abaixo demasiadas vezes

is probably going to draw the guards' attention.

provavelmente vai chamar a atenção dos guardas.

What's the least number of tries it would take

Qual é o menor número de tentativas necessárias

to guarantee that she find the right floor?

para garantir que ela encontra o piso certo?

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

[Suspende aqui o vídeo se quiseres descobrir sozinho.]

Answer in: 3

[Resposta em: 3]

Answer in: 2

[Resposta em: 2]

Answer in: 1

[Resposta em 1:]

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

Se estás com problemas em começar a encontrar a solução,

it might help to start with a simpler scenario.

talvez ajude começar com um cenário mais simples.

Imagine our thief only had one replica egg.

Imagina que a nossa ladra só tem um ovo réplica.

She'd have a single option:

Só tinha uma opção:

To start by dropping it from the first floor

Começar por atirá-lo do primeiro piso

and go up one by one until it breaks.

e ir subindo um piso até ele se partir.

Then she'd know that the floor below that

Ficaria a saber que o piso abaixo

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

era aquele que ela precisava de fixar para o roubo real.

But this could require as many as 100 tries.

Mas isso podia exigir repetir 100 vezes a operação.

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

Como tem um ovo adicional a ladra tem uma opção melhor.

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

Pode atirar o ovo de pisos diferentes com intervalos maiores

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

a fim de reduzir a amplitude dos pisos, para encontrar o piso crítico.

And once the first breaks,

Depois de o primeiro se partir,

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

pode usar o segundo ovo para explorar esse intervalo, piso por piso.

Large floor intervals don't work great.

Grandes intervalos entre pisos não funcionam muito bem.

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

No pior dos cenários, exigem muitos testes com o segundo ovo.

Smaller intervals work much better.

Intervalos mais pequenos funcionam muito melhor.

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

Por exemplo, se ela começar por atirar o primeiro ovo

de 10 em 10 andares,

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

quando ele se partir, só terá que testar os nove andares abaixo.

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

Isso significa que, quando muito,

só precisará de 19 tentativas para encontrar o piso certo.

But can she do even better?

Mas será possível fazer melhor ainda?

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

Afinal, não é necessário que os intervalos tenham todos o mesmo tamanho.

Let's say there were only ten floors.

Digamos que eram só 10 pisos.

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

Um ladrão podia testar o edifício todo apenas com quatro lançamentos,

by dropping the first egg at floors four,

lançando o primeiro ovo no piso quatro,

seven,

no piso sete e no piso nove.

and nine.

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

Se o ovo se quebrasse no piso quatro,

só precisaria de fazer três lançamentos com o segundo ovo,

to find the exact floor.

para encontrar o piso certo.

If it broke at seven,

Se se quebrasse no piso sete,

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

só precisaria de mais dois lançamentos com o segundo ovo.

And if it broke at floor nine,

E se se quebrasse no piso nove,

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

só precisaria de mais um lançamento com o segundo ovo.

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

Intuitivamente, estamos a tentar dividir o edifício em secções,

where no matter which floor is correct,

nas quais, qualquer que seja o piso correto,

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

será preciso o mesmo número de lançamentos para o encontrar,

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

Queremos que cada intervalo seja um piso menor do que o anterior.

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

Esta equação pode ajudar-nos a descobrir

qual o piso por onde devemos começar,

in the 100 floor building.

num edifício de 100 andares.

There are several ways to solve this equation,

Há várias maneiras de resolver esta equação,

including trial and error.

incluindo a tentativa e o erro.

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

Se considerarmos n=2, a equação ficaria assim.

If we plug in three, we get this.

Se considerarmos n=3, obtemos isto.

So we can find the first n to pass 100

Assim, podemos encontrar o primeiro n, que ultrapasse o total de 100,

by adding more terms until we get to our answer,

acrescentando mais termos, até obtermos a nossa resposta,

which is 14.

que é 14.

And so our thief starts on the 14th floor,

Então, a nossa ladra começa no 14.º piso,

moving up to the 27th,

e vai subindo até ao 27.º,

the 39th,

ao 39.º,

and so on,

etc.,

for a maximum of 14 drops.

num máximo de 14 lançamentos.

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

Como diz o ditado, não podemos fazer um assalto sem partir ovos.