树上的帽子猜测游戏

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$ .

1. 引言

帽子猜测游戏可以追溯到一个经典且流行的奥林匹克问题，最初的正式版本由T. Ebert提出[1]。M. Farnik首先将帽子猜测数$HG\left(G\right)$ 定义为使得图$G$ 存在获胜策略的最大数$q$ [2]。在此后的研究中，各类图的帽子猜测数$HG\left(G\right)$ 成为了主要的研究方向。2021年，A. Latyshev发展并研究了允许智者们有不同种可能的帽子颜色，同时开创性地介绍了帽子猜测游戏的构造方法，可以通过已知的可以获胜的帽子猜测游戏构造新的可以获胜的帽子猜测游戏[3]。V. Blažej进一步提出了允许智者们有不同猜测次数的帽子猜测游戏[4]。在本文中，我们讨论一个更为通用的帽子猜测游戏版本，定义如下：设$G=\left(V,E\right)$ 为一个简单无向图。在$G$ 的每个顶点上都站着一位戴着某种颜色帽子的智者。我们通常将对应的顶点视为智者。图$G$ 上的一个帽子颜色函数$h:V\to \mathbb{N}$ 是一个表示智者可能拥有的不同帽子颜色数量的函数。对于每个智者$v_i\in V$ ，令$h_i=h\left(v_i\right)$ ，称为$v_i$ 的帽子颜色数。智者们试图通过观察其邻居的帽子颜色并遵循预先确定的策略来猜测自己帽子的颜色。图$G$ 上的猜测次数函数$g:V\to \mathbb{N}$ 是一个表示每个智者可以进行的猜测次数的函数。我们将该游戏记为$\mathcal{G}=\langle G,h,g\rangle$ 。我们用$\star m$ 表示常数函数$f(\cdot )=m$ 。如果$g=\star 1$ ，即每个智者恰好可以进行一次猜测，那么该游戏可简单记为$\mathcal{G}=\langle G,h\rangle$ 。在帽子猜测游戏$\mathcal{G}$ 中，如果一个策略能确保至少有$t$ 位智者的猜测是正确的，我们称其为$\mathcal{G}$ 的$t$ -获胜策略。否则，称其为$t$ -失败策略。如果游戏$\mathcal{G}$ 有$t$ -获胜策略，则称其为$t$ -获胜游戏，没有获胜策略的游戏称为$t$ -失败游戏。一个帽子游戏或为$t$ -获胜游戏，或为$t$ -失败游戏。当$t=1$ 时，我们将$t$ -获胜游戏简记为获胜游戏，其他同类定义类似。显然，$t$ -获胜游戏($t\ge 1$ )都是获胜游戏。此外，$HG\left(G\right)$ 的定义被扩展到$H{G}_s\left(G\right)$ ，它表示使得游戏$\mathcal{G}=\langle G,\star q,\star s\rangle$ 存在获胜策略的最大数$q$ ，注意$HG\left(G\right)=H{G}_1\left(G\right)$ 。

对于树$T$ 上的帽子猜测游戏$\mathcal{T}=\langle T,h,g\rangle$ ，S. Butler确定了$HG\left(T\right)=2$ [5]。A. Latyshev及其团队得到了当$g=\star 1$ 时帽子猜测游戏$\mathcal{T}$ 有获胜策略的一个充分条件，在本文中我们会证明这个充分条件实际上是必要的[3]。在后续的工作中证明了对于路径$P_n$ 上的帽子猜测游戏，有$H{G}_s\left(P_n\right)\le 4s-2$ 且当$n\ge 2s$ 时等号成立[6]。

2. 预备知识

2.1. 基本定义

考虑一个帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ 。对于图$G$ 中每个智者$v\in V\left(G\right)$ ，用$x_i$ 表示智者$v_i$ 帽子的颜色。那么$x_i\in \left[h_i\right]$ ，且$\chi =\left(x_1,x_2,\cdots ,x_n\right)$ 被称为游戏$\mathcal{G}$ 的一个帽子颜色分配。用$N\left(v_i\right)=\left\{u_1,u_2,\cdots ,u_k\right\}$ 表示$v_i$ 的邻点集合。智者$v_i$ 的猜测表示为一个函数$f_i=f_i\left(x_{u_1},x_{u_2},\cdots ,x_{u_k}\right)\in \left[h\left(v_i\right)\right]$ 。游戏$\mathcal{G}$ 的一个策略函数$f$ 是一个映射$f\left(x_1,x_2,\cdots ,x_n\right)=\left(f_1,f_2,\cdots ,f_n\right)$ 。如果在游戏$\mathcal{G}$ 中，没有智者能根据某个帽子颜色分配猜对自己帽子的颜色，那么这个分配就被称为策略$f$ 的一个错误的帽子颜色分配。

考虑帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ ，设$G^{\prime }$ 是$G$ 的一个诱导子图，$h^{\prime }={h|}_{G^{\prime }}$ 且$g^{\prime }={g|}_{G^{\prime }}$ 。我们称 ${\mathcal{G}}^{\prime }=\langle G^{\prime },h^{\prime },g^{\prime }\rangle$ 为$\mathcal{G}=\langle G,h,g\rangle$ 在$G^{\prime }$ 上的一个子游戏。如果一个帽子猜测游戏$\mathcal{G}$ 是获胜的，那么游戏$\mathcal{G}$ 一定也是获胜的。考虑两个在同一图$G$ 上的帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ 和${\mathcal{G}}^{\prime }=\langle G,h^{\prime },g^{\prime }\rangle$ ，对于任意的智者$v\in G$ ，有$h\left(v\right)\ge h^{\prime }\left(v\right)$ 且$g\left(v\right)\le g^{\prime }\left(v\right)$ 。若帽子猜测游戏$\mathcal{G}$ 是获胜的，有$\mathcal{G}$ 也是获胜的。

2.2. 基本定义

引理2.1：([4], Theorem 2)设$\mathcal{G}=\langle K_n,h,g\rangle$ 是一个在$n$ 个顶点的完全图$K_n$ 上进行的帽子猜测游戏。帽子猜测游戏$\mathcal{G}$ 获胜当且仅当${\displaystyle {\sum }_{v\in K_n}\frac{g\left(v\right)}{h\left(v\right)}}\ge 1$ 。

