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

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

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

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

Сообщение Инна » 11 май 2017, 02:33

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

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

Сообщение Юляша » 11 май 2017, 12:04

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

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

Матожидание максимального результата при выборке 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.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3112
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Инна » 11 май 2017, 19:12

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

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

Сообщение Юляша » 12 май 2017, 10:10

Неужели, как обычно, 1-1/e?
Тогда, где-то должен ряд суммироваться...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3112
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Инна » 12 май 2017, 11:12

Скорeе, е/(e+1). При каком-то алгоритме (не факт, что лучшем) 0,726 получается (все цифры верные).
Но как математически формулу вывести, ума не приложу.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1427
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

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

Сообщение team55 » 12 май 2017, 16:53

Для трёх мудрецов по алгоритму Юляши получается 0.724 (139/192).
Инна писал(а): При каком-то алгоритме (не факт, что лучшем) 0,726 получается (все цифры верные).
Это для большего количества мудрецов шанс выиграть больше? Или алгоритм Инны и для трёх мудрецов даст больший шанс?
Аватара пользователя
team55
Графоман со стажем
Графоман со стажем
 
Сообщения: 711
Зарегистрирован: 18 апр 2006, 16:49

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

Сообщение Юляша » 12 май 2017, 19:23

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

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

Сообщение Инна » 12 май 2017, 20:50

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


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

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron