Математичні парадокси

Задача про секретаряПравило 37%: задача про секретаря 100 кандидатів. Одне рішення. Який шанс найняти найкращого?Шанс найняти найкращого 37%.

Кандидати приходять по одному, і про кожного треба вирішити одразу: найняти чи відмовити назавжди. З яким шансом можна найняти найкращого зі ста? Зафіксуйте свою відповідь, а потім перевірте її в грі, на симуляції та через п'ять пояснень.

Кандидати приходять по одному, і про кожного треба вирішити одразу: найняти чи відмовити назавжди. Здається, що найкращого зі ста можна вгадати хіба що з шансом 1%. Насправді просте правило оптимальної зупинки дає 37%: пропустіть перші 37 кандидатів, а потім беріть першого, хто кращий за всіх попередніх. Перевірте це в грі, на симуляції та через п'ять пояснень.

Вгадати відповідь
1%навмання
37%за правилом 37%
Умова задачі

Уявіть: ви шукаєте секретаря

Це класична задача оптимальної зупинки. Її називають задачею про секретаря, задачею про наречену або грою в гугол. Суть одна: варіанти з'являються по черзі, повернутися до відкинутого не можна, і треба вирішити, коли зупинитися.

  1. 1

    Кандидати

    На одну посаду претендують n кандидатів. Ви знаєте, скільки їх, але вони приходять на співбесіду у випадковому порядку.

  2. 2

    Співбесіда

    Після кожної співбесіди ви знаєте лише одне: як цей кандидат виглядає порівняно з тими, кого ви вже бачили. Про тих, хто ще прийде, ви нічого не знаєте.

  3. 3

    Рішення одразу

    Кандидата можна найняти, і тоді пошук закінчено. Або відмовити, і тоді він іде назавжди. Якщо ви дійшли до останнього, доведеться брати його.

  4. 4

    Мета

    Перемога лише одна: найняти найкращого з усіх n. Найняти другого за рівнем теж означає програти. Яка стратегія дає найбільший шанс і наскільки він великий для 100 кандидатів?

Інтуїція підказує

«Найкращий один зі ста, тож шанс близько 1%. Це лотерея»

Насправді правило 37% вгадує найкращого в 37% випадків, і цей шанс майже не залежить від кількості кандидатів. Навіть серед мільйона кандидатів він залишається 36,8%.

Припущення моделі

  • Кількість кандидатів n відома заздалегідь.
  • Порядок приходу випадковий.
  • Будь-яких двох кандидатів можна порівняти, нічиїх немає.
  • Відкинутого кандидата не повернути.
  • Перемога лише тоді, коли найнято найкращого.

Що буде, якщо змінити ці правила, показано в раунді 5.

Раунд 1 · Вгадайте

Який шанс найняти найкращого зі 100?

Уявіть найрозумнішу стратегію, яку тільки можна придумати. З яким шансом вона знайде найкращого серед 100 кандидатів? Зафіксуйте відповідь, перш ніж читати далі.

Тут з'явиться порівняння вашої відповіді з правильною.

Підказки

Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.

Далі розв'язок

Далі пояснення, і в ньому спойлери

Наступні раунди показують шанс найняти найкращого і як: гра з 20 кандидатами, симуляція і пояснення. Спершу відповісти в раунді 1 чи йти далі?

Ви обрали завжди показувати всі раунди.

Раунд 2 · Наймайте

20 кандидатів, одне рішення

Кандидати приходять по одному. Висота стовпчика показує, як кандидат виглядає серед уже побачених. Рожевий означає, що кандидат кращий за всіх попередніх. Справжні оцінки ви побачите лише в кінці. Зіграйте кілька разів: праворуч видно, як у тих самих чергах зіграло б правило 37%.

Кандидат1 / 20
Серед побачених1

Ваш рахунок

Ви0 / 0
Правило 37%0 / 0

Раунд 3 · Симуляція

Скільки кандидатів пропустити

Стратегія з межею r: пропустити перших r кандидатів, а потім найняти першого, хто кращий за всіх попередніх. Комп'ютер грає тисячі черг для кожного r. Лінія показує точну формулу, точки показують симуляцію. Вершина для 100 кандидатів припадає на r = 37.

точна формула симуляція
–
–
Раунд 4 · П'ять пояснень

Чому саме 37%

Перша частина кандидатів потрібна не для вибору, а для того, щоб дізнатися, який рівень вважати добрим. Питання лише в тому, скільки часу на це витратити.

На пальцяхкартинки, аналогії, маленькі числа

Шар «На пальцях» приховано на всіх задачах.

Спочатку дивимося, потім обираємо

Перші 37 кандидатів задають планку

Без жодної інформації неможливо сказати, чи кандидат хороший. Тому перших 37 ви лише оцінюєте й запам'ятовуєте найкращого з них. Він стає планкою. Далі ви берете першого, хто цю планку перевищить.

Пропущені кандидати не марні: саме вони показують вам рівень. Ціна цього знання полягає в тому, що найкращий може опинитися серед них.

Зарано і запізно

Обидві помилки коштують дорого

Пропустити лише 5 зі 100планка низька, наймаєте першого-ліпшого
Пропустити 80 зі 100у 80% черг найкращий уже пропущений

Якщо надто рано припинити придивлятися, планка слабка, і її перевищить хтось середній. Якщо придивлятися задовго, найкращий, імовірно, вже був серед пропущених, і далі планку ніхто не перевищить. Межа 37 урівноважує ці дві небезпеки.

Чому рівновага саме на 37, а не на 30 чи 45, простими словами не видно. Це показує вершина графіка в раунді 3, а точний розрахунок є в картці з формулами нижче.

Маленький приклад

Три кандидати, шість порядків

Цифра означає справжнє місце кандидата: 1 найкращий. Блідим позначено пропущених, темним того, кого найняли.

Куди зникають інші 63%

Навіть найкраща стратегія частіше програє

З межею 37 є три результати. У 37,1% черг ви наймаєте найкращого. Ще у 37% черг найкращий був серед пропущених: тоді його ніхто не перевищить, і ви дійдете до кінця. В інших 25,9% планку першим перевищує не найкращий.

Строготаблиці, графіки, формули

Шар «Строго» приховано на всіх задачах.

Для тих, хто любить формули

Точна формула і звідки береться 1/e

Нехай найкращий стоїть на місці i, де i більше за r. Таке трапляється з імовірністю 1/n. Ви наймете саме його, якщо до нього ніхто не перевищив планку, тобто якщо найкращий із перших i−1 кандидатів був серед перших r. Шанс цього r/(i−1). Підсумуйте за всіма i:

Точний шанс найняти найкращого, якщо пропустити перших r із n кандидатів.

P(r)=rn·(1r+1r+1+…+1n−1)

Через частку пропущених x = r/n сума стає простою функцією від x.

x=rn:P≈x·ln1x=−x·lnx

Найкраща частка там, де похідна дорівнює нулю. У цій точці шанс теж 1/e.

(−x·lnx)′=−lnx−1=0 x=1e≈0,368,P=1e≈36,8%

Для 100 кандидатів точна формула.

n=100:r=37,P(37)=37,1%

Сума обернених чисел від r до n−1 приблизно дорівнює ln(n/r). Тому шанс залежить лише від частки x = r/n, а не від самого n. Функція −x · ln x досягає максимуму в точці x = 1/e, і там вона теж дорівнює 1/e. Звідси обидва числа: пропускати 37% і вигравати в 37% випадків.

Раунд 5 · Ускладнюємо

Інші n, інші цілі, друга спроба

Число 37% стійке до кількості кандидатів, але чутливе до мети. Якщо вас влаштовує будь-хто з трійки найкращих або можна повернутися до відкинутого, пропускати варто зовсім іншу частку.

