Задача про обиженного короля и сотню звездочётов

Король после пира в своём дворце дал команду страже арестовать 100 звездочётов, так как они позже всех пришли на празднество и этим его обидели. Он был любителем поиграть и приказал звездочётам выстроиться в ряд, задумав надеть на их головы синие и красные шляпы. После построения им будет запрещено общаться, издавать какие-либо звуки, оглядываться и снимать шляпы. Однако разрешено смотреть на шляпы стоящих спереди и слушать ответы стоящих сзади.

Король будет подходить к каждому звездочёту и задавать один и тот же вопрос: «какого цвета твоя шляпа?»

Учёные должны ответить на вопрос короля только одним словом: «красная» или «синяя». Неверный ответ карается тихой смертью, а за верный даруется жизнь (но всё равно придётся стоять безмолвно).

Король доходчиво объяснил, что в случае нарушения правил будет казнена вся сотня участников его игры. После чего разрешил учёным посовещаться.

Какой алгоритм поможет спасти максимальное количество звездочётов?

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

Решение

Звездочёты должны договориться и создать правило: первый отвечающий считает количество синих шляп перед собой, если это нечётное число, он говорит «синяя», если чётное — «красная». Следующий, видя количество и цвет шляп перед собой, может определить, какого цвета шляпа у него на голове (например, если синих все ещё нечётное количество, видимо, на нём красная). Можно вывести правило: если чётный номер говорит «синяя», то синих шляп нечётное число, если он говорит «красная», то красных шляп чётное число и т.д.

Таким образом гарантированно выживут 99 из 100. У первого шансы 50/50.

Обратите внимание на другую нашу задачку о том же короле.