RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2017 Volume 464, Pages 48–76 (Mi znsl6521)

This article is cited in 7 papers

For which graphs sages can guess a color of at least one hat

K. Kokhasa, A. Latyshevb

a St. Petersburg State University, St. Petersburg, Russia
b Information Technologies and Programming Faculty, St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, Russia

Abstract: 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.

Key words and phrases: game, graph, deterministic strategy, information.

UDC: 519.17+519.83

Received: 16.11.2017


 English version:
Journal of Mathematical Sciences (New York), 2019, 236:5, 503–520


© Steklov Math. Inst. of RAS, 2024