若对于树$T$ 中的每个顶点$v$ ，都有$h\left(v\right)\le 2^{d\left(v\right)}$ (其中$d\left(v\right)$ 是顶点$v$ 在$T$ 中的度)，则称树$T$ 上的帽子猜测游戏$\mathcal{T}=\langle T,h\rangle$ 为一个好树游戏。在路径上进行的好树游戏称为好路径游戏。

引理2.2：([3], Corollary 3.1)一个好树游戏$\mathcal{T}=\langle T,h\rangle$ 是获胜的。

引理2.3：([5])对于任意树$T$ ，有$HG\left(T\right)=2$ 。

引理2.4：设$G$ 是一个包含悬挂顶点$v_0$ 的图，图$G^{\prime }$ 是在$G\setminus \left\{v_0\right\}$ 上的$G$ 的诱导子图。设

$h^{\prime }\left(v\right)=\{\begin{array}{ll}{h}_1-\lfloor \frac{h_1}{h_0}\rfloor ,\hfill & \text{if}v=v_1,\hfill \\ h\left(v\right),\hfill & \text{otherwise}.\hfill \end{array}$

其中点$v_1$ 是$v_0$ 在$G$ 中唯一的邻点。如果帽子猜测游戏${\mathcal{G}}^{\prime }=\langle G^{\prime },h^{\prime }\rangle$ 是失败的，那么游戏$\mathcal{G}=\langle G,h\rangle$ 也是失败的。

Proof. 由于$v_0$ 的猜测函数是$f_0\left(x_1\right)$ ，所以存在$v_0$ 的一种颜色${\dot{x}}_0$ ，使得$v_1$ 最多只有$\lfloor \frac{h_1}{h_0}\rfloor$ 种颜色能使$f_0={\dot{x}}_0$ 。将${\dot{x}}_0$ 分配给$v_0$ ，我们可以从$v_1$ 剩余的至少$h_1-\lfloor \frac{h_1}{h_0}\rfloor$ 种颜色中选择一种进行分配，以确保$v_0$ 猜错。因为游戏${\mathcal{G}}^{\prime }$ 是失败的，所以游戏$\mathcal{G}$ 也是失败的。◻

设${\mathcal{G}}_1=\langle G_1,h^1,g^1\rangle$ 和${\mathcal{G}}_2=\langle G_2,h^2,g^2\rangle$ 是两个帽子猜测游戏，其中$G_1=\langle V_1,E_1\rangle$ ，$G_2=\langle V_2,E_2\rangle$ 且 $V_1\cap V_2=\left\{v_0\right\}$ ，$E_1\cap E_2=\varnothing$ 。考虑一个在图$G=\langle V,E\rangle$ 上进行的帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ ，其中$V=V_1\cup V_2$ 且$E=E_1\cup E_2$ 。设

$\left(h\left(v\right),g\left(v\right)\right)=\{\begin{array}{ll}\left(h^1\left(v\right)h^2\left(v\right),g^1\left(v\right)g^2\left(v\right)\right),\hfill & \text{if}v=v_0,\hfill \\ \left(h^1\left(v\right),g^1\left(v\right)\right),\hfill & \text{if}v\in V_1\setminus \left\{v_0\right\},\hfill \\ \left(h^2\left(v\right),g^2\left(v\right)\right),\hfill & \text{if}v\in V_2\setminus \left\{v_0\right\}.\hfill \end{array}$

帽子猜测游戏$\mathcal{G}$ 被称为${\mathcal{G}}_1$ 和${\mathcal{G}}_2$ 的积，并记为$\mathcal{G}={\mathcal{G}}_1{\times }_{v_0}{\mathcal{G}}_2$ 。

引理2.5：([3], Theorem 3.1)设${\mathcal{G}}_1=\langle G_1,h^1,g^1\rangle$ 和${\mathcal{G}}_2=\langle G_2,h^2,g^2\rangle$ 是两个帽子猜测游戏，其中$G_1=\langle V_1,E_1\rangle$ ，$G_2=\langle V_2,E_2\rangle$ 且$V_1\cap V_2=\left\{v_0\right\}$ 。如果游戏${\mathcal{G}}_1$ 和${\mathcal{G}}_2$ 都是获胜的，那么游戏$\mathcal{G}={\mathcal{G}}_1{\times }_{v_0}{\mathcal{G}}_2$ 也是获胜的。

引理2.6：设$G$ 是一个包含悬挂点$v_0$ 的图，$G^{\prime }$ 是由$G\setminus \left\{v_0\right\}$ 诱导的$G$ 的子图。设$v_1$ 是$G$ 中$v_0$ 的唯一邻点。考虑帽子猜测游戏$\mathcal{G}=\langle G,h\rangle$ ，其中$h_0=2$ ，以及游戏${\mathcal{G}}^{\prime }=\langle G^{\prime },h^{\prime }\rangle$ ，其中

$h^{\prime }\left(v\right)=\{\begin{array}{ll}\lfloor \frac{h\left(v\right)+1}{2}\rfloor ,\hfill & 若v=v_1,\hfill \\ h\left(v\right),\hfill & 若v\ne v_1.\hfill \end{array}$

帽子猜测游戏$\mathcal{G}$ 是获胜的当且仅当${\mathcal{G}}^{\prime }$ 是获胜的。

Proof. 若帽子猜测游戏${\mathcal{G}}^{\prime }$ 是失败的，那么根据引理2.4，游戏$\mathcal{G}$ 也是失败的。反之，假设帽子猜测游戏${\mathcal{G}}^{\prime }$ 是获胜的。由引理2.1，游戏${\mathcal{K}}_2=\langle K_2,2\rangle$ 是获胜的。根据引理2.5，帽子猜测游戏${\mathcal{G}}^{″}={\mathcal{G}}^{\prime }{\times }_{v_1}{\mathcal{K}}_2=\langle G,h^{″}\rangle$ 是获胜的。比较$\mathcal{G}$ 的帽子颜色函数$h$ 和${\mathcal{G}}^{″}$ 的帽子颜色函数$h^{″}$ ，对于$G$ 中的每个顶点$v$ ，都有$h\left(v\right)\le h^{″}\left(v\right)$ 。因此，帽子猜测游戏$\mathcal{G}$ 是获胜的。

引理2.7：([7], Theorem 4.1)设${\mathcal{G}}_1=\langle G_1,h^1,g^1\rangle$ 和${\mathcal{G}}_2=\langle G_2,h^2,g^2\rangle$ 为两个帽子猜测游戏，其中 $G_1=\langle V_1,E_1\rangle$ ，$G_2=\langle V_2,E_2\rangle$ 且$V_1\cap V_2=\left\{v_0\right\}$ 。考虑在并图$G=\langle V,E\rangle$ 上定义的帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ ，其中$V=V_1\cup V_2$ 且$E=E_1\cup E_2$ 。令

$\left(h\left(v\right),g\left(v\right)\right)=\{\begin{array}{ll}\left(h^1\left(v\right),g^1\left(v\right)\right),\hfill & 若v\in V_1\text{;}\hfill \\ \left(h^2\left(v\right),g^2\left(v\right)\right),\hfill & 若v\in V_2\setminus \left\{v_0\right\}\text{.}\hfill \end{array}$

当满足$h^2\left(v_0\right)\ge h^1\left(v_0\right)=2$ 时，游戏$\mathcal{G}$ 是获胜的当且仅当${\mathcal{G}}_1$ 或${\mathcal{G}}_1$ 是获胜的。

考虑一个帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ 。对于$G$ 中的一个顶点$u$ ，设$k$ 是一个正有理数，满足 $kh\left(u\right),kg\left(u\right)$ $\in \mathbb{N}$ 。图$G$ 上的游戏${\mathcal{G}}^{\left(k,u\right)}=\langle G,h^{\prime },g^{\prime }\rangle$ 是由游戏$\mathcal{G}$ 得到的，其中

$\left(h^{\prime }\left(v\right),g^{\prime }\left(v\right)\right)=\{\begin{array}{ll}\left(kh\left(v\right),kg\left(v\right)\right),\hfill & \text{if}v=u\text{,}\hfill \\ \left(h\left(v\right),g\left(v\right)\right),\hfill & \text{if}v\in G\setminus \left\{u\right\}\text{.}\hfill \end{array}$

我们称游戏${\mathcal{G}}^{\left(k,u\right)}$ 是$\mathcal{G}$ 的一个数乘。

引理2.8：设$k$ 是一个正整数。考虑帽子猜测游戏$\mathcal{G}=\langle G,h,g\rangle$ ，其中$v_1$ 是$G$ 中的一个顶点。若帽子猜测游戏$\mathcal{G}$ 是获胜的，那么$\mathcal{G}$ 的数乘游戏${\mathcal{G}}^{\left(k,v_1\right)}=\langle G,h^{\prime },g^{\prime }\rangle$ 是获胜的。

Proof. 设$f\left(x_1,\cdots ,x_n\right)=\left(f_1,\cdots ,f_n\right)$ 是$\mathcal{G}$ 的一个获胜策略，我们为${\mathcal{G}}^{\left(k,v_1\right)}$ 构造一个获胜策略$f^{\prime }$ 。定义

$f^{\prime }\left(v\right)=\{\begin{array}{ll}\left\{x|x\left(mod{h}_1\right)\in f_1,x\in \left[{h^{\prime }}_1\right]\right\},\hfill & \text{if}v=v_1\text{,}\hfill \\ f\left(x_1\left(mod{h}_1\right),x_2,\cdots ,x_n\right),\hfill & \text{otherwise}\text{.}\hfill \end{array}$

通过简单的验证，有$f^{\prime }$ 是${\mathcal{G}}^{\left(k,v_1\right)}$ 的一个获胜策略。

引理2.9：设${\mathcal{G}}_1=\langle G_1,h^1,g^1\rangle$ 和${\mathcal{G}}_2=\langle G_2,h^2,g^2\rangle$ 是两个帽子猜测游戏，其中$G_1=\langle V_1,E_1\rangle$ 是一个完全图，且${\displaystyle {\sum }_{v\in V_1}\frac{g^1\left(v\right)}{h^1\left(v\right)}}\le 1$ ，$G_2=\langle V_2,E_2\rangle$ 且$V_1\cap V_2=\left\{v_0\right\}$ 。若帽子猜测游戏$\mathcal{G}={\mathcal{G}}_1{\times }_{v_0}{\mathcal{G}}_2$ 是获胜的，那么游戏${\mathcal{G}}_2^{\left(g^1\left(v_0\right),v_0\right)}$ 是获胜的。

Proof. 设$f$ 是$\mathcal{G}$ 的一个获胜策略。考虑$\mathcal{G}$ 中$V_1$ 里智者的帽子颜色分配，共有 $N=h^1\left(v_0\right)h^2\left(v_0\right){\displaystyle {\prod }_{v\in V_1\setminus \left\{v_0\right\}}{h}^1\left(v\right)}$ 种不同的帽子颜色分配，而$V_1\setminus \left\{v_0\right\}$ 中的每个智者$v$ 可以猜对其中的$\frac{g^1\left(v\right)}{h^1\left(v\right)}N$ 种帽子颜色分配。由于${\displaystyle {\sum }_{v\in V_1}\frac{g^1\left(v\right)}{h^1\left(v\right)}}\le 1$ ，至少有$N-{\displaystyle {\sum }_{v\in V_1\setminus \left(v_0\right)}\frac{g^1\left(v\right)}{h^1\left(v\right)}N}\ge \frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}N$ 种帽子颜色分配使得$V_1\setminus \left\{v_0\right\}$ 中的任何智者都无法猜对。在这些帽子颜色分配中，因为游戏$\mathcal{G}$ 是获胜的，由于$V_1\setminus \left\{v_0\right\}$ 中的所有智者都猜测错误，那么至少有一个$V_2$ 中的智者猜测正确。对于$V_1$ 上的$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}N$ 种颜色分配，考虑$V_1\setminus \left\{v_0\right\}$ 上总共$\frac{1}{h^1\left(v_0\right)h^2\left(v_0\right)}N$ 种颜色分配。根据鸽巢原理，至少存在一个$V_1\setminus \left\{v_0\right\}$ 上的颜色分配$\chi$ ，使得$v_0$ 可以从至少$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}N/\frac{1}{h^1\left(v_0\right)h^2\left(v_0\right)}N=g^1\left(v_0\right)h^2\left(v_0\right)$ 种颜色中进行猜测。根据前文的论述，这保证了至少有一个$V_2$ 中的智者猜测正确。为$V_1\setminus \left\{v_0\right\}$ 中的智者选择这个帽子颜色分配$\chi$ ，那么$v_0$ 的猜测仅与$V_2$ 中的智者有关。现在我们在$G_2$ 上得到一个获胜游戏${{\mathcal{G}}^{\prime }}_2=\langle G_2,h^{2^{\prime }},g^{2^{\prime }}\rangle$ ，其中${h^{\prime }}_2\left(v_0\right)\ge g^1\left(v_0\right)h^2\left(v_0\right)$ 且$g^{2^{\prime }}\left(v_0\right)=g^1\left(v_0\right)g^2\left(v_0\right)$ 。这意味着帽子猜测游戏${\mathcal{G}}_2^{\left(g^1\left(v_0\right),v_0\right)}$ 也是获胜的。

3. 树上的帽子猜测游戏

在这一节中，我们将证明帽子猜测游戏在树上的两个重要结论：

定理3.1：树$T$ 上的帽子猜测游戏$\mathcal{T}=\langle T,h\rangle$ 是获胜的当且仅当$\mathcal{T}$ 有一个好树游戏作为其子游戏。

定理3.2：含有$n\left(\ge 2\right)$ 个顶点的树$T$ 的帽子猜测数$H{G}_s\left(T\right)\le \lceil q\rceil -1$ ，其中$q$ 满足$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ 。

在定理3.1中，我们首先给出具有任意帽子颜色函数的树的帽子猜测游戏是获胜的充分必要条件。在定理3.2中我们得到了树的$HG\left(T\right)$ 的一个上界。定理3.2给出的帽子猜测数的上界比文献中某些路径$P_n$ 的上界更紧。例如，根据定理3.2，长为3的路径的帽子猜测数$HG\left(P_3\right)\le 3s-1$ ，当$s\ge 2$ 时，这个上界小于中已知的上界$HG\left(P_3\right)\le 4s-2$ 。

定理3.1的证明。设$T$ 为一棵树。根据引理2.2，该定理的充分性是显然的。我们通过对$T$ 的顶点数进行归纳来证明必要性，即任意一个树$T$ 上的获胜的帽子猜测游戏$\mathcal{T}$ ，一定有一个好树游戏作为其子游戏。

对于$\left|V\left(T\right)\right|=1$ ，该图是一个只含一个顶点$v$ 的平凡图。仅当$h\left(v\right)=1=2^{d\left(v\right)}$ 时，这个游戏才是获胜的。因此游戏$\mathcal{T}$ 本身就是一个好树游戏。

假设对于$\left|V\left(T\right)\right|\le n-1$ 的树$T$ 上的帽子猜测游戏，必要性成立。对于$\left|V\left(T\right)\right|=n$ 的树$T$ ，我们证明如果游戏$\mathcal{T}$ 是获胜的，则存在一个好树游戏作为$\mathcal{T}$ 的子游戏来进行推导。存在以下三种情况：

情况1：对于$T$ 中的每个顶点$v$ ，$h\left(v\right)\ge 3$ ；

情况2：存在一个顶点$v_0$ ，满足$h_0=2$ 且度数为1；

情况3：存在一个顶点$v_0$ ，满足$h_0=2$ 且度数$d\left(v_0\right)\ge 2$ 。

对于情况1，根据引理2.3，帽子猜测游戏$\mathcal{T}$ 是失败的。因此在这种情况下，结论成立。

对于情况2，假设游戏$T$ 是获胜的。设$v_1$ 是$v_0$ 的唯一邻点。考虑${\mathcal{T}}^{\prime }=\langle T^{\prime },h^{\prime }\rangle$ ，其中$T^{\prime }$ 是由$V\setminus \left\{v_0\right\}$ 诱导的$T$ 的子图，并且$h^{\prime }\left(v\right)=\{\begin{array}{ll}\lfloor \frac{h\left(v\right)+1}{2}\rfloor ,\hfill & \text{if}v=v_1\hfill \\ h\left(v\right),\hfill & \text{if}v\ne v_1\hfill \end{array}$ 。根据引理2.6，由于游戏$\mathcal{T}$ 是获胜的，所以游戏${\mathcal{T}}^{\prime }$

也是获胜的。根据归纳假设，帽子猜测游戏${\mathcal{T}}^{\prime }$ 有一个好树游戏作为其子游戏，设这个好树游戏是 ${\mathcal{T}}_1=\langle T_1,H^1\rangle$ 。如果$v_1\notin T_1$ ，那么${\mathcal{T}}_1$ 也是$\mathcal{T}$ 的子游戏。如果$v_1\in T_1$ ，我们有$h_1\le 2{h^{\prime }}_1\le 2\cdot 2^{d^{\prime }\left(v_1\right)}=2^{d\left(v_1\right)}$ ，其中$d^{\prime }\left(v_1\right)=d\left(v_1\right)-1$ 是$v_1$ 在$T_1$ 中的度数。因此$\mathcal{T}$ 在$T_1$ 上的子游戏也是一个好树游戏。

对于情况3，假设游戏$\mathcal{T}$ 是获胜的。对于$1\le i\le d\left(v_0\right)$ ，设${\mathcal{T}}_i=\langle T_i,{h|}_{T_i}\rangle$ ，其中$T_i$ 是$T$ 的子图，满足${\displaystyle {\cup }_{i=1}^k{T}_i}=T$ 且对于任意$1\le i<j\le k$ 有$T_i\cap T_j=\left\{v_0\right\}$ 。反设$\mathcal{T}$ 没有好树游戏作为其子游戏。这意味着${\mathcal{T}}_i$ 也没有好树游戏作为其子游戏。由于$\left|V\left(T_i\right)\right|<n$ ，根据假设，${\mathcal{T}}_i$ 是失败的。然后根据引理2.7，$\mathcal{T}$ 是失败的，矛盾。证毕。

在给出定理3.2的证明之前，我们引入一类树上的帽子猜测游戏，称为坏树游戏，它提供了一种判断树上游戏是否为失败游戏的方法。我们证明了坏树游戏是失败的，并且如果$n$ 个顶点的星图$K_{1,n-1}$ 上的帽

子猜测游戏$\mathcal{T}=\langle K_{1,n-1},\star q,\star s\rangle$ 是坏树游戏且有$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ ，那么具有$n$ 个顶点的树$T$ 上的帽子猜测游戏$\mathcal{T}=\langle T,\star q,\star s\rangle$ 也是坏树游戏。

我们通过帽子猜测游戏的乘积和数乘，对树的顶点数归纳定义坏树游戏。考虑一个帽子猜测游戏$\mathcal{T}=\langle T,h,g\rangle$ ，其中$\left|V\left(T\right)\right|=2$ 。如果${\displaystyle {\sum }_{v\in T}\frac{g\left(v\right)}{h\left(v\right)}}<1$ ，则游戏$\mathcal{T}$ 被称为最小坏树游戏；如果${\displaystyle {\sum }_{v\in T}\frac{g\left(v\right)}{h\left(v\right)}}=1$ ，则被称为平衡树游戏。最小坏树游戏是坏树游戏，具有$n\left(\ge 3\right)$ 个顶点的树上的帽子猜测游戏是坏树游戏，当且仅当它满足以下条件中的至少一个：

1) 该游戏是一个具有$n-1$ 个顶点的坏树游戏与一个平衡树游戏的乘积；

2) 该游戏是一个具有$n$ 个顶点的坏树游戏的数乘。

引理3.1：给定树$T_1=\langle V_1,E_1\rangle$ 与$T_2=\langle V_2,E_2\rangle$ 满足$V_1\cap V_2=\left\{v_0\right\}$ 。设${\mathcal{T}}_1=\langle T_1,h^1,g^1\rangle$ 和${\mathcal{T}}_2=\langle T_2,h^2,g^2\rangle$ 分别为定义在树$T_1$ 和$T_2$ 上的两个帽子猜测游戏，且${\mathcal{T}}_2$ 为平衡树游戏。如果乘积$\mathcal{T}={\mathcal{T}}_1{\times }_{v_0}{\mathcal{T}}_2$ 在树$T$ 上构成坏树游戏，则游戏${\mathcal{T}}_1$ 必为坏树游戏。

Proof. 通过对树$T$ 顶点数的归纳来证明该结论。

当$\left|V\left(T\right)\right|=3$ 时，由于$\mathcal{T}={\mathcal{T}}_1{\times }_{v_0}{\mathcal{T}}_2$ 是坏树游戏，它必然是最小坏树游戏${\mathcal{T}}_3=\langle T_3,h^3,g^3\rangle$ 与平衡树游戏${\mathcal{T}}_4=\langle T_4,h^4,g^4\rangle$ 的乘积的倍数。假设$V\left(T_3\right)=\left\{v_0,v_1\right\}$ 且$V\left(T_4\right)=\left\{v_0,v_2\right\}$ ，则满足$\frac{g^3\left(v_0\right)}{h^3\left(v_0\right)}+\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}<1$ 和 $\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}+\frac{g^4\left(v_2\right)}{h^4\left(v_2\right)}=1$ 。

