Задача в збірці головоломок
Вікіпедія в розділі про яйця посилається на збірку Konhauser, Velleman, Wagon «Which Way Did the Bicycle Go?», яку 1996 року видала Математична асоціація Америки. Задача там на с. 53.
Є будинок на 100 поверхів і два однакові яйця. Десь у ньому є критичний поверх: кинуте з нього або вище яйце розбивається, а нижче лишається цілим. Ціле яйце можна кидати знову. Ви шукаєте найвищий поверх, з якого яйце не б'ється, і маєте знайти його напевно. Скільки кидків знадобиться в найгіршому випадку, якщо діяти найкраще?
Здається, що треба ділити навпіл (50 кидків) або кидати з кожного десятого поверху (19 кидків). Але перший кидок варто робити з 14-го поверху, а кожен наступний стрибок робити на поверх коротшим: 14, 13, 12… Тоді будь-який результат знайдено за 14 кидків, бо 14 + 13 + … + 1 = 105 ≥ 100.
Класична задача зі співбесід програмістів: Вільям Паундстоун подає її як питання зі співбесіди в Google (2012), а в «Cracking the Coding Interview» вона має номер 6.8. Вона перевіряє не знання формул, а вміння думати про найгірший випадок і рахувати ціну кожної помилки.
100 поверхів, пронумерованих від 1 до 100. Десь є межа: з поверхів нижче неї яйце не б'ється, з неї і вище б'ється.
Два однакові яйця. Ціле яйце можна кидати знову, і падіння його не послаблює. Розбите яйце вибуває.
Треба назвати найвищий безпечний поверх. Це може бути 0, якщо яйце б'ється навіть з першого поверху, або 100, якщо воно витримує навіть сотий. Разом 101 варіант.
Рахуємо кожен кидок. Стратегія може залежати від того, що сталося раніше, але має спрацювати за будь-якого критичного поверху.
Яка найменша кількість кидків гарантує, що ви знайдете найвищий безпечний поверх?
«Двійковий пошук: кинути з 50-го, потім з 25-го чи 75-го…»
Двійковий пошук чудовий, коли яєць скільки завгодно. З двома яйцями перше розбите на 50-му поверсі лишає одне яйце на 49 поверхів, і перевіряти їх доведеться по одному: 50 кидків. Кидки з кожного десятого поверху дають 19. А найкраща стратегія дає 14, і менше не можна.
100 поверхів, два яйця, найкраща стратегія. Зафіксуйте, скільки кидків, на вашу думку, гарантує відповідь.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Бінарний пошук тут пастка: щойно перше яйце розіб'ється, другим доведеться йти вгору по одному поверху. Думайте про найгірший випадок, а не про типовий.
Якщо перше яйце розбилося на поверсі x, може знадобитися ще x − 1 кидків. Тож кожен наступний стрибок першого яйця робіть на поверх коротшим за попередній.
Нехай перший кидок з поверху d. Якщо яйце ціле, наступний стрибок на d − 1 поверхів, потім на d − 2 і так далі. Скільки поверхів так можна покрити, і яке d потрібне для 100?
Критичний поверх тут не загаданий заздалегідь. Будинок вирішує, розбилося яйце чи ні, щойно ви його кинули, і завжди обирає відповідь, після якої вам лишиться більше роботи навіть за найкращої подальшої гри. Готову стратегію він знає наперед і підлаштовується під неї. Він не шахраює: кожна відповідь узгоджена з усіма попередніми. Так ми перевіряємо саме найгірший випадок вашої стратегії.
Клацніть поверх, щоб кинути з нього яйце. Зелена смужка: яйце вціліло, червона: розбилося. Світлі поверхи вже безпечні, темні вже б'ють яйце.
Злий будинок показує найгірший випадок. А що, коли критичний поверх просто випадковий? Графік показує, скільки кидків потрібно кожній стратегії для кожного з 101 можливого результату. Таблиця порівнює точне середнє з симуляцією.
«Навпіл»: перше яйце кидаємо з середини ще не перевіреного відрізка (50, 75, 88, 94…), доки воно не розіб'ється, а потім друге йде вгору по одному поверху. «Кожен 10-й»: 10, 20, 30… і потім по одному. Після розбитого яйця друге завжди йде вгору від останнього безпечного поверху.
Ключ не в тому, як швидко звузити пошук, а в тому, скільки коштує кожна помилка. Поки є два яйця, розбите яйце не катастрофа. Коли лишилося одне, кожен поверх доводиться перевіряти окремо.
Якщо критичний поверх випадковий, обидві стратегії в середньому витрачають близько 10–11 кидків. Різниця вилазить у найгіршому випадку: стратегія «кожен 10-й» платить 10 кидків першим яйцем і ще 9 другим, якщо межа десь на 90-х. Найкраща стратегія вирівнює ці витрати, щоб жоден випадок не був надто дорогим.
Якщо перше яйце розбилося на поверсі x, друге мусить пройти поверхи 1, 2, …, x − 1 по одному: інакше, розбивши його, ви не дізнаєтеся відповіді. Тож перший кидок з поверху x може коштувати x кидків. Щоб уміститися в d кидків, перший має бути не вище за d-й поверх.
Після першого вцілілого кидка один кидок уже витрачено, тож на другий стрибок лишається d − 1 кидків, і він може бути завдовжки щонайбільше d − 1 поверхів. Третій щонайбільше d − 2, і так далі. З d = 14 перше яйце летить з поверхів 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
Той самий рахунок працює і як доведення, що менше не можна. Із d кидками перший стрибок щонайбільше d поверхів, другий d − 1, …, останній 1. Разом не більше ніж 1 + 2 + … + d = d(d + 1)/2 поверхів. Для d = 13 це 91: на 100 поверхів не вистачить за жодної стратегії. Для d = 14 це 105, і 5 поверхів навіть у запасі.
f(e, d) = f(e − 1, d − 1) + f(e, d − 1) + 1
f(e, d) = C(d, 1) + C(d, 2) + … + C(d, e)
Перший кидок ділить будинок на три частини: якщо яйце розбилося, нижче лишається f(e − 1, d − 1) поверхів для e − 1 яйця; якщо вціліло, вище лишається f(e, d − 1); і сам поверх кидка. Звідси рекурсія, а її розв'язок дає суму біноміальних коефіцієнтів: рядок трикутника Паскаля, обрізаний після e-го члена. Для одного яйця f = d, для двох f = d(d + 1)/2, трикутні числа. Позначені клітинки: перше d, де покрито 100 поверхів.
Два яйця і d кидків покривають щонайбільше суму перших d натуральних чисел. Потрібно, щоб вона була не меншою за кількість поверхів N.
Для N = 100: 13 замало, 14 досить.
Поверхи першого яйця: стрибки 14, 13, 12, …, останній обрізаємо на 100.
Загалом для e яєць: найменше d, за якого сума біноміальних коефіцієнтів досягає N.
Запас у 5 поверхів означає, що оптимальна стратегія не одна: перший кидок можна робити з будь-якого поверху від 9-го до 14-го, і все одно вкластися в 14. Нижче 9-го не можна, бо тоді над ним лишиться понад 91 поверх, а на них у двох яєць лише 13 кидків.
Яйця тут лише декорація. Насправді задача про пошук, у якому кожна невдача має ціну. У математиці вона росте в біноміальні суми, у логіці стає обміном «помилки на час», а на практиці підказує, як навантажувати сервіс чи ламати зразки в лабораторії.
Математика
Для 100 поверхів: одне яйце дає 100 кидків, два дають 14, три дають 9, чотири дають 8. З п'ятьма вже 7 кидків, а це ⌈log₂ 101⌉, межа двійкового пошуку: 7 відповідей «так чи ні» розрізняють щонайбільше 2⁷ = 128 варіантів, а їх 101. Далі яйця вже не допомагають.
Чотири яйця не дотягують зовсім трохи: f(4, 7) = 7 + 21 + 35 + 35 = 98 поверхів, на два менше, ніж треба. Для великих N з k яйцями потрібно приблизно (k! · N)1/k кидків: для двох яєць і мільйона поверхів це √2 000 000 ≈ 1414, і точна відповідь теж 1414.
Логіка
Число яєць означає, скільки разів вам дозволено помилитися, тобто кинути вище межі. Без права на помилку лишається лише йти по одному поверху. Одна запасна невдача дозволяє стрибати й ділить час приблизно до кореня з N. Кожна наступна бере ще один корінь, а коли невдач стільки, скільки потрібно двійковому пошуку, час падає до log₂ N.
Це загальний обмін: що дешевша невдача, то сміливіше можна стрибати. Двійковий пошук оптимальний, лише коли помилка нічого не коштує.
Практика
Сервіс витримує навантаження до якогось рівня від 0 до 1000 і падає вище. Кожне падіння означає ручний перезапуск. Скільки падінь ви готові стерпіти?
Шукаємо найвищий рівень навантаження з 1000, який сервіс витримує. Якщо можна впасти лише двічі, потрібно 45 тестів, бо 44 · 45/2 = 990 < 1000 ≤ 1035 = 45 · 46/2. Перший тест на рівні 45, далі стрибки 44, 43, … Якщо падати можна скільки завгодно (тестове середовище само піднімається), досить 10 тестів двійковим пошуком.
Той самий двійковий пошук робить git bisect: серед 1000 комітів він знаходить той, що зламав програму, приблизно за 10 кроків, бо «поганий» коміт нічого не руйнує. А в матеріалознавстві й краш-тестах зразків мало і кожен коштує грошей: зразок, що зламався, і є розбите яйце, тож випробування планують сходами, як у цій задачі.
Схожу ідею з двійковими кодами розібрано в задачі про отруєне вино і щурів.
Вікіпедія в розділі про яйця посилається на збірку Konhauser, Velleman, Wagon «Which Way Did the Bicycle Go?», яку 1996 року видала Математична асоціація Америки. Задача там на с. 53.
Мойше Снідович присвятив задачі статтю «The Joy of Egg-Dropping in Braunschweig and Hong Kong» у журналі INFORMS Transactions on Education (том 4). Це четверта стаття його серії «OR/MS Games» про навчальні ігри.
У статті Вікіпедії про динамічне програмування будинок має 36 поверхів. Це трикутне число 8 · 9/2, тож двом яйцям вистачає рівно 8 кидків, і жодного поверху в запасі.
На LeetCode, де програмісти тренуються до співбесід, загальна версія з k яйцями і n поверхами має номер 887 і позначку Hard.
З двома яйцями на 1 000 000 поверхів потрібно 1414 кидків, бо 1414 · 1415/2 = 1 000 405. Із 20 яйцями досить 20 кидків, як у двійковому пошуку.
У червні 2013 року Ласло Бок, віцепрезидент Google з персоналу, сказав New York Times, що головоломки на співбесідах — цілковита марнота часу: «вони здебільшого потрібні, щоб інтерв'юер почувався розумним». Щоправда, приклади він навів інші: задачі на оцінку на кшталт «скільки м'ячів для гольфу влізе в літак».
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.