Geodesic
For which graphs sages can guess a color of at least one hat
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IX, Tome 464 (2017), pp. 48-76
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Several sages wearing coloured hats are situated at the vertices of a graph. Each sage tries to guess his own hat colour merely on the basis of observing the hats worn by their neighbours without exchanging the information. Each hat can have one of three colours. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colours. We completely solve the question for which graphs the sages win. 
@article{ZNSL_2017_464_a2,
     author = {K. Kokhas and A. Latyshev},
     title = {For which graphs sages can guess a~color of at least one hat},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {48--76},
     year = {2017},
     volume = {464},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a2/}
}
TY  - JOUR
AU  - K. Kokhas
AU  - A. Latyshev
TI  - For which graphs sages can guess a color of at least one hat
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2017
SP  - 48
EP  - 76
VL  - 464
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a2/
LA  - ru
ID  - ZNSL_2017_464_a2
ER  - 
%0 Journal Article
%A K. Kokhas
%A A. Latyshev
%T For which graphs sages can guess a color of at least one hat
%J Zapiski Nauchnykh Seminarov POMI
%D 2017
%P 48-76
%V 464
%U http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a2/
%G ru
%F ZNSL_2017_464_a2
K. Kokhas; A. Latyshev. For which graphs sages can guess a color of at least one hat. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IX, Tome 464 (2017), pp. 48-76. http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a2/

[1] S. Butler, M. T. Hajiaghayi, R. D. Kleinberg, T. Leighton, “Hat guessing games”, SIAM review, 51 (2009), 399—413 | DOI | MR | Zbl

[2] T. Ebert, Applications of Recursive Operators to Randomness and Complexity, University of California, Santa Barbara, 1998 | MR

[3] M. Gardner, The Scientific American book of mathematical puzzles diversions, Simon and Schuster, 1959

[4] M. Krzywkowski, “On the hat problem, its variations, and their applications”, Annales Universitatis Paedagogicae Cracoviensis Studia Mathematica, 9:1 (2010), 55–67 | MR | Zbl

[5] W. W. Szczechla, “The three-colour hat guessing game on the cycle graphs”, Electronic J. of Combinatorics, 24:1 (2017), #P1.37 | MR | Zbl