若$T_1=T_3$ ，则有$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}+\frac{g^1\left(v_1\right)}{h^1\left(v_1\right)}=\frac{g^3\left(v_0\right)}{h^3\left(v_0\right)}+\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}<1$ ，因此${\mathcal{T}}_1$ 是最小坏树游戏。

若$T_1\ne T_3$ ，则顶点$v_1\in V\left(T_2\right)$ 。由$\frac{g^2\left(v_1\right)}{h^2\left(v_1\right)}=\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}$ 可得$\frac{g^2\left(v_0\right)}{h^2\left(v_0\right)}=1-\frac{g^2\left(v_1\right)}{h^2\left(v_1\right)}=1-\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}>\frac{g^3\left(v_0\right)}{h^3\left(v_0\right)}$ 。根据乘积关系$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}\frac{g^2\left(v_0\right)}{h^2\left(v_0\right)}=\frac{g\left(v_0\right)}{h\left(v_0\right)}=\frac{g^3\left(v_0\right)}{h^3\left(v_0\right)}\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}$ 可得$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}<\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}$ 。再结合$\frac{g^1\left(v_2\right)}{h^1\left(v_2\right)}=\frac{g^4\left(v_2\right)}{h^4\left(v_2\right)}$ ，可得$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}+\frac{g^1\left(v_2\right)}{h^1\left(v_2\right)}<\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}+\frac{g^4\left(v_2\right)}{h^4\left(v_2\right)}=1$ ，故${\mathcal{T}}_1$ 仍为最小坏树游戏，归纳假设当$\left|V\left(T\right)\right|=n-1$ 时结论成立。现考虑$\left|V\left(T\right)\right|=n$ 的情形。由于$\mathcal{T}$ 是坏树游戏，它必然是含$n-1$ 个顶点的坏树游戏${\mathcal{T}}_3=\langle T_3,h^3,g^3\rangle$ 与平衡树游戏${\mathcal{T}}_4=\langle T_4,h^4,g^4\rangle$ 的乘积的倍数。

若$T_1=T_3$ ，则$T_2=T_4$ 。由分配关系$g^2\left(v_1\right)=g\left(v_1\right)=g^4\left(v_1\right)$ 和$h^2\left(v_1\right)=h\left(v_1\right)=h^4\left(v_1\right)$ 可得 $\frac{g^2\left(v_0\right)}{h^2\left(v_0\right)}=1-\frac{g^2\left(v_1\right)}{h^2\left(v_1\right)}=1-\frac{g^4\left(v_1\right)}{h^4\left(v_1\right)}=\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}$ ，说明${\mathcal{T}}_2$ 是${\mathcal{T}}_4$ 的倍数。再根据乘积关系 $\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}\frac{g^2\left(v_0\right)}{h^2\left(v_0\right)}=\frac{g^3\left(v_0\right)}{h^3\left(v_0\right)}\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}$ 可得$\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}=\frac{g^3\left(v_0\right)}{h^3\left(v_0\right)}$ 。注意到对任意$v\in V\left(T_1\right)\backslash \left\{v_0\right\}$ 都有 $g^1\left(v\right)=g\left(v\right)=g^3\left(v\right)$ 和$h^1\left(v\right)=h\left(v\right)=h^3\left(v\right)$ ，因此${\mathcal{T}}_1$ 是${\mathcal{T}}_3$ 的倍数，故${\mathcal{T}}_1$ 为坏树游戏。

