Форум Академгородка, Новосибирск > Забавная задачка по теории игр: Дано n мудрецов...
Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Забавная задачка по теории игр: Дано n мудрецов...
Форум Академгородка, Новосибирск > Образование > Задачник
Crazy Diamond
Чем-то напоминает задачку про гномоеда http://forum.academ.org/index.php?showtopic=610897

Дано n мудрецов. Королю чем-то они не понравились, и он решил их казнить. Но его советник сказал, что, мол, это же очень умные люди, и их уничтожение не есть благо для государства. Тогда король решил проверить насколько они умные. Он спустился к ним в подвал (они все сидели в одной камере) и огласил: "Завтра я выдам каждому из вас по колпаку, где будет написано произвольное натуральное число от 1 до n. Каждый может видеть число других, но не видит своё. Если хоть один из вас отгадает, какое число написано у него на колпаке, то я вас помилую, если нет - казню". Мудрецы задумались. Как им нужно договориться, чтобы остаться в живых".

Собственно, примерно в такой трактовке мне её рассказали. Тогда же мне рассказали и решение для n=2. Остальные решения я не нашёл, и не знаю, есть ли они в принципе.

Решение для n=2:
Один из них называет число, которое видит у другого на колпаке, а тот, в свою очередь, называет число, отличное от того, что он видит (ну возможных чисел у нас 2, потому стратегия однозначна). Посмотрим, какие могут быть расклады, и что отвечают мудрецы:
1 1 : 1 2
1 2 : 2 2
2 1 : 1 1
2 2 : 2 1

То есть, если числа на колпаках различны, то угадывает своё число второй. Если числа совпадают, то первый.


Более поздняя правка: Да, кстати, забыл сказать: все мудрецы дают ответ втайне от собратьев.
EVGен
Как вариант:
1) Первый называет любое число, которое видит у других на колпаках.
2) Остальные называют то число, которое назвал первый.
conv
Бред какой-то в условии ... n мудрецов ... числа от 1 до n . Если все числа разные - то чего решать ? Чего не видишь - то и называй. Если условия уникальности чисел на колпаках нет - так тогда это чётко надо прописывать
в условии. И потом - что за 11, 12 в примере N=2 ? такое впечатление что написано с глубокого бодуна.
EVGен
Цитата(conv @ 22.11.2010, 9:41) *
Бред какой-то в условии ... n мудрецов ... числа от 1 до n . Если все числа разные - то чего решать ? Чего не видишь - то и называй. Если условия уникальности чисел на колпаках нет - так тогда это чётко надо прописывать
в условии. И потом - что за 11, 12 в примере N=2 ? такое впечатление что написано с глубокого бодуна.

Судя по примеру, числа могут повторяться, иначе ваще все просто. Как я понял "1 1:1 2": до двоеточия - это то, что у них реально на колпаках, после - то, что они называют.
conv
Да бред - не задача . Первый просто говорит число второго, второй как попугай повторяет - и всё, условие выполнено, остальные n-2 не при делах.
EVGен
Цитата(conv @ 22.11.2010, 9:55) *
Да бред - не задача . Первый просто говорит число второго, второй как попугай повторяет - и всё, условие выполнено, остальные n-2 не при делах.

Я тот же смысл вложил в свое решение) Так и не понял для чего был приведен этот пример с n = 2, наверное, чтоб направить людей в дебри какие-нибудь)
tuchka
видимо их опрашивают поочереди, ну уши там затыкают...

n=3
Первый говорит цифру второго, третий - цифру первого, а второй в случае, если цифры первого и второго различны говорит не такую как у них, а если одинаковы - цифру третьего
на примере 1 и других цифр, остальное аналогично
1 1 1 : 1 . 1
1 1 . : 1 . .
1 . 1 : . . 1
. 1 1 : . 1 .
. . . : . 1 .
conv
Видимо обмен информацией запрещен после начала написания цифирей на лбах. Ответ каждый пишет на тайной от остальных бумажке. Тогда смысл в задаче появляется.
EVGен
Ок. Давайте решать задачу при условии, что они не знают, что сказали остальные.
tuchka, где-то косяк в алгоритме.
tuchka
где?
а нашел
Crazy Diamond
Извиняюсь за не совсем полное условие: свои числа мудрецы пишут на листочке, в тайне от собратьев. Иначе и вправду получается бред какой-то. Числа могут быть произвольные, вполне могут повторяться - читайте внимательней условия: там сказано, что числа - произвольные натуральные от 1 до n.
Crazy Diamond
По поводу приведённого выше алгоритма - косяк найден.

Ну, во-первых, второй не знает цифру второго. Подразумевалось, скорее всего, "второй в случае, если цифры первого и третьего различны". Ну-с, такой алгоритм на числа 1 3 3 выдаёт 3 2 1.
Crazy Diamond
А, ну ты сам уже нашёл)))
Вот беда-то... Ну и что, какие будут идеи?

