Решение задачи 503

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

Решение:
Сопоставим белому цвету 1, а черному 0, тогда заключенные образуют бесконечную последовательность из единиц и нулей.

Рассмотрим все бесконечные последовательности из нулей и единиц. Разобьем их на классы эквивалентности. В каждом классе будут последовательности, любые две из которых отличаются в конечном числе позиций. Каждая последовательность попадет в какой-то класс, причем только в один. Для каждого класса заключенные заранее договариваются о представителе этого класса.

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

Итак, каждый из заключенных верно определил класс A, к которому принадлежит их последовательность. Все они вспомнят об одном и том же представителе b класса A, о котором они заранее договорились. Заключенный на позиции n называет цвет, соответствующий n-ому элементу последовательности b (1 - черный, 0 - белый). В итоге ошибутся только заключенные, стоящие на позициях, в которых a и b различаются. Но так как a и b из одного класса A, то они различаются в конечном числе позиций.