Клоуны

Условие

В шеренгу выстроено n клоунов. На голову каждого надевают колпак одного из цветов: красного, желтого или зеленого. Клоун, стоящий в шеренге n-м, видит всех остальных клоунов, n-1-й клоун видит n-2 клоунов, стоящих впереди, ... 2-й клоун видит только первого, первый клоун не видит никого.

Цвет своего колпака клоун определить не может. Каждого клоуна по порядку, начиная с n-го, просят ответить, какого цвета у него колпак. Клоун обязан назвать один из 3 цветов.

Какое максимальное число клоунов может гарантированно угадать цвет своих колпаков? При этом клоуны перед опоросом могут договориться, но не могут заранее знать, какие колпаки на них наденут.

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

Ответ

Пронумеруем цвета числами от 0 до 2. Видя всех, кроме себя n-й клоун складывает числа, соответствующие цветам видимых им колпаков, и называет цвет, соответствующий остатку от деления полученной им суммы на 3.

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

Разность между ответом n-го клоуна и этим числом будет соответствовать цвету колпака на n-1-м клоуне, что даст ему возможность правильно назвать цвет своего колпака.

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