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