С М Е К А Л К И . Н Е Т
Задача 17. Сто мудрецов и шляпы
В одном королевстве жил король и 100 мудрецов.

Однажды король решил проверить мудрость своих подданных и объявил, что завтра на площади он выстроит всех мудрецов в ряд друг за другом и каждому на голову наденут либо красную, либо синюю шляпу. Мудрец не будет видеть свою шляпу, но будет видеть шляпы других мудрецов, стоящих в ряду перед ним (последний в ряду будет видеть шляпы всех остальных, первый - не будет видеть никого). Затем у каждого мудреца, начиная с последнего, будут спрашивать, какая на нём шляпа. Мудрец может ответить только "красная" или "синяя", ничего другого он сказать или сделать не может. Если мудрец отвечает правильно - его отпускают, если нет - его казнят.

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

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