Два стеклянных шарика и многоэтажка

Раз уж я вскольз упомянул круглые люки, пора вспомнить ещё один классический брейнтизер. Лет двадцать назад мне рассказали классическую алгоритмическую задачку (классическую в исходном смысле -- что решение знают все кроме тебя) про два шарика и 100 этажный дом. Я тогда, кажется, первый раз понял что и тут тоже есть математика, до этого скорее как сноб-дурачок считал что в _сомпутер саенс _её не бывает

Есть два стеклянных шарика, надо узнать начиная с какого этажа они разбиваются за минимум бросков (у нас идеальный мир, шарики одинаковые, разбиваясь с этажа X шарик разобьётся с любого этажа больше X и не разобьётся с любого этажа меньше X, кидать можно сколько угодно раз)

Задачка рассказывали мне за костром под соусом высмеивания программистов что мол на собеседованиях в корпорации считается что человек прошёл дальше если смог предложить решение которое даёт худший вариант за 33 броска, хотя как бы любой нормальный человек предожит 19, ахаха ну тупыыые. Я ещё, помню, порадовался, что я не с физфака, потому что так банально самоутверждаться за счёт других мне показалось низко. Ну вот это вот, классическое чувство что физтех произошёл от мгу как человек от обезьяны 🦨

На самом деле понятно почему 33 это граница при которой идут дальше: заряженный на прохождение собеса программист не думая предложит бинарный поик и будет посрамнён. В бинарном поиске у нас бесконечное количетство шариков и там бы было log₂(100) ≈ 7, но у нас не бесконечное количество шариков и в этом случае worst case 50, и надо понять способен ли кандидат вообще думать. Просто думать, да, мы не хотим тратить силы чтобы проверять способен ли кандидат думать хорошо

Но задачка интересна с точки зрения что если её подсунуть в нужном возрасте, она хорошо показывает интересна ли математика или только гуд энаф эвристика. Потому что одно дело придумать решение за 19 и успокоиться, и совсем другое найти оптимальное решение за 14 (прыжки сокращающимися интервалами, находится через арифметическую прогрессию)

А классический анекдот про два шарика, инопланетян русского, немца и француза я кажется ещё только через пять лет узнал, а так бы может эта заметка была бы о другом

02D10