Pouvez-vous résoudre l'énigme du lancer d’œuf ? - Yossi Elran

Pour le cours en entier : https://ed.ted.com/lessons/can-you-solve-the-egg-drop-riddle-yossi-elran

Leçon créé par Yossi Elran, réalisée par Outis.

La ville vient d'ouvrir un musée des
œufs de Fabergé, unique en son genre,

avec un seul œuf exposé à chaque étage
d'un immeuble de 100 étages.

Une célèbre voleuse de bijoux
veut déjà mettre la main dessus.

Mais comme la sécurité est renforcée
et que les œufs sont trop gros,

elle ne peut en voler qu'un seul.

En le laissant tomber d'une fenêtre
dans un camion

tout en redescendant
avant que la police n'arrive.

Tous les œufs font le même poids
et ont la même forme,

mais plus on monte, plus l'œuf
est rare et précieux.

En général, les voleurs auraient tendance
à voler le plus rare tout en haut,

mais la voleuse pense que celui-ci ne
survivrait pas à une chute de 100 étages.

De façon pragmatique, elle se décide sur
l’œuf le plus cher qu'elle puisse prendre.

Dans la boutique du musée, elle trouve
deux parfaites répliques

d'œufs souvenirs,
qui n'ont pas de valeur.

Le but est de les tester en les lâchant,

afin de trouver l'étage le plus haut
auquel un œuf pourrait survivre

à la chute sans se casser.

Bien entendu, cette expérience
ne peut être répétée

que jusqu'à ce que les faux œufs
se cassent.

Mais les jeter par la fenêtre trop souvent

risque d'attirer l'attention des gardes.

Quel serait le plus petit
nombre de lancers

pour être sûr qu'elle trouve
le parfait étage ?

Faites pause ici, si vous désirez
trouver la réponse par vous-même !

La réponse dans : 3

La réponse dans : 2

La réponse dans : 1

Si vous avez du mal
à trouver une solution,

il serait utile de vous aider
via un simple scénario.

Imaginez que notre voleuse n'ait
qu'une seule réplique de l’œuf.

Elle n'aurait alors qu'une seule option :

commencer à le lâcher
depuis le premier étage

et de les remonter ainsi de suite
jusqu'à ce qu'il casse.

Alors, elle saurait que l'étage du dessous

est celui à viser pour son vol.

Mais elle risque d'avoir besoin
des 100 essais.

Le fait d'avoir un faux œuf en plus
lui donne une option supplémentaire.

Elle peut lâcher un œuf de différents
étages à des intervalles plus grands

afin de réduire l'intervalle
où se trouve le bon étage.

Dès qu'elle a trouvé la limite,

elle peut utilise le second œuf
pour trouver l'intervalle étage par étage.

De grands intervalles d'étages
ne fonctionnent pas très bien.

Dans le pire des cas, il faut faire
plusieurs tests avec le second œuf.

Les plus petits intervalles
fonctionnent mieux.

Par exemple, si elle lâche
le premier œuf tous les dix étages,

et qu'il casse, elle devra essayer
les neuf étages restants.

Ce qui veut dire, qu'elle devra essayer
19 étages afin de trouve le bon.

Mais peut-elle faire mieux ?

Il n'y a pas de raison à ce que
les intervalles soient de la même taille.

Partons du principe
qu'il n'y ait que dix étages.

Le voleur pourrait tester tout l'immeuble
avec seulement quatre lancers,

en lâchant le premier oeuf
du quatrième étage,

du septième,

et du neuvième.

S'il casse au quatrième étage, il faudra
alors jusqu’à trois autres lancers

afin de trouver le bon étage.

S'il casse au septième,

il faudra jusqu'à deux autres lancers,
avec l’œuf restant.

Et s'il casse du neuvième étage,

il faudra alors qu'un seul lancer
avec l’œuf restant.

Ce qu'on essaie de faire ici,
c'est de diviser l'immeuble en sections

où nous voulons trouver le même nombre
de lancers,

peu importe l'étage.

Nous voulons que chaque intervalle soit
plus petit d'un étage que le précédent.

Cette équation peut nous aider à trouver
l'étage par lequel commencer,

pour un immeuble de 100 étages.

Il existe plusieurs façons pour résoudre
cette équation,

en procédant par essais successifs.

Si n vaut deux, l'équation donne ceci.

Si n vaut trois, nous obtenons ça.

On peut donc trouver le premier n
dépassant 100

en ajoutant des chiffres afin de trouver
la réponse,

qui est 14.

Alors notre voleuse commence
au 14ème étage,

puis le 27ème,

le 39ème,

et ainsi de suite.

Pour un maximum de 14 lancers.

Comme on dit, on ne fait pas
de bon cambriolage sans casser d’œufs.