Задача про перебірливу наречену, або проблема зупинки вибору може бути сформульована таким чином:
- Наречена підбирає собі судженого (існує єдине вакантне місце).
- Є відоме число n претендентів.
- Про кожного претендента можна сказати, що він кращий чи гірший від іншого.
- Наречена спілкується з претендентами у випадковому порядку.
- В результаті спілкування з кожним нареченим наречена повинна йому відмовити або прийняти його пропозицію.
- Рішення ухвалюється тільки виходячи з оцінки претендента в порівнянні з попередніми.
- Знехтувані женихи не повертаються.
- Мета: вибрати найкращого претендента.
Цьому завданню було приділено багато уваги саме тому, що оптимальна стратегія має цікаву особливість. А саме: якщо число кандидатів досить велике (порядку сотні), оптимальна стратегія буде полягати у відхиленні всіх перших n/e (де e- основа натурального логарифма ) претендентів і потім вибрати першого, хто буде кращим від всіх попередніх або дійти до кінця. При збільшенні n, ймовірність вибору найкращого претендента прямує до 1/e, тобто приблизно до 37 %.
Виведення оптимальної стратегії
Оптимальним підходом для цієї задачі є (правило зупину). Згідно з ним, наречена відмовляє першим r претендентам (нехай претендент M буде найкращим серед цих r претендентів), і тоді вибирає першого з наступних претендентів, який є кращим ніж претендент M. Для довільного r розглянемо ймовірність обрання найкращого претендента.
Нехай подія полягає в обранні найкращого претендента, а подія
полягає в тому, що найкращим є претендент
Отже, повна ймовірність становить
Ми можемо стартувати з бо якщо найкращий претендент є серед перших
то наречена відмовила йому. За умови події
подія
відбудеться лише якщо найкращий претендент з перших
перебуває серед перших
яким наречена відмовила. Тепер, для будь-якого довільного впорядкування
різних чисел, ймовірність того, що найбільше з них є серед перших
становить
З цього випливає, що
Див. також
Примітки
- С. М. Гусейн-Заде. Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003
- С. М. Гусейн-Заде, Разборчивая невеста. с. 18, М.: МЦНМО, 2003
Посилання
- С. М. Гусейн-Заде. Разборчивая невеста. Библиотека «Математическое просвещение», том 25, МЦНМО, 2003
- С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. , МГУ, 30.11.2002.
![]() | Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет