Задача со шляпами заключенных (#6)

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

Используя универсальный переводчик, один из пришельцев говорит: "Вас выстроят в одну линию по росту, так, что каждый сможет видеть всех кто стоит впереди. Вам запрещается оглядываться либо перемещаться. У каждого на голове будет либо белая, либо черная шляпа, причем цвет выбирается случайно и вы не будете знать сколько шляп каких цветов имеется. Когда я скомандую, вы все по очереди скажете цвет своей шляпы, начиная с человека сзади и двигаясь вперед. Даже не пытайтесь говорить что-нибудь кроме "Черная" или "Белая", или подавать сигналы иным образом, иначе всех вас немедленно съедят. Если хотя бы 9 угадают верно, вас всех отпустят. У вас 5 минут на то чтобы все обсудить и придумать план, затем я выстрою вас, надену шляпы и мы начнем".

Можете придумать стратегию, чтобы всех спасти?

Ответ под картинкой.

ОТВЕТ:

Ключ в том, что человек сзади, который видит шляпы всех остальных, может использовать слова "Черная" или "Белая" чтобы передать нужную информацию. Используем четность или нечетность количества шляп. Решение в том, чтобы договориться, что тот кто будет говорить первым должен будет, например, сказать "Черная", если увидит четное число черных шляп, и "Белая", если количество черных шляп будет нечетным.

Пусть первый, кто будет говорить, видит перед собой четное количество черных шляп. Тогда он говорит "Черная" (вероятность угадать 50%, но помним, что одному человеку позволено ошибиться). Следующий человек может видеть перед собой четное количество черных шляп (парность не изменилась), тогда он понимает что его шляпа имеет белый цвет, и наоборот, если видит нечетное количество черных шляп, понимает, что его шляпа имеет черный цвет. Каждый следующий действует таким же образом, запоминая при этом текущую парность черных шляп.

Вот и все, все свободны! Похоже этим пришельцам придется остаться без обеда, либо найти не таких сильных в логике существ.

Источник: ed.ted.com