论文标题
“帽子”游戏中的集团和构造函数
Cliques and constructors in "Hats'"game
论文作者
论文摘要
分析了以下确定性帽子游戏的一般变体。戴着彩色帽子的几个鼠尾草占据了图的顶点，$ k $ th的圣人可以带有$ h（k）$颜色的帽子。每个圣人都试图仅根据观察邻居的帽子而没有交换任何信息来猜测自己的帽子的颜色。如果预定的猜测策略是为了保证每项颜色任务至少一个正确的个人猜测，那么它将赢得胜利。 对于完整的图表和周期，我们解决了贤哲获胜的功能$ h（k）$的问题。我们在这里演示了完整图表上的圣人赢得策略，并在几乎完整的图表上分析帽子游戏。我们开发“构造理论”，这是一个定理的集合，展示了人们如何构建圣人赢得的新图形。我们还定义了新的游戏“ rook”，它等同于4循环的帽子游戏，并对此游戏进行完整的分析。
The following general variant of deterministic Hats game is analyzed. Several sages wearing colored hats occupy the vertices of a graph, the $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 neighbors without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. For complete graphs and for cycles we solve the problem of describing functions $h(k)$ for which the sages win. We demonstrate here winning strategies for the sages on complete graphs, and analyze the Hats game on almost complete graphs. We develop "theory of constructors", that is a collection of theorems demonstrating how one can construct new graphs for which the sages win. We define also new game "Check by rook" which is equivalent to Hats game on 4-cycle and give complete analysis of this game.
