Задача про перебірливу молодицю
У деякому Королівстві прийшов час принцесі вибирати собі нареченого. У призначений день з’явилися 1000 принців. Їх побудували в чергу у випадковому порядку і стали по одному запрошувати до принцеси. Про будь-яких двох претендентів принцеса, познайомившись з ними, може сказати, який з них краще. Познайомившись з претендентом, принцеса може або прийняти пропозицію (і тоді вибір зроблений назавжди), або відкинути його (і тоді претендент втрачений: принци горді і не повертаються). Якої стратегії повинна дотримуватися принцеса, щоб з найбільшою ймовірністю вибрати кращого?
У 1960 році її придумав Мартін Гарднер, автор величезної кількості книг із захоплюючими завданнями і головоломками, пов’язаними з математикою. У 1963 році професор Євген Борисович Динкін запропонував рішення цієї задачі для окремого випадку саме в 1000 принців. Загальне рішення було знайдено студентом цього професора Сабіром Гусейн-Заде в 1966 році, який згодом і сам став доктором математичних наук. А дисертація Бориса Березовського на здобуття наукового ступеня доктора наук, захищена в 1983 році, є узагальненням задачі про розбірливу чи навіть перебірливу наречену.
Сформулюємо задачу таким чином:
Молодиця шукає собі нареченого (існує єдине вакантне місце).
Є відоме число n претендентів.
Про кожного претендента можна сказати, що він кращий чи гірший від іншого.
Молодиця спілкується з претендентами у випадковому порядку.
В результаті спілкування з кожним нареченим молодиця повинна йому відмовити або прийняти його пропозицію.
Рішення приймається тільки виходячи з оцінки претендента в порівнянні з попередніми.
Знехтувані женихи не повертаються.
Мета: вибрати найкращого претендента.
Припустимо, що принцеса пропустила 999 претендентів і зараз зустрічається з останнім. Тоді у неї немає ніякої альтернативи, все абсолютно ясно. Якщо останній і є найкращий, то принцеса виграла, домоглася свого, якщо він не найкращий, то принцеса програла і йде в монастир. У будь-якому випадку відкидати останнього претендента безглуздо, це до перемоги точно не приведе. Тепер припустимо, що принцеса знає, як поводитися на 601-му кроці. Спробуємо зрозуміти, що робити при зустрічі з 600-м, тобто за крок до цього. Ясно, що якщо 600-й претендент не краще за всіх попередніх, то і думати нічого, йому потрібно відмовляти. Взагалі в нашому завданні принцеса буде зупинятися тільки на тих, хто краще за всіх попередніх, інакше вона точно програє, адже її влаштовує тільки найкращий. Якщо ж він дійсно краще за всіх попередніх, то у принцеси є вибір. Наприклад, коли приходить перший, то, природно, він краще всіх попередніх, так як і попередніх-то ніяких не було, але зупинятися на ньому якось дуже дивно, шансів перемогти мало, з таким же успіхом можна і на десятому зупинитися, краще ще почекати хоч трохи, може, хто-небудь краще з’явиться. Отже, нехай 600-й краще за всіх попередніх, і принцесі потрібно оцінити (вона, напевно, і не може, але ж для цього математики і існують), що краще: вибрати цього самого 600-го або відмовити йому, перейти до наступного, а там, як ми пам’ятаємо, вже все відомо, зрозуміло, як потрібно чинити, і шанси на отримання кращого нареченого ми порахувати зможемо.
𝑛 – кількість женихів
𝑡 – номер кроку
𝑔(𝑡) – ймовірність перемоги в момент 𝑡 за умови, що 𝑡 – ий наречений краще за всіх попередніх
ℎ(𝑡) – ймовірність перемоги за умови, що наречена пропустить 𝑡 перших кандидатів і далі (починаючи з кроку 𝑡 + 1) буде діяти оптимально
Зауваження. ℎ(𝑡) монотонно не зростає
Отже, оголосимо для початку, що 1000 ми позначимо за n, тобто вирішимо завдання для довільної кількості претендентів. Далі, нехай принцеса знаходиться на кроці t (це номер кроку, тобто натуральне число). Перше, що їй потрібно знати — це ймовірність перемоги в разі вибору нареченого в момент t, за умови, що він краще всіх попередніх, тобто ймовірність того, що він не тільки краще всіх попередніх, а взагалі краще за всіх. Позначимо цю ймовірність за g(t) . Крім того, необхідно знати ще одну величину — це ймовірність того, що вона врешті-решт отримає найкращого нареченого, за умови, що вона пропустить перших t претендентів і далі буде користуватися оптимальною стратегією (тут мається на увазі наше припущення про те, що принцеса знає, як себе оптимально вести починаючи з кроку t+1). Позначимо цю ймовірність за h(t). Знаючи ці дві величини для будь-якого t, ми можемо легко зрозуміти оптимальну стратегію поведінки для принцеси: якщо на кроці t претендент не краще всіх попередніх, то, ясна річ, його потрібно відкинути, якщо ж він дійсно кращий серед перших t претендентів, то потрібно порівняти g(t) і h(t) , якщо більше g(t) , то потрібно зупинитися на претенденті t, якщо більше ht , то потрібно його відкинути і перейти до наступного, така стратегія випливає прямо з визначення цих ймовірностей. Що ж робити в разі рівності? Зрозуміло, що це неважливо, так як ймовірність перемоги в кожному з випадків однакова, тому давайте домовимося, що в разі рівності g(t) і h(t) принцеса буде, наприклад, весь час зупинятися на поточному претенденті.
Натуральний логарифм — це логарифм з основою e, де e — ірраціональна константа, що дорівнює приблизно 2,718281828.
Ймовірність успіху принцеси, яку ми шукали з самого початку, дорівнює 0,368. Таким чином, відповідь на поставлене спочатку завдання виглядає так: принцеса повинна спочатку пропустити першу e частина женихів (в разі t = 1000 це приблизно 368 чоловік), тільки запам’ятовуючи їх для майбутнього порівняння, а далі вона повинна брати в чоловіки першого ж, який володіє тією властивістю, що він краще за всіх своїх попередників. При цьому ймовірність отримати в кінці кінців найкращого нареченого з усіх t претендентів дорівнює приблизно 0,368.