Сообщение от matematik

N гномиков стоят в колонне. На голове у каждого гномика шляпа черного или белого цвета. Гномик не видит цвета своей шляпы, но видит цвет шляпы всех стоящих перед ним. Каждый гномик, начиная с конца колонны называет цвет: черный или белый. Если он угадал цвет своей шляпы, он остается в живых, в противном случае гибнет.

гномики могут договориться о наилучшей стратегии ответов, но только перед началом "опроса"

гномики не могут меняться местами

глухих и слабослышаших гномиков среди них нет

Вопрос : какое максимальное количество гномиков гарантированно может уцелеть при их наилучшей стратегии ?



Решение :

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

Поэтому вся стратегия гномов заключается в следующем -
последний гном своим ответом кодирует соотношение цветов шляп всех гномов. Например если он называет "черный" - то количество черных шляп всех гномов (кроме него естественно) - четное.

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