Лека прислала чудеснейшую задачку.
«Есть тролль, который любит поедать гномиков.
Тролль выставил гномиков на полянке в шеренгу в затылок друг другу, предварительно надев на них белые и черные колпачки в случайном порядке и случайном количестве. Задние гномики могут видеть всех передних гномиков и какого цвета колпачки на них надеты. Тролль подходит к каждому гномику и спрашивает у него, какого цвета на гномике надет колпак. Если гномик угадывает — его не съедают.Гномику можно отвечать только одним из двух слов: «белый» или «чёрный». Если он скажет что-то еще — его съедают.
Передние гномики могут слышать ответы задних гномиков, и слышать результат: угадал или не угадал. Тролль начинает спрашивать гномиков с конца шеренги: сперва у последнего, потом у предпоследнего и т.д.
Задача: Как выжить большему количеству гномиков?»
 |
| JoyReactor |
Примечание: Похоже, что тролль предварительно объяснил гномикам, что он будет делать, и у гномиков было время, чтобы договориться о стратегии до начала эксперимента.
Лека также прислала «самый шикарный алгоритм решения»:
«Если гномики договариваются закодировать четность колпачков определенного цвета, к примеру, чёрного.
Например, они договорились, что если [только] первый отвечающий гномик ответит «чёрный», значит количество гномиков с черными колпачками перед ним — чётное число. если он скажет «белый», значит нечётное.
И только на этом первом гномике действительно будет играть судьба — повезет или нет.
Второй гномик услышит ответ первого гномика, допустим «чёрный», посчитает количество чёрных колпачков перед собой. Если их будет нечётное число, он поймет, что на нём чёрный колпак. Если их будет чётное число, он поймет, что на нем белый колпак. И т.д. Остальным просто надо будет следить за ответами, считать чёрные колпачки перед собой и определять чётность».
Спасибо
Комментариев нет:
Отправить комментарий