Клики и конструкторы в игре “Hats”. I

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