Мудрецы Толесникова

Логические задачи

Модераторы: Азарапетыч, Администрация

Ответить
Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Мудрецы Толесникова

Сообщение Инна »

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

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Мудрецы Толесникова

Сообщение Юляша »

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

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

Матожидание максимального результата при выборке 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.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Мудрецы Толесникова

Сообщение Инна »

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

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Мудрецы Толесникова

Сообщение Юляша »

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

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Мудрецы Толесникова

Сообщение Инна »

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

Аватара пользователя
team55
Популярный автор
Популярный автор
Сообщения: 1086
Зарегистрирован: 18 апр 2006, 16:49

Re: Мудрецы Толесникова

Сообщение team55 »

Для трёх мудрецов по алгоритму Юляши получается 0.724 (139/192).
Инна писал(а): При каком-то алгоритме (не факт, что лучшем) 0,726 получается (все цифры верные).
Это для большего количества мудрецов шанс выиграть больше? Или алгоритм Инны и для трёх мудрецов даст больший шанс?

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Мудрецы Толесникова

Сообщение Юляша »

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

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Мудрецы Толесникова

Сообщение Инна »

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

Ответить

Вернуться в «Задачки»