Людоед и гномики

Задача

Голодный людоед поймал семерых гномиков и собрался их съесть. Он заявил им следующее: «Я запру вас на ночь в пещере, а на следующее утро построю в колонну и надену каждому красную или зелёную шапочку. Каждый гномик будет видеть, какие шапочки на стоящих перед ним, но не будет видеть свою собственную и тех, кто позади. Я буду спрашивать по очереди, начиная с последнего гномика, какого цвета на них шапочки. Тех, кто ответит неправильно, буду съедать, а ответивших верно – отпущу. То, что будет говорить каждый гном, услышат все, поэтому на мой вопрос вы должны будете ровным голосом сказать только «красная» или «зелёная», при попытках выразиться по-другому или при вариациях тона вся компания будет съедена сразу же». За ночь гномы придумали такую стратегию поведения, которая позволит большинству из них выжить. В чём она заключалась? Можно ли её применить, если цветов шапочек будет более двух?

Решение

Говорят, что эту задачу дают на собеседовании в Microsoft. Первый приходящий в голову способ решения, когда гномы с нечётными номерами говорят цвет шапочек гномов, стоящих перед ними, а гномы с чётными номерами повторяют названный цвет позволит наверняка спасти только троих из всей компании, остальные четверо выживут с вероятностью 50% (если предположить цвета шапочек равно вероятными). Однако можно получить стопроцентные шансы на спасение всех гномов, кроме последнего.

Для этого поставим в соответствие красной шапочке число 0, а зелёной – 1. Последний гном складывает все числа, соответствующие шапочкам впереди стоящих, и, если число чётное, говорит «красная», если нечётная – «зелёная», иными словами, говорит тот цвет, который соответствует остатку от деления суммы чисел шапочек впереди стоящих гномов на 2. Съедят его затем или нет – уже дело случая, ему самому больше ничем не помочь.

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

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