若$T_1\ne T_3$ ，则可将${\mathcal{T}}_3$ 视为平衡树游戏${\mathcal{T}}_2$ 与某个游戏${\mathcal{T}}_5$ 的乘积。根据归纳假设，${\mathcal{T}}_5$ 必为坏树游戏。此时坏树游戏${\mathcal{T}}_5$ 与平衡游戏${\mathcal{T}}_4$ 的乘积仍为坏树游戏，而该乘积是${\mathcal{T}}_1$ 的倍数，因此${\mathcal{T}}_1$ 必为坏树游戏。

引理3.2：设${\mathcal{T}}_1=\langle T,h^1,g^1\rangle$ 和${\mathcal{T}}_2=\langle T,h^2,g^2\rangle$ 是树$T$ 上的两个帽子猜测游戏。若对$T$ 中每个顶点$v$ 都满足$\frac{g^1\left(v\right)}{h^1\left(v\right)}\ge \frac{g^2\left(v\right)}{h^2\left(v\right)}$ ，则当${\mathcal{T}}_1$ 是坏树游戏时，${\mathcal{T}}_2$ 也必为坏树游戏。

Proof. 我们对树$T$ 的顶点数进行数学归纳。

当$\left|V\left(T\right)\right|=2$ 时，${\mathcal{T}}_1$ 是极小坏树游戏。此时有${\displaystyle {\sum }_{v\in V\left(T\right)}\frac{g^2\left(v\right)}{h^2\left(v\right)}}\le {\displaystyle {\sum }_{v\in V\left(T\right)}\frac{g^1\left(v\right)}{h^1\left(v\right)}}<1$ ，因此${\mathcal{T}}_2$ 也是极小坏树游戏。

