Задача про перебірливу наречену
Задача про перебірливу наречену, або проблема зупинки вибору може бути сформульована таким чином:[1]
- Наречена підбирає собі судженого (існує єдине вакантне місце).
- Є відоме число n претендентів.
- Про кожного претендента можна сказати, що він кращий чи гірший від іншого.
- Наречена спілкується з претендентами у випадковому порядку.
- В результаті спілкування з кожним нареченим наречена повинна йому відмовити або прийняти його пропозицію.
- Рішення ухвалюється тільки виходячи з оцінки претендента в порівнянні з попередніми.
- Знехтувані женихи не повертаються.
- Мета: вибрати найкращого претендента.
Цьому завданню було приділено багато уваги саме тому, що оптимальна стратегія має цікаву особливість. А саме: якщо число кандидатів досить велике (порядку сотні), оптимальна стратегія буде полягати у відхиленні всіх перших n/e (де e- основа натурального логарифма ) претендентів і потім вибрати першого, хто буде кращим від всіх попередніх або дійти до кінця.[2] При збільшенні n, ймовірність вибору найкращого претендента прямує до 1/e, тобто приблизно до 37 %.
Оптимальним підходом для цієї задачі є правило зупину. Згідно з ним, наречена відмовляє першим r претендентам (нехай претендент M буде найкращим серед цих r претендентів), і тоді вибирає першого з наступних претендентів, який є кращим ніж претендент M. Для довільного r розглянемо ймовірність обрання найкращого претендента.
Нехай подія полягає в обранні найкращого претендента, а подія полягає в тому, що найкращим є претендент Отже, повна ймовірність становить
Ми можемо стартувати з бо якщо найкращий претендент є серед перших то наречена відмовила йому. За умови події подія відбудеться лише якщо найкращий претендент з перших перебуває серед перших яким наречена відмовила. Тепер, для будь-якого довільного впорядкування різних чисел, ймовірність того, що найбільше з них є серед перших становить З цього випливає, що
- С. М. Гусейн-Заде. Разборчивая невеста. Библиотека «Математическое просвещение», том 25, МЦНМО, 2003 ISBN 5-94057-076-3
- С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |