|
Zapiski Nauchnykh Seminarov POMI, 2019, Volume 488, Pages 97–118
(Mi znsl6913)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Cliques and constructors in “Hats” game. II
K. P. Kokhasa, A. S. Latyshevb, V. I. Retinskiyc a Saint Petersburg State University
b St. Petersburg National Research University of Information Technologies, Mechanics and Optics, Information Technologies and Programming Faculty
c National Research University "Higher School of Economics", Moscow
Abstract:
We analyze the following general variant of deterministic “Hats” game. Several sages wearing colored hats occupy the vertices of a graph, $k$th sage can have hats of one of $h(k)$ colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbours without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors.
We demonstarte here winning strategies fo the sages on complete graphs, and analyze the Hats game on almost complete graphs. We prove also a collection of theorems demonstrating how one can construct new graphs for which the sages win.
Key words and phrases:
game, graph, deterministic strategy, guessing color of hat.
Received: 02.12.2019
Citation:
K. P. Kokhas, A. S. Latyshev, V. I. Retinskiy, “Cliques and constructors in “Hats” game. II”, Combinatorics and graph theory. Part XI, Zap. Nauchn. Sem. POMI, 488, POMI, St. Petersburg, 2019, 97–118
Linking options:
https://www.mathnet.ru/eng/znsl6913 https://www.mathnet.ru/eng/znsl/v488/p97
|
Statistics & downloads: |
Abstract page: | 118 | Full-text PDF : | 29 | References: | 20 |
|