Царь пытается выбрать из 100 невест, котрых он никогда не видел, самую красивую. Они случайным образом высративаются в ряд и по одной подходят к нему. Царь может либо объявить подошедшую самой красивой, либо продолжить смотрины. Он заранее с девушками не знаком, но легко упорядочивает их по красоте. Докажите, что царь может выбрать самую красивую с вероятностью большей, чем 1/3.

Нужно сперва просмотреть 27 девушек, и запомнить самую красивую,
Далее проверить всех остальных и если попадется красавица по-красивше
выбрать её, если не попадется, видать не судьба.
Цифру 27 взял от балды

> Нужно сперва просмотреть 27 девушек, и запомнить самую красивую,
> Далее проверить всех остальных и если попадется красавица по-красивше
> выбрать её, если не попадется, видать не судьба.
> Цифру 27 взял от балды


Ну, в общем, да. Я был менее оригинален и взял цифру 25 (половина), но думаю, что и для 27 пройдет, просто считать лень.

> Ну, в общем, да. Я был менее оригинален и взял цифру 25 (половина), но думаю, что и для 27 пройдет, просто считать лень.

Торможу!!! Конечно же, я брал 50, и для 27 этот способ не проходит.

Это классика жанра.
Только в классике эта задача называется "задачей о разборчивой невесте". И условие там с точностью до наоборот А придумал её Мартин Гарднер в 1960-х годах.

Алгоритм таков:
Первые n невест пропускаем, накапливая информацию (запоминаем максимально красивую X), из последующих N-n берем первую, которая лучше X, или последнюю, если не нашли такой.

Вероятность события "мы выбрали самую красивую" варьируется в зависимости от n. Оказывается, что если взять n=N/e, то эта вероятность будет равна 1/e — то есть больше 1/3 (e — это основание натурального логарифма). В данном случае n=36.

Исчерпывающего доказательства я не видел, но логика его понятна. Можно выписать вероятность события, что среди первых i открытых максимум будет j-м в общем порядке. Потом, через эту вероятность выразить вероятность искомого события (там будут суммы). Потом заметить там ряд Тэйлора для логарифма. Потом получить ответ

Have fun

Здравствуйте, vyxaryx, Вы писали:

V>Исчерпывающего доказательства я не видел, но логика его понятна. Можно выписать вероятность события, что среди первых i открытых максимум будет j-м в общем порядке. Потом, через эту вероятность выразить вероятность искомого события (там будут суммы). Потом заметить там ряд Тэйлора для логарифма. Потом получить ответ

Вот здесь все подробно расписано.