У меня как-то была мысль запрогать все стратегии, коих (если я не ошибаюсь) n^(n*(n-1)^n) штук (т.е. каждому нужно выбрать свой ответ на (n-1)^n возможных видимых ситуаций - имеем n^((n-1)^n) стратегий для одного игрока, - да плюс к тому эту стратегию нужно провернуть для каждого игрока, т.е. (n^((n-1)^n))^n = n^(n*(n-1)^n) вариантов). Если в числах то для каждого n получаем вариантов:
для 2 - 2^(2*1^2) = 4
для 3 - 3^(3*2^3) = 3^24 = 282 429 536 481 - уже настолько дофига...
для 4 - 4^(4*3^4) = 4^324 = 2^648 ~ 1,1679847981112819759721399310593e+195 - что-то как-то многовато... Ну для 3х ещё можно попробовать сделать.

А какие вообще могут быть подходы к обычному решению?
EVGен
Какая у нас цель задачи? Чтобы они точно выжили или выжили с большой вероятностью?

Если они точно должны выжить, то в стратегии точно кто-то должен писать число, которое он не видит.
Если они должны выжить с большой вероятностью, то могу привести несколько примеров)
Crazy Diamond
А вот не знаю... Ну, в любом случае первый случай содержится во втором... Ну если вы приведёте пример на некоторую достаточно большую вероятность, то попытайтесь доказать, что большая вероятность невозможна. Ежели наибольшая вероятность всё-таки меньше 1, то вот у меня созрела ещё задачка - король объявляет мудрецам ещё тот факт, что хочет казнить их с как можно большей вероятностью, т.е. числа на колпаках будут стоять самые наипечальнейшие.
Otouto
Эта задачка гораздо проще гномоедовской) Для удобства можно считать, что мудрецы пронумерованы. Пусть M_i - это i-тый мудрец, а K_i - число на колпаке M_i. Для n>=3

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

Место M_1 определяет M_2 c точностью до того случая, когда они сидят рядом. На этот случай есть M_3, который видит K_1 и K_2 и может усадить M_1 и M_2 в нужном порядке. Итак, можно считать что мудрецы линейно упорядочены.

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

Но если например 100 мудрецов строго линейно упорядочены и на их шапках номера от 1 до 100, каждый из них знает свой номер - достаточно взглянуть на шапку соседа.
tuchka
В общем виде:
n мудрецов
m-й мудрец говорит число равное mod(сумма чисел всех цифр на шапках друзей+m) по основанию n
для 3х проверил
EVGен
Otouto, думаю они не могут упорядочиваться, иначе задача становится совсем простой, что вы, собственно, и показали..
Crazy Diamond
Разумеется, EVGen, вы правы по поводу того, что Otouto не прав.

Пытаюсь проверить алгоритм tuchk'и. Как я понимаю, остаток от деления n*k на n подразумевает k? А вот нумеровать мудрецов с 1 или с 0? В первом случае контрпример 1 3 2 : 3 2 1, во втором он же 1 3 2 : 2 1 3. Я ничего не напутал?..
EVGен
Crazy Diamond, не напутали. С единицей на первом месте у меня 2 контрпримера: 1 1 3 и 1 3 2.
Otouto
Цитата(EVGен @ 22.11.2010, 13:55) *
Otouto, думаю они не могут упорядочиваться, иначе задача становится совсем простой, что вы, собственно, и показали..

Понятно, что в формулировке задачи чего-то не хватает. Например того, что мудрецы могут и не могут делать во время угадывания. До тех пор трактовать "Как им нужно договориться, чтобы остаться в живых" можно как угодно.
tuchka
остаток от деления n*k на n равен 0 =) И да, нумеровать лучше с 0 =)
но решение и правда врет =(
conv
Короче , видимо так : мудрецов собирают вместе, объясняют задачу, оставляют на некоторое время вместе (для того чтобы те придумали чего-то ) затем их разводят по отдельным камерам, пишут каждому на лбу его номер, и дают бумагу со списком оставшихся номеров. Грубо говоря, к этому списку он должен дописать собственнолобное число.

И , судя по всему , можно построить алгоритм, по которому хотя бы один из мудрецов назовет свое число правильно.
EVGен
Цитата(conv @ 22.11.2010, 14:50) *
Короче , видимо так : мудрецов собирают вместе, объясняют задачу, оставляют на некоторое время вместе (для того чтобы те придумали чего-то ) затем их разводят по отдельным камерам, пишут каждому на лбу его номер, и дают бумагу со списком оставшихся номеров. Грубо говоря, к этому списку он должен дописать собственнолобное число.

Да, только список дается в одном определенно порядке.

Цитата(tuchka @ 22.11.2010, 14:39) *
остаток от деления n*k на n равен 0 =) И да, нумеровать лучше с 0 =)

