Решение задачи про гномиков

Пришло время опубликовать ответ к предыдущей задаче

Есть такое понятие - бит четности. Оно используется в алгоритмах передачи данных. Суть следующая: при передаче последовательности бит (нулей/единиц) в последовательность добавляют еще один бит. Если количество единиц в последовательности четное, он равен единице, иначе нулю.

Эта идея используется в решении задачи. Пусть красные шапки - 0, синие - 1. Первый гном считает бит четности всех впереди стоящих гномов, называет его и умирает с вероятностью 50%. Второй гном считает бит четности по гномам впереди себя. Он сравнивает с ответом предыдущего гнома. Если значение бита четности изменилось, то на втором гноме шапка цвет которой мы приняли за 1, то есть синяя. Иначе красное.