Хах, давно уже знаю эту задачу, вроде даже на форуме ее уже обсуждали! Самый высокий должен назвать тот цвет, шляп которого перед ним четное/нечетное количество по предварительной договорености, вроде так. Исходя из этой инфы следующие гномы будут знать цвет своей шляпы.

ps идея хорошая, если можешь выкладывай задачи дальше.

каждый гном говорит цвет шапок, который преобладает, тогда кто-то из гномов выжевет)
если же гномы отвечают в произвольной форме, то зашифровывать цвет следующего в своем ответе

Разбиваются на пары, один из пары (кто стоит сзади) называет цвет шляпы другого.
Очевидно, минимум половина выживает (в худшем случае), матожидание выживших - 75%.

считаем белый истиной, черный - ложью (можно наоборот... не принципиально)

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

У гномов есть стратегия, которая будет стоить жизни максимум одному из них.

Пусть черные шляпы обозначают единицы, а белые - нули. Каждый гном вычисляет сумму по модулю 2 шляп перед ним. Первый (самый высокий гном) объявляет цвет, согласно сумме, им посчитанной. Он может быть убит либо нет (зависит от его удачливости… конечно, маги всегда могут подстроить так, что он умрет в любом случае, т.к. они знают, что используется оптимальная стратегия).

Следующий гном сравнивает сумму, посчитанную им, с суммой, сказанной самым высоким гномом. Если суммы совпадают, сие означает, что его шляпа белая, иначе - черная. Он объявляет свой цвет и выживает.

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

Итак, только самый первый (и самый высокий) гном погибает… что, на мой взгляд, объясняет, почему гномы такие низенькие.

The dwarves have a strategy that will cost the life of at most one dwarf. If you want to know what this strategy is, read on.

Let black hats signify 1's and white hats signify 0's. Each dwarf calculates the parity (sum modulo 2) of the hats in front of him. The first (tallest) dwarf announces the color corresponding to the parity he calculated. He may or may not be killed (depending on his luck... of course the Wizards can always engineer it so he dies, because they know this is the optimal strategy).

The next dwarf compares the parity he calculated and the parity the first dwarf announced. If the two parities are the same, that means his hat is white, otherwise it is black. He announces this color, and lives.

Each successive dwarf, armed with the original parity of all but the first dwarf and the colors of the hats of all the preceding dwarves (but the first), can easily calculate the color of his own hat. An inductive proof of correctness is pretty easy.

Thus only the first (and tallest) dwarf dies... which I guess explains why dwarves are so short.