Занимательная задача про гномов и людоеда - Интересное - Каталог статей

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

"На следующее утро - сказал он, я построю вас в колонну и в случайном порядке надену на вас шапки двух цветов (красный и синий). Начиная с последнего в колонне, я буду спрашивать, какого цвета его шапка. Того, кто назовет цвет своей шапки правильно - отпущу, тех кто назовет неправильный цвет - того съем. Вы будете видеть всех тех, кто стоит впереди и слышать ответы тех, кто сзади. Но цвет своей шапки никто не видит. Говорить можно только одно слово – «красный» или «синий», иначе съем всех сразу".

Соотношение красных и синих шапок гномы не могут знать. Никакие дополнительные сигналы подавать нельзя (интонацией, паузами в ответах и т.п.).

Тем не менее, за ночь гномы придумали порядок ответов, который при этих условиях гарантировал выживание всех, кроме одного из них (у этого одного, тем не менее, тоже оставался шанс выжить).

Вопрос: какой способ придумали гномы?

ОТВЕТ
Ход рассуждений

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

Давайте на минуту представим, что ограничений на общение между гномами нет. Первый же гном сможет остальным озвучить всю последовательность цветов шапок. Но ему, увы, помочь никто не сможет: его шапку вообще никто не видит. Остальные гномы без вариантов должны говорить только цвета своих шапок – иначе решение не будет достигнуто. Только первый гном может позволить себе роскошь передать остальным некий код-отгадку, с помощью которой они смогут выжить.

Итак, только первый гном, который видит всех стоящих впереди, может зашифровать какую-то информацию для остальных. Но что можно зашифровать, если вариантов ответов только 2: «красный» или «синий»?

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

В двух вариантах ответов можно зашифровать, например, «четный» и «нечетный». Далее, примем красный цвет равный 1, а синий будет 0. Первый гном суммирует цвета шапок всех остальных, используя этот код. И результат сообщает вслух (например, красный – «четный», «синий» - нечетный – у гномов есть вся ночь, чтобы договориться об этом).

Второй гном, услышав шифр, так же суммирует всех стоящих впереди. Если результат совпадает с тем, что сказал первый гном, значит цвет его шапки не повлиял на общую сумму. Стало быть, это «ноль» - синий. Если результат изменился, значит это «единица» - красный.

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

Этот способ позволяет выжить N-1 гному. Общее количество гномов при этом не имеет значения, задача решается для любого N. Самый первый гном не обязательно погибает: с вероятностью 50% шифр может совпасть с цветом его шапки и тогда он останется жив и здоров.

P.S. Говорят, эту задачу предлагают на собеседовании в Microsoft