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