Найкраща межа для різних n

Пропустити перших
Шанс найкращого
n/e ≈

Частка та шанс прямують до 1/e

найкращий шанс частка пропущених r/n

Вісь n , від 3 до 10 000. Пунктир показує 1/e ≈ 36,8%. Для малих n шанс навіть вищий: для трьох кандидатів 50%.

Можна повернутися до відкинутого

Нехай наприкінці, якщо ви нікого не найняли, можна зателефонувати найкращому з усіх побачених. Він погоджується з імовірністю q. Кандидатів 100.

з поверненням класична задача
Пропустити перших
Шанс найкращого

Інші цілі та невідома кількість кандидатів

Скрізь те саме правило: пропустити перших r, далі брати першого, хто кращий за всіх попередніх, а якщо такого немає, брати останнього. Найкращі межі знайшов комп'ютер. Натисніть «Перевірити», щоб симуляція 10 000 черг повторила результат.

Мета (100 кандидатів)Найкраща межаРезультат

Останній рядок стосується пошуку з обмеженим часом, коли невідомо, скільки кандидатів прийде. Тоді рахують не кандидатів, а час: перші 37% строку лише дивляться. Шанс залишається не нижчим за 1/e за будь-якої кількості кандидатів.

Тут кандидата, якого відпустили, не повернути. Коли ж можна пробувати знову й знову, як із двома ігровими автоматами, виходить інша задача про той самий вибір між розвідкою і користю: багаторукий бандит.

Бонус · Цікаві факти

Що розповісти друзям

11

Кеплер шукає дружину

Після смерті першої дружини в 1611 році астроном Йоганн Кеплер розглядав 11 можливих наречених. Зрештою він одружився з п'ятою, Сюзанною Ройттінгер. Цю історію часто наводять як приклад задачі про секретаря, зокрема в книжці «Алгоритми для життя».

1960

Гра в гугол

Широкій публіці задачу представив Мартін Гарднер у колонці «Математичні ігри» журналу Scientific American 1960 року. У його версії на папірцях пишуть будь-які числа, хоч і такі великі, як гугол, і треба зупинитися на найбільшому.

1% → 37%

У 37 разів краще за вгадування

Якщо обрати одного зі 100 кандидатів навмання, шанс найкращого 1%. Правило 37% дає 37,1%. Для 1 000 кандидатів навмання вийде 0,1%, а правило все одно дає 36,8%.

2016

Квартири й побачення

Книжка Браяна Крістіана й Тома Гріффітса «Алгоритми для життя» (2016) починається з правила 37% і застосовує його до пошуку квартири та партнера. Якщо ви шукаєте від 18 до 40 років, перші 37% цього строку минають приблизно у 26 років.

e ≈ 2,718

Те саме число в іншій задачі

Число 1/e ≈ 36,8% з'являється й у задачі про «Таємного Санту»: якщо багато людей тягнуть імена навмання, шанс, що ніхто не витягне власне ім'я, теж прямує до 1/e.

3,87

Середнє місце нижче 4

Якщо мета не «найкращий або нічого», а якомога краще середнє місце, існує хитріша стратегія з кількома порогами. Навіть для дуже великої кількості кандидатів вона дає середнє місце близько 3,87. Цей результат опубліковано в 1964 році.

Життя за алгоритмами. Ефективний спосіб знайти квартиру, кохання і парковку

Браян Крістіан, Том Ґріффітс

Наш Формат, 2020 · розділ 1

Математика кохання: стереотипи, докази і пошук остаточного рішення

Ганна Фрай

Vivat, 2017 · розділ 7

Усі книжки →
Обговорення

Що ви думаєте?

Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.

Рівень «Шкільна математика» відповідає задачі?

Дякуємо! Це допоможе точніше ставити рівні.

Розсилка

Нові задачі, пояснення й обговорення

Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.

Форма підписки з'явиться тут найближчим часом.