"Записки научных семинаров ПОМИ"
Том 464, стр. 48-76
На каких графах мудрецы могут угадать цвет хотя бы одной шляпы
К. П. Кохась, А. С. Латышев
С.-Петербургский
государственный университет,
Университетская набережная 7-9,
199034 Санкт-Петербург, Россия
kpk@arbital.ru
Факультет информационных технологий
и программирования Университет ИТМО,
пр. Кронверкский, д. 49,
197101 Санкт-Петербург, Россия
alex_700_95@mail.ru
- Аннотация:
В вершинах графа находятся мудрецы, на них надевают шляпы \emph{трех} различных цветов.
Каждый мудрец видит шляпы мудрецов в соседних вершинах, но не видит свою.
Любые формы взаимодействия исключены.
Каждый мудрец высказывает догадку, шляпа какого цвета надета на нем.
Цель мудрецов состоит в том, чтобы хотя бы один из них угадал.
Библ. -- 5 назв.
- Ключевые слова: игра, граф, детерминированная стратегия, информация
[game, graph, deterministic strategy, information]
Полный текст(.pdf)