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

Александр выложил интересную задачу про гномиков.

Не придумал как вставить картинку к нему в каменты, поэтому решение привожу здесь.

Итак, вот схема:

В первой строке отмечены номера гномиков (для удобства), во второй их реальное расположение. Гномики смотрят вправо, т.е. номер первый видит всех, последний никого. Далее идут шаги которые гномикам нужно предпринять, чтобы всем спастись (в колонках отмечено кто и что делает).

Итак, первый гномик делает операцию последовательного XOR-а. Т.е. он берет 2-го и 3-го гномика и проводит XOR, результат я записал в колонку G (под третьего гномика). После чего он берет результат и XOR-ти с 4-м (результат под 4-го), потом этот результат XOR-ит c 5-ым и т.д. В итоге он получает значение, которое и называет (отмечено желтым). В зависимости от того совпало оно или нет людоед его съедает или нет и тут работает чистая удача.

Но дальше, все уже знают конечный XOR последовательности и могут понять кто они. Например на шаге 3 второй гномик предполагает, что он 0 (отмечено голубым). Исходя из этого он проводит последовательный XOR (шаг 4) и получает в результате 0 (отмечено красным). Поскольку его результат не совпадает с начальным, который посчитал 1-й гномик  (желтым) он понимает, что предположение о том, что он 0 было не верным, а значит он 1. И на 5-м шаге говорит: 1. Дальше аналогично третий гномик делает предположение и считает XOR и т.д.

UPD.: (извините, нужно было убегать, потому набросал саму идею, теперь формализую)
Или, говоря строгим языком математики:
Обозначим состояние шапки каждого гномика как X. Тогда состояние шапки n-го гномика будет X_n. Пусть, для определенности, у черных шапок X=1, а для белых X=0.
Так же для определенности, пусть общее количество гномиков равно m.
Вначале первый гномик (который видит всех) должен вычислить "общий XOR" (обозначим его Z) последовательности гномиков по формуле:

Z₁=(((X₂ XOR X₃) XOR X₄) XOR X₅) ... XOR X_m)

Полученный результат он называет и в зависимости от удачи людоед его съедает, либо нет. (Если Z₁ совпало с X₁, то, соответственно не съедает). Однако таким образом всем становится известно состояние X₁.
Дальше каждый гномик делает предположение о своем состоянии (X_n) и вычисляет собственный "общий XOR" (Z_n) по формуле:

Z_n=(((X_n-1 XOR X_n) XOR X_n+1) XOR X_n+2) XOR X_n+3) ... XOR X_m)

Если Z_n отличается от Z₁ то это означает, что предположение гномика о собственном состоянии было ошибочным и он называет противоположное. При совпадении, соответственно, предположение считается верным и называется именно оно.

Таким образом все гномики начиная со 2-го назовут заведомо верные собственные состояния.

Задача решена.