mod - это не остаток, так что n*k сравнимо с n по mod n.

P.s. решение врет в любом случае.
conv
Цитата(EVGен @ 22.11.2010, 15:04) *
Да, только список дается в одном определенно порядке.


Да в любом порядке - каждому дают свой уникальный список = список всех за вычетом его номера

И ещё - к ТС : А причём здесь теория игр ?
tuchka
переделал. Итак, первый мудрец - если видит одинаковые цифры, говорит такое же число, если разные - недостающее.
Второй то же самое но ответы смещает на 1 (если видит 2 и 1 говорит 1)
Третий смещает ответы аналогичным образом на 2
Crazy Diamond
Conv, ты не прав. Каждый мудрец знает не набор чисел, а на каком мудреце какое число (в условии так и написано). Хотя если в списке прописать не только числа, но и ещё какому мудрецу каждое из них соответствует, то можно и в произвольном порядке)))

По поводу теории игр - ну тут игра, команда мудрецов против короля. Первые выигрывают, если хотя бы одно число совпадает, иначе выигрывает второй. Требуется найти стратегию для первых.
conv
Цитата(Crazy Diamond @ 22.11.2010, 17:56) *
Требуется найти стратегию для первых.


По моему , в таких задачах надо найти точное решение - мудрецы (в данном случае - хотя бы один ) дают точный ответ.
Crazy Diamond
Цитата(conv @ 22.11.2010, 18:05) *
Цитата(Crazy Diamond @ 22.11.2010, 17:56) *
Требуется найти стратегию для первых.


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


Ну, собственно, стратегия выигрышная, если при каждом исходе хотя бы один из мудрецов назвал своё число.
Crazy Diamond
Цитата(tuchka @ 22.11.2010, 15:48) *
переделал. Итак, первый мудрец - если видит одинаковые цифры, говорит такое же число, если разные - недостающее.
Второй то же самое но ответы смещает на 1 (если видит 2 и 1 говорит 1)
Третий смещает ответы аналогичным образом на 2


Гм, а вот это решение, вроде как, правильное... Люди, проверьте его ещё разок, и вынесите свой вердикт, а...
EVGен
Она правильная, вчера сразу проверил smile.gif

P.s. случай при n = 2, кстати, можно в такой же формулировке переписать..
Crazy Diamond
А при n=4, 5, 6... эта стратегия проканывает?
tuchka
не уверен, но видимо как-то можно, проблема в том, что для 2 выбор однозначный, для 3 - два варианта, для большего числа надо придумывать больше вариантов поведения
conv
Задачка решается , похоже, методом "от безысходности".
Чего у нас есть (для каждого мудреца) ? Набор чисел на остальных (лбах) .Плюс неизвестное на своём. Но оно точно есть!
Чего из этого набора можно извлечь? С учётом того, что в числах (из математического удобства полагаем что не от 1 до n , а от 0 до n-1) присутствует 0 , всякие произведения - степени отбрасываем. Единственно разумным для дальнейшего рассмотрения взять сумму.

Чего ещё есть? Ага! Нам же можно о чём-то договориться до того как ... Но о чём ? Опять таки , не видно ничего кроме как перенумеровать себя (мудрецов) от 0 до n-1 !

Теперь , стало быть, надо придумать функцию F: Ответ(k) = F(S(k),k) , такую что хотя бы для одного k выполняется :
Ответ(k) = НомерНаЛбу(k) . где S(k) - сумма которую видит мудрец с номером k.

идейно понятно , что Ответ(k)=СуммаВсех - S(k).

Осталось элегантно формализовать.
EVGен
Я решииил для любого n smile.gif

Ps вечером могу кинуть и ответ, и доказательство того, что подойдет для любого n. Сейчас ограничен во времени просто(
conv
Цитата(conv @ 25.11.2010, 11:40) *
Осталось элегантно формализовать.


Продолжаем рассуждения дальше .. фактически мы пришли к тому, что задача определения НомерНаЛбу эквивалентна задаче определения СуммаВсех. Уже интересно ! Морщим ум ещё чуточку ... СуммаВсех - немного неоперабельно .. что если повозиться с объектом СуммаВсех по модулю n (запишем как mod(СуммаВсех,n)) ?! Числа получаются по крайней мере не какие-то непонятные, а как раз из диапазона 0...n .

Итак ищем : S(k) + Ответ(k) = СуммаВсех ... стало быть и по модулю n они совпадут .. так ...

mod( (S(k) + Ответ(k)), n ) = mod(СуммаВсех,n) .... и что дальше ? Ага ! А вот для правой части последнего выражения у нас уже есть сгенерированный набор значений - это порядковые номера мудрецов !!! Что же получается ? А получается , что каждый мудрец в качестве ответа должен сказать такое число, которое при сложении с суммой чисел остальных давало бы число, по модулю n равным его порядковому номеру. Осталось проверить - правильно это или нет и, если да, исчерпывающее ли это решение. Во как !

EVGен
Проведу анализ результата выше, а заодно и про свой напишу:

Обозначения:
1) на лбу им пишут числа от 0 до n-1. X(j) - число, которое написано на лбу.
2) заранее нумеруются они от 0 до n-1. j - номер мудреца
3) ост(t) - остаток от деления t на n
4) S - сумма всех чисел. S(j) = S - X(j) - сумма всех чисел, которые видит мудрец с номером j
5) k(j) - число, которое пишет мудрец с номером j.

