Людоед и гномики

Голодный людоед поймал гномиков и собрался их съесть. Он заявил им следующее: «Я запру вас на ночь в пещере, а на следующее утро построю в колонну и надену каждому красную или синюю шапочку. Каждый гномик будет видеть, какие шапочки на стоящих перед ним, но не будет видеть свою собственную и тех, кто позади. Я буду спрашивать по очереди, начиная с последнего гномика, какого цвета на них шапочки. Тех, кто ответит неправильно, буду съедать, а ответивших верно – отпущу. То, что будет говорить каждый гномик, услышат все, поэтому на мой вопрос вы должны будете ровным голосом сказать только «красная» или «синяя», при попытках выразиться по-другому или при вариациях тона вся компания будет съедена сразу же». Как нужно действовать гномикам, чтобы как можно больше из них спаслось?

Ответ: Очевидно, последний гномик ничего не может знать о том, какая шапочка на нём одета, следовательно, он может спастись только с вероятностью 0,5. Зато он может передать информацию другим гномикам, получив которую те могли бы спастись. Для этого в своём ответе он должен зашифровать информацию о чётности количества шапочек одного из цветов (например, красного), которые он видет перед собой. Например, если он видит перед собой чётное количество красных шапочек, он говорит: "красная", если нечётное - "синяя". Каждый последующий гномик должен сложить количество красных шапочек, которые он видит перед собой, с количеством раз, которое он услышал слово "красная". Если число получилось чётным, то на нём красная шапочка, о чём он тут же говорит людоеду. Если нечётным - то синяя. Таким образом можно спасти всех, кроме одного, гномиков. Последний же может спастись с вероятностью 0,5.

- (наведите курсор)

Зеркало