Подсказка - для двух цветов
N гномиков стоят в колонне. На голове у каждого гномика шляпа черного или белого цвета. Гномик не видит цвета своей шляпы, но видит цвет шляпы всех стоящих перед ним. Каждый гномик, начиная с конца колонны называет цвет: черный или белый. Если он угадал цвет своей шляпы, он остается в живых, в противном случае гибнет.
гномики могут договориться о наилучшей стратегии ответов, но только перед началом "опроса"
гномики не могут меняться местами
глухих и слабослышаших гномиков среди них нет
Вопрос : какое максимальное количество гномиков гарантированно может уцелеть при их наилучшей стратегии ?
Решение :
Последнему гному действительно абсолютно всё равнокакой цвет назвать - для случайной последовательности цветов ему, (как отвечающему на вопрос первым) ничего не поможет - его шансы 50/50.
Поэтому вся стратегия гномов заключается в следующем -
последний гном своим ответом кодирует соотношение цветов шляп всех гномов. Например если он называет "черный" - то количество черных шляп всех гномов (кроме него естественно) - четное.
Таким образом, уже предпоследний гном уже будет иметь полную информацию о количестве черных шляп всех оставшихся гномов, включая себя.
|
