Здравствуйте, nikov, Вы писали:

N>Однако, есть стратегия, которая гарантирует гораздо лучший исход. Попробуйте её найти.

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