Стратегия, которую привел conv: мудрец с номером j пишет на бумажке число от 0 до n-1 такое, что ост(k(j) + S(j)) = j.

Анализ:
ост(k(j) + S(j)) = j следовательно k(j) + S(j) - j = k(j) + S - X(j) - j = (k(j) - X(j) + (S - j) делится на n. Так как j принимает значения от 0 до n-1, то найдется такое j0, что S - j0 будет делиться на n, следовательно и k(j0) - X(j0) будет делится на n, а т.к. k(j0) и X(j0) могут принимать значения только от 0 до n-1, то k(j0) = X(j0).

Итог: мудрецы точно останутся живы!

Моя стратегия: мудрец с номером j пишет на бумажке число k(j) = ост((n - 1)S(j) + j).

Анализ:
Если найдется такое j0, что k = X(j0), то мудрецы останутся живы. Проанализируем разность k(j) и X(j): k(j) - X(j) сравнима по модулю n с (n - 1)S(j) + j - X(j) = (n - 1)S - (n - 1)X(j) + j -X(j) = n(S - X(j)) - S + j, а это сравнимо с j - S по модулю n. Так как S фиксирована, а j пробегает значения от 0 до n-1, то существует такой j0, что j0 - S будет сравнимо с 0 по модулю n, т.е. k(j0) - X(j0) будет сравнима с 0 по модулю n, а т.к. k(j0) и X(j0) могут принимать значения только от 0 до n-1, то k(j0) = X(j0).

Итог: мудрецы точно останутся живы!

Итого есть уже два алгоритма поиска чисел, которые не приводят к смерти мудрецов. Возникает вопрос, а одинаковые ли мы будем получать числа при данных алгоритмах? Может оба эти алгоритма приводят к одной и той же последовательности чисел.. Надо подумать.

Подумал. conv предлагает искать такое k(j), чтобы ост(k(j) + S(j)) = j, т.е. это можно переписать в виде k(j) = ост(j - S(j)), а я ищу k(j) по формуле k(j) = ост(j + (n - 1)S(j)), а так как j - S(j) сравнимо по модулю n с j + (n - 1)S(j), то отсюда следует, что последовательности чисел, написанных на бумажках мудрецами по этим двум алгоритмам, совпадут. Следовательно наши алгоритмы эквивалентны, т.е. формулы разные, но на выходе одинаковые последовательности получаем.
conv
Получается - решили задачку-то ?
EVGен
Цитата(conv @ 25.11.2010, 18:35) *
Получается - решили задачку-то ?

Типа того smile.gif
Crazy Diamond
Клёво!!!
gthnjdbx
Цитата(EVGен @ 25.11.2010, 12:13) *
...ост(k(j) + S(j)) = j....
стратегия: мудрец с номером j пишет на бумажке число k(j) = ост((n - 1)S(j) + j)
...
алгоритмы эквивалентны, т.е. формулы разные, но на выходе одинаковые последовательности получаем.
k(j)=ocm(j-s(j)) эквивалентна предложенным и выведена из них;
ocm(k(j)-X(j))=ocm(j-S(j)-X(j));
ocm(k(j)-X(j))=ocm(j-S); т.к. j в правой части принимает все значения от 0 до n-1 по одному разу, то и левая часть примет все значения от 0 до n-1 так же по одному разу, т.е. среди них будет и ноль, а значит и k(j)=X(j) написанное мудрецом равно написанному на лбу.
Поскольку в исходной задаче нет X(j)=0 зато есть =n тот у кого k(j) получится 0 должен написать n.
EVGен
Цитата(gthnjdbx @ 04.02.2011, 0:36) *
k(j)=ocm(j-s(j)) эквивалентна предложенным и выведена из них;

Так ведь conv и предложил эту стратегию smile.gif
conv
Что-то давно хитро-мудрых задач не появлялось ... скучно
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Русская версия IP.Board © 2001-2024 IPS, Inc.