В одном королевстве жил король и 100 мудрецов.
Однажды король решил проверить мудрость своих подданных и объявил, что завтра на площади он выстроит всех мудрецов в ряд друг за другом и каждому на голову наденут либо красную, либо синюю шляпу. Мудрец не будет видеть свою шляпу, но будет видеть шляпы других мудрецов, стоящих в ряду перед ним (последний в ряду будет видеть шляпы всех остальных, первый - не будет видеть никого). Затем у каждого мудреца, начиная с последнего, будут спрашивать, какая на нём шляпа. Мудрец может ответить только "красная" или "синяя", ничего другого он сказать или сделать не может. Если мудрец отвечает правильно - его отпускают, если нет - его казнят.
Никак повлиять на своё положение в ряду никто из мудрецов не сможет. Все мудрецы услышат как сами ответы стоящих за ними, так и отклики о том, был ли ответ правильным. Мудрецы имеют ночь, чтобы согласовать между собой стратегию ответов.
Сколько мудрецов точно будут отпущены при наилучшей стратегии?
Правильно! Авторский ответ: 99 мудрецов
Неправильно, попробуйте обдумать задание ещё раз!
Вы уверены, что хотите получить подсказку? Это действие необратимо и может не позволить Вам
получить максимальное удовольствие от решения задачи! Если вы абсолютно уверены, то
нажмите сюда.
При наилучшей стратегии количество казненных мудрецов в худшем случае не зависит ни от общего числа мудрецов, ни от числа цветов шляп
Если вы уверены, что потеряли интерес к самостоятельному решению задачи и хотите подсмотреть авторский ответ, то
нажмите сюда.
Авторский ответ:
99 мудрецовЕсли вы хотите подсмотреть ещё и авторский ход решения задачи, то
нажмите сюда.
Авторское решение: Задача на чётность. Если красные шляпы считать за 0, а синие - за 1, то каждый мудрец, кроме последнего, может посчитать суммарную четность шляп стоящих перед собой. Последний мудрец должен ответить таким образом, чтобы сумма цветов шляп, включая его ответ была четной. Услышав ответ стоящего позади и его правильность, мудрецу достаточно своим ответом сохранять общую четность суммы с учётом его собственной шляпы. Таким образом, последний мудрец может погибнуть (с вероятностью 1/2), остальные могут точно определить и назвать цвет своей шляпы.