Задача о разборчивой невесте
Интересная математическая задача из тероии вероятностей:
Оптимальная остановка случайных процессов :)
Теперь я расскажу саму задачу, ровно так, как её формулиро-
вал Гарднер. Это задача о разборчивой невесте. Пусть в некотором
царстве, в некотором государстве принцесса решила, что ей по-
ра найти себе жениха. Созвали царевичей и королевичей со всего
света, и явилось 1000 претендентов. Про любых двух когда-либо
увиденных принцесса может сказать, кто из них лучше. При этом
царевичи, как говорят математики, образуют упорядоченное мно-
жество, т. е. если Иван Царевич лучше Василия Царевича, а Ва-
силий Царевич лучше Фёдора Царевича, то Иван Царевич лучше
Фёдора Царевича. Претенденты входят к принцессе по очереди,
по одному, причём их порядок определён случайным образом, т. е.
вероятность появления какого-то царевича первым, или пятисо-
тым, или тысячным совершенно одинакова. Принцесса, разумеет-
ся, умея их сравнивать, может сказать, что, например, вошедший
тридцатым является десятым по качеству, т. е. девять из предыду-
щих были лучше, а остальные - хуже, и т. д. Цель принцессы -
получить самого хорошего жениха, т. е. даже второй её не устраи-
вает. На каждом шаге, т. е. после встречи с каждым из царевичей,
она решает, берёт ли она его в мужья. Если берёт, то на этом смотр
претендентов заканчивается, они все разъезжаются по домам.
Если же принцесса ему отказывает, то царевич, будучи отвергну-
тым, тут же уезжает домой, потому что все царевичи и королеви-
чи - люди гордые. Показ претендентов на замужество при этом
продолжается. Если в конце концов принцесса не получает лучшего,
то считается, что она проиграла, выходить замуж вообще не будет,
а уйдёт в монастырь (про монастырь я уже от себя придумал, у Гард-
нера этого не было). Спрашивается, как действовать принцессе,
чтобы с наибольшей вероятностью получить лучшего жениха.
Полность здесь:
http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf
Оптимальная остановка случайных процессов :)
Теперь я расскажу саму задачу, ровно так, как её формулиро-
вал Гарднер. Это задача о разборчивой невесте. Пусть в некотором
царстве, в некотором государстве принцесса решила, что ей по-
ра найти себе жениха. Созвали царевичей и королевичей со всего
света, и явилось 1000 претендентов. Про любых двух когда-либо
увиденных принцесса может сказать, кто из них лучше. При этом
царевичи, как говорят математики, образуют упорядоченное мно-
жество, т. е. если Иван Царевич лучше Василия Царевича, а Ва-
силий Царевич лучше Фёдора Царевича, то Иван Царевич лучше
Фёдора Царевича. Претенденты входят к принцессе по очереди,
по одному, причём их порядок определён случайным образом, т. е.
вероятность появления какого-то царевича первым, или пятисо-
тым, или тысячным совершенно одинакова. Принцесса, разумеет-
ся, умея их сравнивать, может сказать, что, например, вошедший
тридцатым является десятым по качеству, т. е. девять из предыду-
щих были лучше, а остальные - хуже, и т. д. Цель принцессы -
получить самого хорошего жениха, т. е. даже второй её не устраи-
вает. На каждом шаге, т. е. после встречи с каждым из царевичей,
она решает, берёт ли она его в мужья. Если берёт, то на этом смотр
претендентов заканчивается, они все разъезжаются по домам.
Если же принцесса ему отказывает, то царевич, будучи отвергну-
тым, тут же уезжает домой, потому что все царевичи и королеви-
чи - люди гордые. Показ претендентов на замужество при этом
продолжается. Если в конце концов принцесса не получает лучшего,
то считается, что она проиграла, выходить замуж вообще не будет,
а уйдёт в монастырь (про монастырь я уже от себя придумал, у Гард-
нера этого не было). Спрашивается, как действовать принцессе,
чтобы с наибольшей вероятностью получить лучшего жениха.
Полность здесь:
http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf