Приветствую Вас, уважаемые Читатели! Сегодня поговорим об увлекательной задаче с не менее увлекательным названием. Вернее, даже не задаче, а целом классе оптимизационных задач.
В 1960 году его придумал уже известный нам Мартин Гарднер — замечательный популяризатор математики, когда понял, что в рамках теории вероятностей она ранее не встречалась.
Тема диссертации — «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения»Источник: https://avatars.mds.yandex.net/get-zen_doc/1589334/pub_5cc1625ec53c2900afb2b264_5cc1629a2a15bb00b3097cf9/scale_1200
Вы удивитесь, но докторская диссертация Бориса Абрамовича Березовского в бытность работы в Институте проблем управления РАН также была посвящена этой задаче, только лишь в обобщенной формулировке! Итак, посмотрим, каково её условие? Поехали!
Задача о разборчивой невесте (есть еще вариант задача секретаря, если речь идет о найме работников) — это одна из задач теории оптимального выбора. Почему сразу невесты? Источник: https://i.artfile.ru/1600x1200_303971_%5Bwww.ArtFile.ru%5D.jpg
Условие задачи
Пусть в некотором царстве принцесса озаботилась выбором жениха. Отец-царь предоставил дочери на выбор n женихов. Условия следующие:
1. Принцесса может общаться с претендентами не более одного раза.
2. Женихи приходят к невесте в случайном порядке.
3. О каждом из них принцессе известно, лучше или хуже он любого из предыдущих.
4. Невеста может сказать "Да" претенденту, тогда шоу завершается. Если невеста говорит "Нет", вернуться к этому жениху она уже не сможет.
Цель — найти лучшего жениха! Если среди претендентов принцесса никого не выберет, то проиграет и отправится в монастырь (шутка).
Кстати, задача о быстром поиске старшей карты в колоде аналогична рассматриваемой. Источник: https://love-is.org/wp-content/uploads/2020/01/gadanie-na-kartah-na-parnya-4.jpg
Давайте поразмышляем, что делать невесте. Пусть на выбор у нее 1000 женихов. Если она отказала 999 женихам, то последнего уж, как ни крути, ей надо выбирать — не проигрывать же!
А вот что делать, например, с 450-м или 670-м ? Как максимизировать вероятность выбора самого лучшего жениха?
Естественно, что принцесса должна остановиться на том женихе, который, как её известно, лучше остальных.
Решение задачи довольно нетривиальное и занимает с десяток страниц рисунков, рассуждений и формул, вместе с этим оно невероятно изящное и простое!
Источник: https://cf2.ppt-online.org/files2/slide/s/SZnMQ8zVAItj5FBxlyioEH3mbuJKaRr41TOwXh0P9p/slide-4.jpg
Принцесса должна сначала пропустить 1/e женихов, где е — замечательное число Эйлера, равно 2,718281828 ! Т.е. для случая с 1000 женихов её нужно пропустить 368 претендентов, а потом сразу же схватиться за первого, который окажется лучше всех предыдущих!
Да, кстати, вероятность выбора лучше принца в таком случае тоже равна 0,368! Неплохо!
У задачи есть еще вариации: например, принцесса может устраивать и второй и третий и т.д. жених или же ситуация, когда принцесса заранее знает, насколько она будет счастлива, если выберет первого, второго и т.д. жениха, а её стратегия будет состоять в том, чтобы максимизировать своё "счастье" и т.д.
На самом деле задачи оптимального выбора преследуют каждого из нас по жизни. И особенно замечательно, что с ними всегда может помочь царица-математика! Читайте про незаконные числа в математике.
Ставьте лайк и подписывайтесь! ! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.
Мой второй канал — "Экономика не для всех". Поднимаю теоретические вопросы экономики и рынков. Никаких быстрых способов заработка и "выгодных" кредитов. Только чистое знание!
