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

на первом курсе университета на "введении в специальность" нам старик-препод задавал эту задачу, и мы коллективно сообразили правильный ответ :)

Не, белка. Это фигня.

В поиск. А вообще, шах какой-то без фантазии. Демократический. Советский шах надевал на мудрецов колпаки ТРЕХ разных цветов.

Да ты что? Никогда не слышал. И оптимальная результат оставался тем же что и для двух?

s/оптимальная/оптимальный/

Впервые слышу о задаче с тремя шляпами...

Если n - кол-во колпаков того цвета, которого меньше, то 2n-1 выживут точно, у остальных 50%. Се ля ви. Я таки пгав, или нет?

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

Я тоже сначала так подумал, но потом понял, что при этом подразумевается равенство колпаков разного цвета. Более правильно мое решение выше.

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

Каждый мудрец знает все цвета перед ним и все цвета за ним, не знает только свой цвет. Контроль четноти (остаток от деления на n) позволяет восстановить 1 бит информации

ужос какой боян. они рискуют ниболее чем одним хреном. решение не рассказываю

>Каждый мудрец знает все цвета перед ним и все цвета за ним, не знает только свой цвет. Контроль четноти (остаток от деления на n) позволяет восстановить 1 бит информации

Мудрец видит 300 белых и 100 черных колпаков. Какой на нем? По условию ведь не сказано, что их число четно, а количество черных колпаков равно количеству белых.

Мудрец-камикадзе называет стоящему перед ним цвет его колпака, при таком раскладе погибает только один и то если его колпак другого цвета.

Не, белка. Туфта это. При твоём раскладе выживает каждый второй. А остальным - как повезёт. Вот про контроль чётность - то верно.

Перечитай, до полного и тотального просветления мозга.

> Если n - кол-во колпаков того цвета, которого меньше, то 2n-1 выживут точно, у остальных 50%. Се ля ви. Я таки пгав, или нет?

Хорошее решение за неимением лучшего. Но есть лучшее :). Гарантированно выживают n-1 человек. Ну и один как повезёт.

ага, сам прочитай.

Положим ситуация. Три мудреца. в очереди. Ч-Б-Ч. последний говорит предпоследнему цвет его колпака (белый). Итого, последний дал дуба, средний точно выжил если назвал свой цвет. Но если он назвал свой цвет, откуда первый узнает цвет своего?

По твоей теории второй назовет цвет своего колпака по наводке Мудреца-камикадзе, а как быть с третьим? Он то не знает своего цвета.

Перечитывай.

Туплю, ладно придется звать коминтерна.

>По твоей теории второй назовет цвет своего колпака по наводке Мудреца-камикадзе, а как быть с третьим? Он то не знает своего цвета.

как все плохо с логикой.

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

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

>Хорошее решение за неимением лучшего. Но есть лучшее :). Гарантированно выживают n-1 человек. Ну и один как повезёт.

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

Опередил, сабака эмо.

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

Ч-Б-Б-Ч-Ч-Б-Б

Слова мудрецов:
1) Чёрный (или б-белый, как повезёт)
2) Б-белый
3) Белый
4) Ч-чёрный
5) Чёрный
6) Б-белый

Тогда первому 50/50, остальные гарантированно выживут.

ИМХО так.

Хорошо. А для m цветов? расширим задачу Берии?

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

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

>Хорошо. А для m цветов? расширим задачу Берии?

Задача Берии подходит для любого количества цветов. Там все проще. Ну там каждый пятый, десятый. Применима не только к мудрецам.

Аналогично, слишком много информации передается, почему последнему мудрецу просто не крикнуть: "у впереди стоящего белый, впереди него черный и тп."? Или я опять туплю.

Есть слабинка: если кто-то из мудрецов "нативный" заика, то лучше его грохнуть своими силами лдо начала мероприятия :)

> Хорошо. А для m цветов?

У этой задачи одинаковое решение на любом кол-ве цветов.

Да тупишь, и я ступил. Генераторглюков дал правильный ответ, однако...

Видишь ли в условии задачи нет указания что мудрилы могут свободно общаться и называть суммы и проч, как бы они могут называть только _цвет_, иначе кердык.

Тогда как выполнить это:

>пусть белый колпак - нолик, черный - единичка. первый считает сумму и берет остаток от деления на два и _называет_.

> Вот про контроль чётность - то верно.

Как верно? Соотношение количества чёрных / белых ведь неизвестно.. Пусть первый мудрец скажет "белый", если белых чётно и "чёрный", если нечётно.. ну а дальше - понятно :)

Хотя, опять ступил, пойду чтоли спать.

а чёрных и белых равное количество или неизвестно?

неизвестно

Исходя из условия задачи мудрецы могут называть только цвет. Для начал пусть черный или белый.

Если впередистоящие мудрецы не знают, что сказали предыдущие, то они все погибают с вероятностью 0.5.

Если вередистоящие мудрецы слышат, какой цвет назвали все, стоящие сзади (и нефиг цепляться к условию), то они могут додуматься до простого алгоритма. Самый первый считает количество черных шапок перед ним и называет такой цвет, чтобы в сумме вышло четное число.

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

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

Для случая нескольких цветов вспоминаем, что четность -- это остаток от деления на 2.

Пусть цветов n. Тогда присвоим каждому из них цифру от 0 до n-1. Последний мудрец называет цвет соответсвующий остатку от деления суммы всех цветов шапок перед ним на n.

Следующий мудрец может посчитать сумму всех шапок перед ним и знает остаток деления всей суммы (все остальные + его шапка) на n. Соответсвенно, он может понять свой цвет.

Следующий мудрец (3) знает сумму перед собой и слышал цвета (читай, сумму) за собой и знает остаток от деления всей суммы (все остальные + его шапка) на n. Т.е. он в предыдущей ситуации и может назвать свой цвет точно.

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

Про заключенных и лампочку: В тюрьму приводят N заключенных, дают им пол часа пообщатья и разводят по одиночным камерам.

После этого начинают по одному в случайном порядке водить на допросы. На допросе задают один главный вопрос "Всех ли заключенных хотя бы один раз допрашивали?". Если допрашиваемый отвечает "нет", то его отводят обратно в камеру и продолжают допросы. Если он отвечает "да" и ошибается, то всех убивают. Если отвечает "да" и действительно всех хотя бы по одному разу допрашивали, то всех отпускают.

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

Как надо им действовать, чтобы всем освободиться?

Одного заключенного могут водить на допросы много раз. При этом считается, что хотя бы по разу рано или поздно допросят всех.

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

Возможно про лампочку надо завести отдельный треп.

>Завтра утром я велю надеть на вас колпаки и выстрою в очередь лицом на восток. Так, самый последний из вас будет видеть какие колпаки на всех

Нихрена он не будет видеть. Утром с востока солнце будет слепить глаза и все впереди стоящие колпаки будут чёрными =)

Мудрец называет цвет колпака впереди стоящего. Каждый второй точно спасется. Плюс каждый первый с вероятностью 1/кол-во_цветов.

sage

sage Мудрец во все поля!!!

Количество колпаков по цвету не ограничено, шанс умереть без чита рандомный.