"Записки научных семинаров ПОМИ"
Том 488, стр. 97-118
Клики и конструкторы в игре ``Hats''. II.
К. П. Кохась, А. С. Латышев, В. И. Ретинский
С.-Петербургский
государственный университет,
Университетская набережная 7-9,
199034, С.-Петербург, Россия
kpk@arbital.ru
Федеральное государственное
автономное образовательное учреждение
высшего образования
``Национальный исследовательский университет ИТМО''
Кронверкский проспект, д.49,
197101, г. С.-Петербург, Россия
alex_700_95@mail.ru
Национальный исследовательский университет
``Высшая школа экономики''
viretinskiy@gmail.com
- Аннотация:
Мы рассматриваем следующий общий вариант детерминированной игры ``Hats''.
В вершинах графа находятся мудрецы, на $k$-го мудреца надевают шляпы одного из $h(k)$ возможных цветов.
Каждый мудрец видит шляпы мудрецов в соседних вершинах, но не видит свою.
Любые формы взаимодействия исключены.
Каждый мудрец высказывает догадку, шляпа какого цвета надета на нем.
Цель мудрецов состоит в том, чтобы хотя бы один из них угадал.
В этой статье мы приводим явные стратегии,
с помощью которых мудрецы выигрывают на полных графах и анализируем игру на почти полных графах.
Мы также приводим набор теорем, позволяющих строить новые выигрышные для мудрецов графы из уже имеющихся.
Библ. -- 9 назв.
- Ключевые слова:игра, граф, детерминированная стратегия, угадывание цвета шляпы
[game, graph, deterministic strategy, guessing color of hat]
Полный текст(.pdf)