Задача про перебірливу наречену

Задача про перебірливу наречену, або проблема зупинки вибору може бути сформульована таким чином:

1. Наречена підбирає собі судженого (існує єдине вакантне місце).
2. Є відоме число n претендентів.
3. Про кожного претендента можна сказати, що він кращий чи гірший від іншого.
4. Наречена спілкується з претендентами у випадковому порядку.
5. В результаті спілкування з кожним нареченим наречена повинна йому відмовити або прийняти його пропозицію.
6. Рішення ухвалюється тільки виходячи з оцінки претендента в порівнянні з попередніми.
7. Знехтувані женихи не повертаються.
8. Мета: вибрати найкращого претендента.

Цьому завданню було приділено багато уваги саме тому, що оптимальна стратегія має цікаву особливість. А саме: якщо число кандидатів досить велике (порядку сотні), оптимальна стратегія буде полягати у відхиленні всіх перших n/e (де e- основа натурального логарифма ) претендентів і потім вибрати першого, хто буде кращим від всіх попередніх або дійти до кінця. При збільшенні n, ймовірність вибору найкращого претендента прямує до 1/e, тобто приблизно до 37 %.

Виведення оптимальної стратегії

Оптимальним підходом для цієї задачі є правило зупину. Згідно з ним, наречена відмовляє першим r претендентам (нехай претендент M буде найкращим серед цих r претендентів), і тоді вибирає першого з наступних претендентів, який є кращим ніж претендент M. Для довільного r розглянемо ймовірність обрання найкращого претендента.

Нехай подія $B_{r}$ полягає в обранні найкращого претендента, а подія $A_{k}$ полягає в тому, що найкращим є претендент $k.$ Отже, повна ймовірність становить

${\mbox{P}}(B_{r})=\sum _{k=r+1}^{n}{\mbox{P}}(B_{r}|A_{k}){\mbox{P}}(A_{k}).$

Ми можемо стартувати з $r+1,$ бо якщо найкращий претендент є серед перших $r,$ то наречена відмовила йому. За умови події $A_{k},$ подія $B_{k}$ відбудеться лише якщо найкращий претендент з перших $k-1$ перебуває серед перших $r,$ яким наречена відмовила. Тепер, для будь-якого довільного впорядкування $k-1$ різних чисел, ймовірність того, що найбільше з них є серед перших $r$ становить $r/(k-1).$ З цього випливає, що

${\mbox{P}}(B_{r})=\sum _{k=r+1}^{n}{\frac {r}{k-1}}\cdot {\frac {1}{n}}={\frac {r}{n}}\sum _{j=r}^{n-1}{\frac {1}{j}}.$

Див. також

• Наступний (Передача)

Посилання

• С. М. Гусейн-Заде. Разборчивая невеста. Библиотека «Математическое просвещение», том 25, МЦНМО, 2003 ISBN 5-94057-076-3
• С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.