Игра “Hats”. Сила конструкторов

Мы рассматриваем следующий общий вариант детерминированной игры “Hats”. В вершинах графа находятся мудрецы, на каждого мудреца надевают шляпы одного из $k$ возможных цветов. Каждый мудрец видит шляпы мудрецов в соседних вершинах, но не видит свою. Любые формы взаимодействия исключены. Каждый мудрец высказывает догадку, шляпа какого цвета надета на нем. Цель мудрецов состоит в том, чтобы хотя бы один из них угадал. В этой статье мы приводим пример планарного графа, на котором мудрецы выигрывают при $k=14$, а также даем простое доказательство известной теоремы об игре “Hats” на графах-“мельницах”. Библ. – 7 назв.