Форум умных людей

     Пусть в некотором царстве, в некотором государстве принцесса решила, что ей пора найти себе жениха. Созвали царевичей и королевичей со всего света, и явилось 1000 претендентов. Про любых двух когда-либо
увиденных принцесса может сказать, кто из них лучше. При этом царевичи, как говорят математики, образуют упорядоченное множество, т. е. если Иван Царевич лучше Василия Царевича, а Василий Царевич лучше Фёдора Царевича, то Иван Царевич лучше Фёдора Царевича. Претенденты входят к принцессе по очереди, по одному, причём их порядок определён случайным образом, т. е. вероятность появления какого-то царевича первым, или пятисотым, или тысячным совершенно одинакова. Принцесса, разумеется, умея их сравнивать, может сказать, что, например, вошедший тридцатым является десятым по качеству, т. е. девять из предыдущих были лучше, а остальные — хуже, и т. д. Цель принцессы — получить самого хорошего жениха, т. е. даже второй её не устраи-
вает. На каждом шаге, т. е. после встречи с каждым из царевичей, она решает, берёт ли она его в мужья. Если берёт, то на этом смотр претендентов заканчивается, они все разъезжаются по домам. Если же принцесса ему отказывает, то царевич, будучи отвергнутым, тут же уезжает домой, потому что все царевичи и королевичи — люди гордые. Показ претендентов на замужество при этом продолжается. Если в конце концов принцесса не получает лучшего, то считается, что она проиграла, выходить замуж вообще не будет, а уйдёт в монастырь. Спрашивается, как действовать принцессе, чтобы с наибольшей вероятностью получить лучшего жениха. И какова эта вероятность?
P.S. Это вам не со взбалмошной старушкой и бедолагой Джо разбираться. И не кубики бросать.

Извиняюсь, вам решение из книжки привести? :-[

ЗЫ. Там были ученые и написанные на бумажках числа :)

   Это известная задача. Естественно, она представляет интерес только для тех людей, которые с ней не знакомы. Но если очень хочется привести решение из книжки, я возражать не буду.

Та нет, пусть люди решают :)

я в панике!! я бы посмотрела примерно 500 женихов... если бы на этом этапе ни от одного не свалилась в обморок от восторга, то брала бы максимально приличного из 490 - 510...

А если она выберет 300-го, а 800-й лучше. То что будет

ну, полагаю, будет жить с не самым лучшим, но вопрос ведь не в этом

ну вы хоть намекните, куда думать...

То есть в монастырь она не уйдёт?

Перед seamew встал острый вопрос выбора жениха

Уйдет :'(

Хайд -
//скрытый текст, требуется сообщений: 400//

жекас, Вы по задаче интересуетесь или по чайке?
зы: по задаче это имхо не имеет значения

самый лучший Царевич может и первым зайти  ??? :roll:

не может! пока хотя бы несколько других для сравнения не увидела, он не "лучший", а "первый встречный"

Ну развели флудилку))

Задачка-то интересная, хотя и сложная ;)

как не может? вероятность появления каждого царевича одинаковая
зы: так что  "любовь с первого раза взгляда" вполне возможна  :yesgirl:

Я не помню, как решать, поэтому попробую сам:

Показать скрытый текст

может, продиффиринцировать?

Та да, но я не знаю, как такие функции дифференцировать.

нам надо узнать, при каком N эта твоя жуткая формула имеет максимальное значение... нужно ее примерно построить и посмотреть, где максимум...

А мне это напомнило задачу о двух конвертах.

Мы выбираем конверт (мы не знаем, что там) == К нам заходит прынц (мы еше не знаем какой он)
Мы смотрим содержимое (оцениваем, узнаём) == Мы оцениваем прынца узнаём его "вес"
Нам предлагают поменят' конверт == Нам предлагают поменят' принца (сказат' нет и смотрет' следуюшего)

"Мощность" ("хорошеть") принцев как и сумм в конвертах вполне ограниченное число.
Мы стоим перед выбором: поменят' этого принца (этот конверт) на другого, в надежде получит' лучший вариант

не, тут фишка-то получить не лучший, а Наилучший вариант. Или не получить ничего...

    Как верно заметил Um_nik, если принцесса не угадала, то она уходит в монастырь. Нелегка жизнь принцессы. У нее нет  стратегии , которая гарантирует 100% успех.
    Можно заметить, что любая разумная стратегия принцессы сводится к выбору числа. Но мудро выбрать число сложно. Дерзайте!

Ну хорошо.

Метод: "Закрыт' глаза и выбрат' наугад"
Вероятност': 1/1000

Следовател'но, если ест' лучший метод, то он должен дат' бол'шую вероятност'  :laugh:

@Um_nik: Откуда формула?

http://nazva.net/forum/index.php/topic,3773.0.html

Принцесса, разумеется, умея их сравнивать, может сказать, что, например, вошедший тридцатым является десятым по качеству, т. е. девять из предыдущих были лучше, а остальные — хуже, и т. д.

смотрите, если она отсмотрела N претендентов, cледующим входит обалденный красавчик N+1, который лучше всех!! предыдущих, то ей надо выбирать его.
Т.к. выбрав принца N+1:
1. она точно получает лучшего из всех просмотренных
2. она его оставляет, то есть остальных она не смотрит (не может же она выбранного прогнать). следовательно из всех (виденных), она выбрала лучшего...

Начиркал)

   Да, это та  самая задача, но в другой формулировке.

VVV, если Вы прочли задачу в прошлой ее формулировке, то наверное также обратили внимание на замечания buka касательно представленного Ильей решения
интересно было бы узнать Ваше решение, а также Ваше мнение касательно того, на сколько оно (решение) обосновано
P.S. Это вам не бедолагу принцессу за царевичей-королевичей выдавать. И не мячики резать.  :tianchik:

   Решение обосновано, но некоторые моменты неплохо бы разобрать более четко. Чуть более подробное доказательство можно найти в книге С. М. Гусейн-Заде "Разборчивая невеста". Она есть в сети в свободном доступе. Эта книга написана на очень доступном языке.