danetka.ru

Каждому из стоящих в ряд 1000 мудрецов сообщают случайное число от 0 до 1 (равномерное распределение). Каждый мудрец знает своё число, но не знает остальных. После этого, начиная с последнего мудреца, все последовательно говорят "вист" или "пас" (висты и пасы слышны всем мудрецам). Если наибольшее из написанных чисел окажется у последнего вистовавшего мудреца, то мудрецы выиграли, иначе проиграли.
Придумайте коллективную стратегию, позволяющую выиграть с как можно большей вероятностью. Стратегия включает правило выбора "вист/пас" для каждого мудреца в зависимости от написанного ему числа, его места в ряду и предыдущих ответов, и список этих правил тоже можно считать известным для всех мудрецов

Насколько я понимаю, слышны только "висты" и "пасы", а числа остаются неизвестными до момента проверки.

Ну некий алгоритм я предложить могу, хотя оценить его качество не возьмусь.

Матожидание максимального результата при выборке n независимых равномерно распределенных чисел на отрезке [0,1] чисел равно n/(n+1).

Алгоритм может быть таким:
1. Вистов нет. Кроме данного мудреца, еще осталось k "неголосовавших" участников.
Мудрец вистует, если его число больше или равно, чем k/(k+1).

2. Висты есть. Первым был вист участника, когда оставалось m "неголосовавших", всего было p вистов.
Мудрец вистует, если его число больше или равно, чем (m-1)/m+1/m*(p/(p+1)).

В данной схеме мудрец вистует, если его число превосходит матожидание текущего максимума. Часть "или равно" не принципиальна.

--- добавление
Алгоритм точно оптимален в случае 2 мудрецов: P=13/16.

У двух мудрецов при пороге первого
1/3
а у второго для перекрытия виста первого
2/3
вероятность выигрыша получается 5/6.
П.С.
Я общее решение не знаю, можно обеспечить вероятность около 0.7...

Неужели, как обычно, 1-1/e?
Тогда, где-то должен ряд суммироваться...

Скорeе, е/(e+1). При каком-то алгоритме (не факт, что лучшем) 0,726 получается (все цифры верные).
Но как математически формулу вывести, ума не приложу.

Для трёх мудрецов по алгоритму Юляши получается 0.724 (139/192).

Инна писал(а): При каком-то алгоритме (не факт, что лучшем) 0,726 получается (все цифры верные).

Это для большего количества мудрецов шанс выиграть больше? Или алгоритм Инны и для трёх мудрецов даст больший шанс?

Ну мой алгоритм точно не оптимален - по крайней мере для двух мудрецов... (что, впрочем, оказалось довольно неожиданно для меня).
Для трех мудрецов вроде тоже не очень сложно получить точный результат - там всего шесть переменных , по которым нужна оптимизация. Попробую за выходные посчитать - может всплывут какие закономерности.

По идее, вероятность выигрыша при оптимальном алгоритме как функция от числа мудрецов должна убывать.
Нестрогое доказательство:
Допустим, мудрецам дополнительно сообщается, у кого минимум среди них. Получается, что фактически в вистовании фактически участвуют N -1 мудрец, а итоговый результат от дополнительной информации не ухудшится.
Нестрогость доказательства в том, что на самом деле мудрец с минимальным числом может участвовать и вистовать, действуя в соответствии с алгоритмом, например, если он говорит первым. Тогда его вист может отсечь некоторые последующие висты, которые, в свою очередь, отсекли бы абсолютный максимум при его молчании.