"Записки научных семинаров ПОМИ"
Том 498, стр. 26-37
Игра ``Hats''. Сила конструкторов
К. П. Кохась, А. С. Латышев
С.-Петербургский
государственный университет,
199034, С.-Петербург, Россия
kpk@arbital.ru
Федеральное государственное автономное
образовательное учреждение высшего образования
``Национальный исследовательский университет ИТМО'',
197101, С.-Петербург, Россия
aleksei.s.latyshev@gmail.com
- Аннотация:
Мы рассматриваем следующий общий вариант детерминированной
игры ``Hats''. В вершинах графа находятся мудрецы, на каждого мудреца
надевают шляпы одного из $k$ возможных цветов. Каждый мудрец видит
шляпы мудрецов в соседних вершинах, но не видит свою. Любые формы
взаимодействия исключены. Каждый мудрец высказывает догадку, шляпа
какого цвета надета на нем. Цель мудрецов состоит в
том, чтобы хотя бы один из них угадал.
В этой статье мы приводим пример планарного графа, на котором мудрецы
выигрывают при $k=14$,
а также даем простое доказательство известной теоремы об игре ``Hats''
на графах-``мельницах''.
Библ. -- 7 назв.
- Ключевые слова: игра ``Hats'', детерминированная стратегия
[hat guessing number, hat chromatic number, hat guessing game]
Полный текст(.pdf)