假设结论对$\left|V\left(T\right)\right|=n-1$ 的情形成立。当$\left|V\left(T\right)\right|=n$ 时，取$v_0$ 为树$T$ 的叶，$v_1$ 为其邻点。令$T^{\prime }$ 为$T$ 在顶点集$V\left(T\right)\setminus \left\{v_0\right\}$ 上的诱导子图，$T^{″}$ 为$\left\{v_0,v_1\right\}$ 构成的路径。构造游戏${\mathcal{T}}_3=\langle T^{\prime },h^3,g^3\rangle$ 和平衡树游戏${\mathcal{T}}_4=\langle T^{″},h^4,g^4\rangle$ 。适当定义帽子颜色函数和猜测次数函数使得满足：$\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}=\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}$ ，$\frac{g^4\left(v_1\right)}{h^4\left(v_1\right)}=1-\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}$ ，$\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}\frac{g^4\left(v_1\right)}{h^4\left(v_1\right)}=\frac{g^1\left(v_1\right)}{h^1\left(v_1\right)}$ ，且对$T\setminus \left\{v_0,v_1\right\}$ 中每个顶点$v$ 有$\frac{g^3\left(v\right)}{h^3\left(v\right)}=\frac{g^1\left(v\right)}{h^1\left(v\right)}$ 。此时存在${\mathcal{T}}_1$ 的一个倍数，该倍数是${\mathcal{T}}_3$ 与${\mathcal{T}}_4$ 在$v_0$ 处的乘积。

同理，存在${\mathcal{T}}_2$ 的一个倍数，该倍数是游戏${\mathcal{T}}_5=\langle T^{\prime },h^5,g^5\rangle$ 与平衡树游戏${\mathcal{T}}_6=\langle T^{″},h^6,g^6\rangle$ 在$v_0$ 处的乘积。由于$\frac{g^4\left(v_0\right)}{h^4\left(v_0\right)}=\frac{g^1\left(v_0\right)}{h^1\left(v_0\right)}\ge \frac{g^2\left(v_0\right)}{h^2\left(v_0\right)}=\frac{g^6\left(v_0\right)}{h^6\left(v_0\right)}$ ，可得$\frac{g^4\left(v_1\right)}{h^4\left(v_1\right)}\le \frac{g^6\left(v_1\right)}{h^6\left(v_1\right)}$ 。又因 $\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}\frac{g^4\left(v_1\right)}{h^4\left(v_1\right)}=\frac{g^1\left(v_1\right)}{h^1\left(v_1\right)}\ge \frac{g^2\left(v_1\right)}{h^2\left(v_1\right)}=\frac{g^5\left(v_1\right)}{h^5\left(v_1\right)}\frac{g^6\left(v_1\right)}{h^6\left(v_1\right)}$ ，故$\frac{g^3\left(v_1\right)}{h^3\left(v_1\right)}\ge \frac{g^5\left(v_1\right)}{h^5\left(v_1\right)}$ 。根据引理3.1，因${\mathcal{T}}_1$ 是坏树游戏，${\mathcal{T}}_3$ 亦然。由归纳假设知${\mathcal{T}}_5$ 是坏树游戏，故由定义可知${\mathcal{T}}_2$ 是坏树游戏。

引理3.3：树$T$ 上的坏树游戏$\mathcal{T}=\langle T,h,g\rangle$ 是失败游戏。

Proof. 我们对树$T$ 的顶点数进行数学归纳。

当$\left|V\left(T\right)\right|=2$ 时，由引理2.1知极小坏树游戏是失败的。

当$\left|V\left(T\right)\right|=n$ 时，反设$\mathcal{T}$ 是必胜游戏。取$v_0$ 为叶子顶点，$v_1$ 为其邻点。根据引理2.8，其倍数 ${\mathcal{T}}^{\left(h\left(v_0\right)\left(h\left(v_0\right)-g\left(v_0\right)\right),v_1\right)}$ 是必胜的。构造平衡树游戏${\mathcal{T}}_1=\langle T_1,h^1,g^1\rangle$ ，其中$T_1$ 是$T$ 在$\left\{v_0,v_1\right\}$ 上的诱导子图，且满足

