Задача про перебірливу молодицю

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

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

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

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

${\displaystyle {\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.