Кандидати приходять по одному, і про кожного треба вирішити одразу: найняти чи відмовити назавжди. Здається, що найкращого зі ста можна вгадати хіба що з шансом 1%. Насправді просте правило оптимальної зупинки дає 37%: пропустіть перші 37 кандидатів, а потім беріть першого, хто кращий за всіх попередніх. Перевірте це в грі, на симуляції та через п'ять пояснень.
Це класична задача оптимальної зупинки. Її називають задачею про секретаря, задачею про наречену або грою в гугол. Суть одна: варіанти з'являються по черзі, повернутися до відкинутого не можна, і треба вирішити, коли зупинитися.
На одну посаду претендують n кандидатів. Ви знаєте, скільки їх, але вони приходять на співбесіду у випадковому порядку.
Після кожної співбесіди ви знаєте лише одне: як цей кандидат виглядає порівняно з тими, кого ви вже бачили. Про тих, хто ще прийде, ви нічого не знаєте.
Кандидата можна найняти, і тоді пошук закінчено. Або відмовити, і тоді він іде назавжди. Якщо ви дійшли до останнього, доведеться брати його.
Перемога лише одна: найняти найкращого з усіх n. Другий найкращий теж вважається програшем. Яка стратегія дає найбільший шанс і наскільки він великий для 100 кандидатів?
«Найкращий один зі ста, тож шанс близько 1%. Це лотерея»
Насправді правило 37% вгадує найкращого в 37% випадків, і цей шанс майже не залежить від кількості кандидатів. Навіть серед мільйона кандидатів він залишається 36,8%.
Що буде, якщо змінити ці правила, показано в раунді 5.
Уявіть найрозумнішу стратегію, яку тільки можна придумати. З яким шансом вона знайде найкращого серед 100 кандидатів? Зафіксуйте відповідь, перш ніж читати далі.
Тут з'явиться порівняння вашої відповіді з правильною.
Кандидати приходять по одному. Висота стовпчика показує, як кандидат виглядає серед уже побачених, а помаранчевий означає «найкращий досі». Справжні оцінки ви побачите лише в кінці. Зіграйте кілька разів: праворуч видно, як у тих самих чергах зіграло б правило 37%.
Для 20 кандидатів найкраще пропустити 7 і далі брати першого, хто кращий за всіх попередніх. Так найкращого знаходять у 38,4% черг. Навмання вийшло б 5%.
Стратегія з межею r: пропустити перших r кандидатів, а потім найняти першого, хто кращий за всіх попередніх. Комп'ютер грає тисячі черг для кожного r. Лінія показує точну формулу, точки показують симуляцію. Вершина для 100 кандидатів припадає на r = 37.
Перша частина кандидатів потрібна не для вибору, а для того, щоб дізнатися, який рівень вважати добрим. Питання лише в тому, скільки часу на це витратити.
Без жодної інформації неможливо сказати, чи кандидат хороший. Тому перших 37 ви лише оцінюєте й запам'ятовуєте найкращого з них. Він стає планкою. Далі ви берете першого, хто цю планку перевищить.
Пропущені кандидати не марні: саме вони дають вам знання про рівень. Ціна цього знання полягає в тому, що найкращий може опинитися серед них.
Якщо зупинитися зарано, планка слабка, і її перевищить хтось середній. Якщо зарано не зупинитися, найкращий, імовірно, вже був серед пропущених, і далі його ніхто не переможе. Межа 37 урівноважує ці дві небезпеки.
Цифра означає справжнє місце кандидата: 1 найкращий. Блідим позначено пропущених, темним того, кого найняли.
З межею 37 є три результати. У 37,1% черг ви наймаєте найкращого. Ще у 37% черг найкращий був серед пропущених: тоді його ніхто не перевищить, і ви дійдете до кінця. В інших 25,9% планку першим перевищує не найкращий.
Нехай найкращий стоїть на місці i, де i більше за r. Таке трапляється з імовірністю 1/n. Ви наймете саме його, якщо до нього ніхто не перевищив планку, тобто якщо найкращий із перших i−1 кандидатів був серед перших r. Шанс цього r/(i−1). Додаємо по всіх i:
Сума обернених чисел від r до n−1 приблизно дорівнює ln(n/r). Тому шанс залежить лише від частки x = r/n, а не від самого n. Функція −x · ln x досягає максимуму в точці x = 1/e, і там вона теж дорівнює 1/e. Звідси обидва числа: пропускати 37% і вигравати в 37% випадків.
Число 37% стійке до кількості кандидатів, але чутливе до мети. Якщо вас влаштовує будь-хто з трійки найкращих або можна повернутися до відкинутого, пропускати варто зовсім іншу частку.
Вісь n логарифмічна, від 3 до 10 000. Пунктир показує 1/e ≈ 36,8%. Для малих n шанс навіть вищий: для трьох кандидатів 50%.
Нехай наприкінці, якщо ви нікого не найняли, можна зателефонувати найкращому з усіх побачених. Він погоджується з імовірністю q. 100 кандидатів.
Скрізь те саме правило: пропустити перших r, далі брати першого, хто кращий за всіх попередніх, а якщо такого немає, брати останнього. Найкращі межі знайдено комп'ютером. Натисніть «Перевірити», щоб симуляція 10 000 черг повторила результат.
| Мета (100 кандидатів) | Найкраща межа | Результат |
|---|
Останній рядок стосується пошуку з обмеженим часом, коли невідомо, скільки кандидатів прийде. Тоді рахують не кандидатів, а час: перші 37% строку лише дивляться. Шанс залишається не нижчим за 1/e за будь-якої кількості кандидатів.
Після смерті першої дружини в 1611 році астроном Йоганн Кеплер розглядав 11 можливих наречених. Зрештою він одружився з п'ятою, Сюзанною Ройттінгер. Цю історію часто наводять як приклад задачі про секретаря, зокрема в книжці «Алгоритми для життя».
Широкій публіці задачу представив Мартін Гарднер у колонці «Математичні ігри» журналу Scientific American 1960 року. У його версії на папірцях пишуть будь-які числа, хоч до гугола, і треба зупинитися на найбільшому.
Якщо обрати одного зі 100 кандидатів навмання, шанс найкращого 1%. Правило 37% дає 37,1%. Для 1 000 кандидатів навмання вийде 0,1%, а правило все одно дає 36,8%.
Книжка Браяна Крістіана й Тома Гріффітса «Алгоритми для життя» (2016) починається з правила 37% і застосовує його до пошуку квартири та партнера. Якщо ви шукаєте від 18 до 40 років, 37% цього строку закінчуються приблизно у 26 років.
Число 1/e ≈ 36,8% з'являється й у задачі про «Таємного Санту»: якщо багато людей тягнуть імена навмання, шанс, що ніхто не витягне себе, теж прямує до 1/e.
Якщо мета не «найкращий або нічого», а якомога краще середнє місце, існує хитріша стратегія з кількома порогами. Навіть для дуже великої кількості кандидатів вона дає середнє місце близько 3,87. Цей результат опубліковано в 1964 році.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.