Разве можно здесь придумать какую-то стратегию?

Question

Разве можно здесь придумать какую-то стратегию?

AWESOM-O Мыслитель (7183), закрыт 9 лет назад

Гигант напал на деревню и поймал 10 гномов. Он выстроил их в ряд по росту, начиная с самых низких. Гигант в случайном порядке надел на каждого из гномов чёрные и белые шляпы. Каждый из них видит всех стоящих спереди, но не сзади. Гигант по очереди, начиная с самого высокого, спрашивает гномов о цвете их шляпы. Если он не угадал, то гигант убивает его. Стоящий позади ( думаю тут опечатка, все-таки - впереди) него гном не может понять, умер сосед или нет. Перед распределением шляп, гигант даёт гномам фору и разрешает обсудить свои действия. Какую следует гномам выбрать стратегию, чтобы умерло наименьшее количество созданий? Сколько минимально должно умереть гномов, чтобы остальные выжили?

Answer 1

При правильной стратегии может умереть только один гном - тот, кто отвечает первым, чью шапку никто не видел, зато который видел шапки всех остальных. Этот гном должен посчитать количество чёрных шапок, и сказать, чётное это количество или нет (мол, ответ "чёрный" - значит чётное, ответ "не чёрный" значит "нечётное"... или наоборот). Следующий гном слышал ту информацию, видит, чётное ли число чёрных шапок у остальных (кроме него), и поэтому точно знает цвет своей шляпы. Остальные тоже учитывают ответ первого и ответы остальных.

Кстати, традиционно эта задача звучит о мудрецах и жестоком правителе. Это путь восточной мудрости - покориться тирану. Более правильным считается ответ: гномы должны договориться и напасть на великана. Нанести хотя бы какой-то ему ущерб. Пусть они и умрут сразу - но рядом с таким великаном их жизнь всё равно не будет долгой...

Answer 2

Умрет 1 или 0 гномов, зависит от верности ответа первого гнома, а еще точнее, от того, стоят ли два первых гнома в одинаковых шляпах. Гномы договариваются о том, что называют цвет шляпы особым образом, в зависимости от впереди стоящего, чтоб ответ был и его цвет шляпы и подсказкой для следующего. Допустим, у второго гнома черная шляпа, первый гном называет цвет именно второго гнома, в свою очередь, второй гном смотрит на цвет третьего, если у него тоже черная, то он говорит "черная", если белая, то он должен сказать "не белая", чтоб третий гном услышал свой цвет шляпы. То есть, в ответе гнома должен быть цвет следующего, так каждый поймет цвет своей шляпы, Кроме первого, если его цвет шляпы совпадет со вторым, то он останется жив.