Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 78
Хватает и двух шляп и двух мудрецов. Просто нужно заранее договориться, что первый называет цвет шляпы второго. И соответственно второй уже называет цвет своей шляпы.
Получается возможна ситуация, когда не все цвета будут задействованы?
У меня вопрос. Правильное решение максимизирует вероятность выигрыша или гарантирует его?
Они могут сгрупироваться по цветам. Но что делать если все цвета уникальны?
Первое, что приходит в голову всем назвать 1 цвет, вероятность одного угаданного варианта 1 к 100. Но что-то мне кажется, что есть более красивое решение.
Они имеют право совершать какие-либо действия: двигаться, делать жесты? Или только смотрят на остальных, а потом по команде говорят цвет?
Увы только смотреть(
Ага, уже интереснее. Но как-то мне не верится, что есть стопроцентная стратегия
Чтобы поверить можно рассмотреть задачу два мудреца — два цвета.
Тут два варианта (и два других варианта инвариантны):
1. М1 — Ц1, М2 — Ц1
2. М1 — Ц1, М2 — Ц2.
Не существует алгоритма при заданных условиях определить на 100% цвет своей шляпы.
1. М1 — Ц1, М2 — Ц1
2. М1 — Ц1, М2 — Ц2.
Не существует алгоритма при заданных условиях определить на 100% цвет своей шляпы.
Не нужно всем гарантированно правильно определять свой цвет. Нужно, чтобы ХОТЬ ОДИН гарантированно определил свой цвет. И Вы совершенно верно разбили задачу на варианты. Дальше решение для двух мудрецов тривиально.
Для двух цветов и двух мудрецов всё просто:
Первый называет не свой цает (цвет, котороый видит на втором)
Второй называет не чужой цвет (цвета известны, называет не тот цвет, который видит на первом)
Первый называет не свой цает (цвет, котороый видит на втором)
Второй называет не чужой цвет (цвета известны, называет не тот цвет, который видит на первом)
Может так быть чтобы на всех мудрецах были шляпы одного цвета?
Ну… Они все могут обменяться шляпами и уже знать свой цвет… xD
Думаю, чтоб люди не искали вероятностные решения, стоит добавить условие о «full disclosure», то есть королю известно ВСЕ, о чем договорятся мудрецы и он может выбирать цвета шапок так, чтобы минимизировать/исключить вероятность выигрыша мудрецов исходя из заранее известной стратегии.
Не хочу спойлерить, но дам подсказку: чтоб толкнуть мысль в правильном направлении можно сначала решить достаточно тривиальный случай для двух цветов и двух мудрецов, а уж потом обобщать на N цветов/N мудрецов.
Решение для двух цветов может, кроме прочего, убедить неверующих существовании гарантированной стратегии выигрыша.
Не хочу спойлерить, но дам подсказку: чтоб толкнуть мысль в правильном направлении можно сначала решить достаточно тривиальный случай для двух цветов и двух мудрецов, а уж потом обобщать на N цветов/N мудрецов.
Решение для двух цветов может, кроме прочего, убедить неверующих существовании гарантированной стратегии выигрыша.
Первый мудрец должен назвать цвет другого мудреца предварительно посмотрев сначала на шляпу, а потом ему в глаза и подмигнув. Когда дело дойдет до того мудреца, цвет шляпы которого назвал первый, тот скажет этот же цвет. Надеюсь мудрец не тупой, и поймет что от него требуется.
одели, молча обменялись шляпами и сказали цвета? (: не?
Для 2 мудрецов подойдёт такая тактика:
1 из них называет цвет шляпы другого
А второй называет обратный цвет шляпы первого
Тогда если на обоих одинаковые шляпы, то 1 будет прав
Если разные, то второй угадает
1 из них называет цвет шляпы другого
А второй называет обратный цвет шляпы первого
Тогда если на обоих одинаковые шляпы, то 1 будет прав
Если разные, то второй угадает
А они знают все 100 цветов? иначе каждый из 100 мудрецов называет 1 цвет — хоть 1 да отгадает…
Назовем две разных цветовых последовательности принадлежащими к одному классу, если они совпадают, начиная с некоторого момента. По аксиоме выбора, из каждого класса можно выбрать по одному различному «представителю» — то есть сопоставить каждому классу одну конкретную последовательность цветов, причем все эти последовательности будут различными.
Заставим мудрецов запомнить это сопоставление. Тогда, видя перед собой бесконечное число шляп, каждый мудрец легко определяет класс, в который входит данная последовательность, и отвечает на заданный ему вопрос, называя тот цвет, который находится на данном месте в последовательности-«представителе». Поскольку все последовательности одного класса различаются только в каком-то (заведомо конечном) количестве начальных позиций, то казнено могут быть только конечное число мудрецов.
Заставим мудрецов запомнить это сопоставление. Тогда, видя перед собой бесконечное число шляп, каждый мудрец легко определяет класс, в который входит данная последовательность, и отвечает на заданный ему вопрос, называя тот цвет, который находится на данном месте в последовательности-«представителе». Поскольку все последовательности одного класса различаются только в каком-то (заведомо конечном) количестве начальных позиций, то казнено могут быть только конечное число мудрецов.
1. Все мудрецы решают кто за кем будет следить (как бы хоровод и каждый следит за тем кто слева)
2. Все цвета разделяются на пары (получится 50 пар)
3. Все мудрецы делятся на 2 группы
Далее все мудрецы 1 группы называют тот цвет что видят у соседа слева, а все мудрецы 2й группы называют противоположный (исходя из разделения цветов на пары)
Не уверен, но кажется должно сработать.
2. Все цвета разделяются на пары (получится 50 пар)
3. Все мудрецы делятся на 2 группы
Далее все мудрецы 1 группы называют тот цвет что видят у соседа слева, а все мудрецы 2й группы называют противоположный (исходя из разделения цветов на пары)
Не уверен, но кажется должно сработать.
Каждый мудрец одевает костюм одного из 100 цветов так, чтобы были костюмы всех 100 цветов.
Далее все глазами ищут того, у кого цвет костюма совпадает с цветом шляпы и останавливаются на нем взглядом.
Тот, на ком есть хоть один взгляд — называет цвет костюма.
М? :)
Далее все глазами ищут того, у кого цвет костюма совпадает с цветом шляпы и останавливаются на нем взглядом.
Тот, на ком есть хоть один взгляд — называет цвет костюма.
М? :)
перед одним поставить всю толпу, он посмотрит какие цвета использованы и назовет свой, при условии что он знает все цвета.а остальные наугад могут сказать.
Решение белым цветом (надеюсь, парсер не съет теги):
Перенумеруем мудрецов и шляпы от 0 до 99. Каждый мудрец считает сумму своего номера и номеров видимых ему шляп, берёт по модулю 100 и называет это число. Для произвольного количества мудрецов решение аналогично.
Доказательство: мудрец оказывается прав тогда и только тогда, когда его номер совпадает с остатком от деления суммы номеров шляп на 100. Следовательно, для любой суммы номеров цветов шляп найдётся ровно один мудрец, который не ошибся.
Забавно, что правильный цвет всегда называет ровно один мудрец, и это верно для любого решения головоломки.
Перенумеруем мудрецов и шляпы от 0 до 99. Каждый мудрец считает сумму своего номера и номеров видимых ему шляп, берёт по модулю 100 и называет это число. Для произвольного количества мудрецов решение аналогично.
Доказательство: мудрец оказывается прав тогда и только тогда, когда его номер совпадает с остатком от деления суммы номеров шляп на 100. Следовательно, для любой суммы номеров цветов шляп найдётся ровно один мудрец, который не ошибся.
Забавно, что правильный цвет всегда называет ровно один мудрец, и это верно для любого решения головоломки.
Верно, а как догадались?
Решил для двух мудрецов, подумал про разделение зон ответственности. Написал варианты для трёх, решил разделить ответственность по аналогии. Получилось. Ну а дальше всё просто, и решение сразу сформировалось, и доказательство придумалось.
Круто, а я
Представил, что есть функция из номеров 100 (номер аргумента — номер мудреца, значение — цвет на его шляпе) цветов в номер мудреца, который должен сказать верно. Каждый мудрец про себя думает, что именно он должен сказать правду, если это предположение неверно, то правду скажет кто-то другой, а если верно, то все ок; так вот мудрец знает, что он должен сказать верно, то есть что это он значение функции, кроме того ему известно 99 аргументов из 100, получается одно уравнение, одна неизвестная.
Далее, я сообразил, что если взять произвольный набор шляп и поменять шляпу под номером значения функции от этого набора, то значение функции должно измениться. После этого наложил более строгое условие: меняешь значение аргумента — меняется значение функции. Под это определение подходит остаток от суммы аргументов, и получилось решение
Представил, что есть функция из номеров 100 (номер аргумента — номер мудреца, значение — цвет на его шляпе) цветов в номер мудреца, который должен сказать верно. Каждый мудрец про себя думает, что именно он должен сказать правду, если это предположение неверно, то правду скажет кто-то другой, а если верно, то все ок; так вот мудрец знает, что он должен сказать верно, то есть что это он значение функции, кроме того ему известно 99 аргументов из 100, получается одно уравнение, одна неизвестная.
Далее, я сообразил, что если взять произвольный набор шляп и поменять шляпу под номером значения функции от этого набора, то значение функции должно измениться. После этого наложил более строгое условие: меняешь значение аргумента — меняется значение функции. Под это определение подходит остаток от суммы аргументов, и получилось решение
Белым цветом на случай если я не прав.
Итого: все от 0 до 98 видят 1 в сумме и называют соответственно цвета под номерами от 1 до 99 и все неправы.
Мудрец под номером 99 видит 0 и называет цвет под номером 99 и тоже не прав.
Перенумеруем мудрецов и шляпы от 0 до 99. Каждый мудрец считает сумму своего номера и номеров видимых ему шляп, берёт по модулю 100 и называет это число. Для произвольного количества мудрецов решение аналогично.Мудрецы с номерами от 0 до 98 имеют шляпу с цветом под номером 0, мудрец под номером 99 имеет шляпу с цветом под номером 1.
Итого: все от 0 до 98 видят 1 в сумме и называют соответственно цвета под номерами от 1 до 99 и все неправы.
Мудрец под номером 99 видит 0 и называет цвет под номером 99 и тоже не прав.
Это настолько близко у ответу, то я даже поверил и не проверил. Вот опровержение:
foreach (var x in data)
foreach (var y in data)
foreach (var z in data)
foreach (var w in data)
{
if ((0 + y + z + w) % 4 == x) continue;
if ((x + 1 + z + w) % 4 == y) continue;
if ((x + y + 2 + w) % 4 == z) continue;
if ((x + y + z + 3) % 4 == w) continue;
Console.WriteLine("fail");
return;
}Доказательство, с первого взгляда, вроде ничего не доказывает, а является переформулированным решением.
Это верно, но откуда это получилось? как вы писали, догадка на основе наблюдения случая 2,3 цветов?
Мудрец оказывается прав тогда и только тогда, когда его номер совпадает с остатком от деления суммы номеров шляп на 100
Это верно, но откуда это получилось? как вы писали, догадка на основе наблюдения случая 2,3 цветов?
Мудрец k называет цвет ans[k] = (k — sum(i!=k, color[i])) mod 100.
Утверждение «мудрец прав» означает, что ans[k] = color[k] и эквивалентно color[k] = (k — sum(i!=k, color[i])) mod 100 => k = sum(color[i]) mod 100, что и выражается фразой «k-й мудрец будет прав тогда и только тогда, когда его номер равен сумме цветов по модулю 100».
Утверждение «мудрец прав» означает, что ans[k] = color[k] и эквивалентно color[k] = (k — sum(i!=k, color[i])) mod 100 => k = sum(color[i]) mod 100, что и выражается фразой «k-й мудрец будет прав тогда и только тогда, когда его номер равен сумме цветов по модулю 100».
Думаю, что можно уже в открытую — ниже засветили ответ.
факт = «k-й мудрец будет прав тогда и только тогда, когда его номер равен сумме цветов по модулю 100»
А, это так, я просто думал, что доказательство имеет другую схему: этот факт предполагается очевидным, а из него уже следует решение; оказалось, что факт — свойство решения, которое можно проверить и убедиться в верности решения.
факт = «k-й мудрец будет прав тогда и только тогда, когда его номер равен сумме цветов по модулю 100»
А, это так, я просто думал, что доказательство имеет другую схему: этот факт предполагается очевидным, а из него уже следует решение; оказалось, что факт — свойство решения, которое можно проверить и убедиться в верности решения.
мудрец N: возможно цвет моей шляпы #806b2a
«Представьте себя на месте мудрецов, и попытайтесь придумать правильную стратегию» — и вы обеспечите решившего золотом на всю оставшуюся жизнь?
Препод по матану в МГУ загадывал нам такую задачку, решили группой, но решение не помню :)
Выбрать одного, который поставит всех мудрецов в ряд по градиенту. Каждый мудрец примерно будет знать в каком диапазоне находится его цвет.
а давайте так: все цвета — 0...99, значит цвет толпы мудрецов: x1+x2+...+x100 = y mod 100 (возьмем по модулю), чтобы найти свой цвет, каждый мудрец должен в уме решить это уравнение относительно своего xi: xi = 10n+y-x1-x2-..x(i-1)- x(i+1)-...-x100. Причем, в этом уравнение он не знает только y, т.к. сумму иксов он видит перед собой, а n-выбирается произвольно, чтобы ответ попал в 0...99. Для y существует 100 вариантов всего, мудрецов 100… значит каждый мудрец использует вместо игрека свой порядковый номер и одному точно повезет.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пятничная головоломка