树上的帽子猜测游戏

Hat Guessing Games on Trees

摘要: 设$\mathcal{G}=\langle G,h,g\rangle$ 是定义在图$G$ 上的帽子猜测游戏，其中$h$ 为帽子颜色函数，$g$ 为猜测次数函数。在该游戏中，图$G$ 的每个顶点$v$ 代表一位智者，每位智者会佩戴一顶从$h\left(v\right)$ 种可能颜色中选择的帽子。智者可以看到其邻点的帽子颜色，但无法观察自己的帽子颜色。根据预先制定的策略和可以看到的邻居帽子颜色，每位智者将对自身帽子颜色进行$g\left(v\right)$ 次猜测。若该策略能保证在任何颜色分配方案下都至少存在一个正确猜测，则称该游戏为获胜游戏。帽子猜测数$H{G}_s\left(G\right)$ 定义为使得当所有顶点$v$ 满足$h\left(v\right)=q$ 且$g\left(v\right)=s$ 时，图$G$ 上的帽子猜测游戏获胜的最大整数$q$ 。令$\star m$ 表示常数函数$f(\cdot )=m$ 。在论文中，我们研究树上的帽子猜测游戏。我们得到了当$h$ 任意，$g\left(v\right)=\star 1$ 时，树$T$ 上的帽子猜测游戏是获胜游戏的充分必要条件。并且得到了$g\left(v\right)=\star s$ 时$H{G}_s\left(T\right)$ 的一个上界。

Abstract: Let $\mathcal{G}=\langle G,h,g\rangle$ be a hat guessing game on a graph $G$ , where $h$ is a hat color function and $g$ is a guessing function. Each vertex $v$ in $G$ represents a sage who wears a hat of a color chosen from $h\left(v\right)$ possible options. Each sage can see the hat colors of their neighbors but not their own. Based on a predetermined strategy and the observed hat colors, each sage makes $g\left(v\right)$ guesses about their own hat color. The game is called winning if the strategy guarantees at least one correct guesses under any color assignment. The hat guessing number $H{G}_s\left(G\right)$ is defined as the largest integer $q$ such that the game is winning when $h\left(v\right)=q$ and $g\left(v\right)=s$ for all $v\in V\left(G\right)$ . Let $\star m$ denote the constant function $f(\cdot )=m$ . In this paper, we study the hat guessing games on trees. We provide a necessary and sufficient condition for the game $\langle T,h,g\rangle$ to be winning when $g\left(v\right)=\star 1$ and $h$ is arbitrary. We also derive an upper bound on $H{G}_s\left(T\right)$ when $g\left(v\right)=\star s$ .