Как выбрать лучшее или проблема остановки выбора. Математика на QWERTY
Всем привет! Сегодня мы с вами будем говорить про задачу выбора разборчивый невестами. С вами Георги Вольфсон, а значит, это реальная математика на канале QWERTY. Надеюсь, что вы на нас уже давно подписаны, но если вдруг нет, то это можно сделать вот здесь.
Что это за задача? На самом деле, задачу поставил чуть больше шестидесяти лет назад известный популяризатор математики Мартин Гарднер. Вот представьте себе, что есть невеста. Она хочет выйти замуж, и у нее есть сколько-то кандидатов. В оригинальной задаче было 1000, которые по очереди приезжают к ней свататься.
Предположим, что невеста по некоторым критериям оценила этих потенциальных тысяч учеников. Ну скажем, от 1 до 1000, она может проранжировать, за кого выйти замуж. Но при этом, когда приезжает конкретный, она не знает, лучший он в данный момент среди всех или нет. Она может только сравнить его с предыдущими.
Например, самый простой способ — это узнать, сколько у него денег, но это было бы не интересно. Поэтому давайте будем считать, что принцесса абсолютно точно умеет измерять IQ этих самых женихов.
По условию задачи, у всех айкью равен. И вот задача выбрать самого-самого умного жениха. То есть, если даже она выберет второго, это будет для нее поражение. Как ей поступить, если учесть, что когда к ней приезжает свататься один жених, она ему либо говорит: "Да, давай, я выйду за тебя замуж", либо она ему отказывает, и тогда он обижается и больше уже к ней не приезжает.
То есть, если она самому умному отказала, то все — больше она уже вернуть его не сможет. Он слишком горд. Понятно, что здесь невозможно со стопроцентной вероятностью ткнуть в самого-самого умного.
Например, вот первый жених приехал, его IQ принцесса померила, она знает какой у него IQ, но она же не знает, лучший это из всех или нет. И допустим, она ему отказывает, а он оказался самым лучшим — все, она проиграла. Если же наоборот, она говорит: "Давай, мы с тобой поженимся", — ну, сами понимаете, шанс, что он самый лучший, в общем, не очень высок, потому что, возможно, следующий будет более высоким.
Так точно выиграть нельзя, но с другой стороны, хочется придумать такую стратегию, которая максимизирует вероятность выигрыша. То есть вот как поступить, чтобы с наибольшей вероятностью заполучить себе самого-самого умного?