$\left(h^1\left(v\right),g^1\left(v\right)\right)=\{\begin{array}{ll}\left(h\left(v_0\right),h\left(v_0\right)-g\left(v_0\right)\right),\hfill & 若v=v_1\text{;}\hfill \\ \left(h\left(v_0\right),g\left(v_0\right)\right),\hfill & 若v=v_0\text{.}\hfill \end{array}$

再构造游戏${\mathcal{T}}_2=\langle T_2,h^2,g^2\rangle$ ，其中$T_2$ 是$T$ 在$T\setminus \left\{v_0\right\}$ 上的诱导子图，且满足

$\left(h^2\left(v\right),g^2\left(v\right)\right)=\{\begin{array}{ll}\left(h\left(v_1\right)\left(h\left(v_0\right)-g\left(v_0\right)\right),h\left(v_0\right)g\left(v_1\right)\right),\hfill & 若v=v_1\text{;}\hfill \\ \left(h\left(v\right),g\left(v\right)\right),\hfill & 若v\ne v_1\text{.}\hfill \end{array}$

注意到${\mathcal{T}}^{\left(h\left(v_0\right)\left(h\left(v_0\right)-g\left(v_0\right)\right),v_1\right)}={\mathcal{T}}_1{\times }_{v_1}{\mathcal{T}}_2$ 。根据引理2.9，游戏${\mathcal{T}}_2^{\left(\left(h\left(v_0\right)-g\left(v_0\right)\right),v_1\right)}$ 是必胜的。然而由于$\mathcal{T}$ 是坏树游戏，其倍数${\mathcal{T}}^{\left(h\left(v_0\right)\left(h\left(v_0\right)-g\left(v_0\right)\right),v_1\right)}$ 必为坏树游戏。由引理3.1可知${\mathcal{T}}_2$ 是坏树游戏，进而其倍数${\mathcal{T}}_2^{\left(\left(h\left(v_0\right)-g\left(v_0\right)\right),v_1\right)}$ 也是坏树游戏。根据归纳假设该游戏失败，矛盾。

设$T=\langle V,E\rangle$ 是有顶点$v_0$ 的树。顶点$v_{a1},v_{a2},\cdots ,v_{at}$ 和$v_{b1},v_{b2},\cdots ,v_{bt}$ 是不在$T$ 中的$2t$ 个顶点。图 $T_a=\langle V_a=V\cup \left\{v_{a1},v_{a2},\cdots ,v_{at}\right\},E_a\rangle$ 是通过将$v_0$ 与$v_{ai}\left(i=1,2,\cdots ,t\right)$ 相连得到的。图 $T_b=\langle V_b=V\cup \left\{v_{b1},v_{b2},\cdots ,v_{bt}\right\},E_b\rangle$ 是通过将$v_0$ 与$v_{b1}$ 相连，并且将$v_{b1}$ 与$v_{bj}\left(j=2,3,\cdots ,t\right)$ 相连得到的。我们有以下结果。

引理3.4：若游戏${\mathcal{T}}_a=\langle T_a,\star q,\star s\rangle$ 是坏树游戏且满足$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ ，则游戏${\mathcal{T}}_b=\langle T_b,\star q,\star s\rangle$ 也是坏树游戏。

Proof. 考虑树$T$ 上的两个游戏${\mathcal{T}}_{a0}=\langle T,h^{a0},g^{a0}\rangle$ 和${\mathcal{T}}_{b0}=\langle T,h^{b0},g^{b0}\rangle$ ，其中定义

$\left(h^{a0}\left(v\right),g^{a0}\left(v\right)\right)=\{\begin{array}{ll}\left({\left(q-s\right)}^t,s{q}^{t-1}\right),\hfill & �v=v_0�;\hfill \\ \left(q,s\right),\hfill & �v\ne v_0�\text{.}\hfill \end{array}$

以及

$\left(h^{b0}\left(v\right),g^{b0}\left(v\right)\right)=\{\begin{array}{ll}\left(q\left({\left(q-s\right)}^{t-1}-s{q}^{t-2}\right),s{\left(q-s\right)}^{t-1}\right),\hfill & �v=v_0�;\hfill \\ \left(q,s\right),\hfill & �v\ne v_0�\text{.}\hfill \end{array}$

首先证明：若游戏${\mathcal{T}}_{a0}$ 是坏树游戏，则${\mathcal{T}}_{b0}$ 也是坏树游戏。根据引理3.2，只需验证$\frac{g^{b0}\left(v_0\right)}{h^{b0}\left(v_0\right)}<\frac{g^{a0}\left(v_0\right)}{h^{a0}\left(v_0\right)}$ 。令$\frac{s}{q}=x$ ，则$0<x\le 1$ 。由$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ 及$2\le t\le n-1$ 可得$x<{\left(1-x\right)}^{n-1}\le {\left(1-x\right)}^t\le 1-x$ ，进而$x<\frac{1}{2}$ 。于是有

$\begin{array}{l}\frac{g^{b0}\left(v_0\right)}{h^{b0}\left(v_0\right)}-\frac{g^{a0}\left(v_0\right)}{h^{a0}\left(v_0\right)}\\ =\frac{s{\left(q-s\right)}^{t-1}}{q\left({\left(q-s\right)}^{t-1}-s{q}^{t-2}\right)}-\frac{s{q}^{t-1}}{{\left(q-s\right)}^t}\\ =\frac{x{\left(1-x\right)}^{t-1}}{{\left(1-x\right)}^{t-1}-x}-\frac{x}{{\left(1-x\right)}^t}\\ =\frac{x}{\left({\left(1-x\right)}^{t-1}-x\right){\left(1-x\right)}^{t+1}}\left({\left(\frac{1}{2}-{\left(1-x\right)}^t\right)}^2+x\left(1-x\right)-\frac{1}{4}\right)\\ <\frac{x}{\left({\left(1-x\right)}^{t-1}-x\right){\left(1-x\right)}^{t+1}}\left({\left(\frac{1}{2}-x\right)}^2+x\left(1-x\right)-\frac{1}{4}\right)\\ =0.\end{array}$

这表明当${\mathcal{T}}_{a0}$ 是坏树游戏时，${\mathcal{T}}_{b0}$ 必为坏树游戏。

其次证明：${\mathcal{T}}_a$ 是坏树游戏当且仅当${\mathcal{T}}_{a0}$ 是坏树游戏。对$i=1,\cdots ,t$ ，记$v_0$ 与$v_{ai}$ 的诱导子图为$T_{ai}$ 。考虑游戏${\mathcal{T}}_{ai}=\langle T_{ai},h^{ai},g^{ai}\rangle$ ，其中定义

$\left(h^{ai}\left(v\right),g^{ai}\left(v\right)\right)=\{\begin{array}{ll}\left(q,q-s\right),\hfill & �v=v_0�;\hfill \\ \left(q,s\right),\hfill & �v=v_{ai}�.\hfill \end{array}$

此时每个${\mathcal{T}}_{ai}\left(i=1,\cdots ,t\right)$ 均为平衡树游戏，且满足${\mathcal{T}}_a^{\left(q^{t-1}{\left(q-s\right)}^t,v_0\right)}={\mathcal{T}}_{a0}{\times }_{v_0}{\mathcal{T}}_{a1}{\times }_{v_0}\cdots {\times }_{v_0}{\mathcal{T}}_{at}$ 。根据坏树游戏定义并重复应用引理3.1，可知${\mathcal{T}}_a$ 为坏树游戏当且仅当${\mathcal{T}}_{a0}$ 为坏树游戏。

最后证明：${\mathcal{T}}_b$ 是坏树游戏当且仅当${\mathcal{T}}_{b0}$ 是坏树游戏。记$v_0$ 与$v_{b1}$ 的诱导子图为$T_{b1}$ ，$v_{b1}$ 与 $v_{bj}\left(j=2,3,\cdots ,t\right)$ 的诱导子图为$T_{bj}$ 。定义游戏${\mathcal{T}}_{b1}=\langle T_{b1},h^{b1},g^{b1}\rangle$ 和${\mathcal{T}}_{bj}=\langle T_{bj},h^{bj},g^{bj}\rangle$ ，其中

$\left(h^{b1}\left(v\right),g^{b1}\left(v\right)\right)=\{\begin{array}{ll}\left({\left(q-s\right)}^{t-1},{\left(q-s\right)}^{t-1}-s{q}^{t-2}\right),\hfill & �v=v_0�;\hfill \\ \left({\left(q-s\right)}^{t-1},s{q}^{t-2}\right),\hfill & �v=v_{b1}�\text{.}\hfill \end{array}$

以及

$\left(h^{bj}\left(v\right),g^{bj}\left(v\right)\right)=\{\begin{array}{ll}\left(q,q-s\right),\hfill & �v=v_{b1}�;\hfill \\ \left(q,s\right),\hfill & �v=v_{bj}�\text{.}\hfill \end{array}$

此时每个${\mathcal{T}}_{bj}\left(j=1,\cdots ,t\right)$ 均为平衡树游戏，且满足

${\left({\mathcal{T}}_b^{\left({\left(q-s\right)}^{t-1}\left({\left(q-s\right)}^{t-1}-s{q}^{t-2}\right),v_0\right)}\right)}^{\left(q^{t-2}{\left(q-s\right)}^{t-1},v_{b1}\right)}={\mathcal{T}}_{b0}{\times }_{v_0}{\mathcal{T}}_{b1}{\times }_{v_1}{\mathcal{T}}_{b2}{\times }_{v_1}\cdots {\times }_{v_1}{\mathcal{T}}_{bt}.$

根据坏树游戏定义并重复应用引理3.1，可知${\mathcal{T}}_b$ 为坏树游戏当且仅当${\mathcal{T}}_{b0}$ 为坏树游戏。

综上得证。

推论3.1：设$T$ 为具有$n$ 个顶点的树，$q$ 和$s$ 为正整数且满足$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ 。若星图$K_{1,n-1}$ 上的游戏$\mathcal{T}=\langle K_{1,n-1},h=\star q,g=\star s\rangle$ 是坏树游戏，则树$T$ 上的游戏$\mathcal{T}=\langle T,h=\star q,g=\star s\rangle$ 也是坏树游戏。

Proof. 该结果直接由引理3.4得出。

定理3.2的证明：由于$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ ，根据推论3.1和引理3.3，只需证明星图$K_{1,n-1}$ 上的游戏 $\mathcal{T}=\langle K_{1,n-1},h=\star q,g=\star s\rangle$ 是坏树游戏。

设$v_0$ 为$K_{1,n-1}$ 的中心顶点，$v_i\left(i=1,\cdots ,n-1\right)$ 为叶。记$v_0$ 与$v_i$ 的诱导子图为$T_i\left(i=1,\cdots ,n-1\right)$ 。任取$ϵ\in {\mathbb{Q}}^{+}$ ，记$ϵ=\frac{b}{a}\left(a,b\in {\mathbb{N}}^{+}\right)$ 。对$i=1$ ，构造坏树游戏${\mathcal{T}}_1=\langle T_1,h^1,g^1\rangle$ ，其定义为

$\left(h^1\left(v\right),g^1\left(v\right)\right)=\{\begin{array}{ll}\left(q,s\right),\hfill & �v\ne v_0�;\hfill \\ \left(aq,a\left(q-s-ϵ\right)\right),\hfill & �v=v_0�\text{.}\hfill \end{array}$

对$i=2,\cdots ,n-1$ ，构造平衡树游戏${\mathcal{T}}_i=\langle T_i,h^i,g^i\rangle$ ，其定义为

$\left(h^i\left(v\right),g^i\left(v\right)\right)=\{\begin{array}{ll}\left(q,s\right),\hfill & �v\ne v_0�;\hfill \\ \left(q,q-s\right),\hfill & �v=v_0�\text{.}\hfill \end{array}$

令${\mathcal{T}}^{\prime }=\langle K_{1,n-1},h^{\prime },g^{\prime }\rangle ={\mathcal{T}}_1{\times }_{v_0}\cdots {\times }_{v_0}{\mathcal{T}}_{n-1}$ ，则${\mathcal{T}}^{\prime }$ 为坏树游戏。由于$\frac{s}{q}<{\left(1-\frac{s}{q}\right)}^{n-1}$ ，存在$ϵ\in {\mathbb{Q}}^{+}$ 使得$\frac{g^{\prime }\left(v_0\right)}{h^{\prime }\left(v_0\right)}=$ ${\displaystyle {\prod }_{i=1}^n\frac{g^i\left(v_0\right)}{h^i\left(v_0\right)}}=\frac{a\left(q-s-ϵ\right){\left(q-s\right)}^{n-2}}{a{q}^{n-1}}>\frac{s}{q}$ 。根据引理3.2，这表明原游戏$\mathcal{T}=\langle K_{1,n-1},h=\star q,g=\star s\rangle$ 是坏树游戏。再由引理3.3可知该游戏为失败游戏，因此帽子猜测数满足$H{G}_s\left(T\right)\le \lceil q\rceil -1$ 。

NOTES

^*通讯作者。