外观
Skip to content 查看源代码：
查看源代码：
maximum-rest-time-in-round-robin-tournaments.md
---
title: 循环赛最大休息时间问题（草稿）
createTime: 2025/11/22
categories:
- study
tags:
- maths
---
## 问题引入
在比赛中，我们要确保运动员有充足的休息时间。基于这一背景，73Dsi 在 11 月 16 日发布了这一问题：
:::problem 原始问题
$n\ (n \ge 5)$ 个人打循环赛，证明存在一种安排比赛顺序的方式，使得一个人不会连续打两场比赛。
:::
这个问题是简单的。在此基础上，我们可以进行推广，继续探究能否将一个人打两场比赛的间隔提高。
:::problem
$n\ (n \ge 3)$ 个人打循环赛，每个人的最短比赛间隔的最大值 $g$ 是多少？
:::
## 上界
我们将 $p$ 和 $q$ 的比赛记作 $(p,q)$。
**因为 $n \ge 3$，所以至少有 $3$ 场比赛。**
记前 $(g+2)$ 场比赛分别为 $\{(p_1, p_2), (q_1, q_2), \dots, (q_{2g-1}, q_{2g}), (r_1, r_2)\}$，由间隔为 $g$ 有：
1. $p_i, q_i, r_i$ 分别各不相同；
2. $p_1, p_2, r_1, r_2 \notin \{ q_1, q_2, \dots, q_{2g} \}$；
3. $(p_1, p_2) \ne (r_1, r_2)$。
于是 $n \ge \bigl|\{p_1, p_2, q_1, q_2, \dots, q_{2g}, r_1, r_2\}\bigr| \ge 2g+3$，整理可得
$$
\boxed{ g \le \left\lceil\frac{n}{2}\right\rceil - 2 }
$$
如果存在一种构造能达到 $\left\lceil\dfrac{n}{2}\right\rceil - 2$ 的间隔，就能证明 $g = \left\lceil\dfrac{n}{2}\right\rceil - 2$。
## 简单情况与拆分
为了避免一上来就写出一大坨形式化构造，我们先从直观的画图讲起。
把每个人画成一个点，用两个点的连线表示一场比赛，我们就能得到像下面一样的图：
:::center
{width="400px"}
:::
然而这个图太复杂了，我们先来探究一些简单的图。
### 圈与链
圈与链是两种较简单的图。在圈和链上面，我们很容易达到 $g = \left\lceil \dfrac{n}{2} \right\rceil - 2$ 的上界，只需要给各个比赛标号，然后先按标号从小到大取奇数标号的比赛，再按标号从小到大取偶数标号的比赛即可，如下图：
:::center
（上图的数字是比赛的标号，不是比赛顺序）
:::
### Walecki 分解
于是我们有一种构造思路：将所有比赛拆成若干个圈/链，然后分别处理这些圈/链。而 Walecki 在百年前给出了如下图的巧妙构造：
:::center
（左图是对于偶数个点的图的构造，在它的基础上增加一个点，即有右图的奇数构造）
:::
基于 Walecki 的构造，我们便得以拆分问题。
### 错位构造
在每个圈/链上解决问题还不够，我们还需要保证它们合起来之后不会出现新的冲突。而得益于 Walecki 构造的高度对称性，我们有如下的安排方式，恰好将相近的边错开：
:::center
:::
上图可以让我们直观地理解最终的构造。此处我们不用上图对其进行证明，形式化的构造和证明将在下面给出。
## 形式化构造及证明
接下来，我们就要进入复杂的形式化证明了。
为了方便地表示构造，约定序列拼接符号：
:::definition 约定
$\{a_1, a_2, \dots, a_n\} \mathop{\#} \{b_1, b_2, \dots, b_m\} = \{a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_m\}$
$\mathop{\Large{\#}}\limits_{i=1}^{n} A_i = A_1 \mathop{\#} A_2 \mathop{\#} \cdots \mathop{\#} A_n$
与其他序列拼接时，只有一项的序列可以省略大括号。
:::
### 偶数情况
::::lemma 构造
设 $n = 2m$，记所有顶点为 $a_i, i=0, 1, \dots, n-1$，有构造
$$
\providecommand{\concat}{\mathop{\#}}
\providecommand{\bigconcat}{\mathop{\Large{\#}}\limits}
\bigconcat_{i=1}^{m} \left( {\color{red}{\bigconcat_{j=1}^{m} (a_{i-j}, a_{i+j-1})}} \right) \concat \left( {\color{blue}{\bigconcat_{j=1}^{m-1} (a_{i-j}, a_{i+j})}} \right)
$$
:::right
（下标 $\bmod n$）
:::
满足 $g = m-2 = \left\lceil\dfrac{n}{2}\right\rceil - 2$。
::::
::::proof
将构造分割为子串 $A_i = {\color{red}{\mathop{\Large{\#}}\limits_{j=1}^{m} (a_{i-j}, a_{i+j-1})}}, B_i = {\color{blue}{\mathop{\Large{\#}}\limits_{j=1}^{m-1} (a_{i-j}, a_{i+j})}}$，
因为 $A_i, B_i$ 内部不重且长度均 $\ge m-1$，要证此构造在 $(m-1)$ 轮内的点（选手）不重复，只需证相邻子串长度和为 $m-1$ 的前后缀的点不重复。
记 $\mathcal{P}_l(A_i)$ 为 $A_i$ 的长度为 $l$ 的前缀包含的点，$\mathcal{S}_l(A_i)$ 为 $A_i$ 的长度为 $l$ 的后缀包含的点，类似地定义 $\mathcal{P}_l(B_i), \mathcal{S}_l(B_i)$，则
$$
\begin{align*}
\mathcal{P}_l(A_i) &= \{a_{i-l}, \dots, a_{i+l-1}\} \\
\mathcal{S}_l(A_i) &= \{a_{i+m-l}, \dots, a_{i+m+l-1}\} \\
\mathcal{P}_l(B_i) &= \{a_{i-l}, \dots, a_{i+l}\} \setminus \{a_{i}\} \\
\mathcal{S}_l(B_i) &= \{a_{i+m-l}, \dots, a_{i+m+l}\} \setminus \{a_{i+m}\}\\
\end{align*}
$$
:::right
（下标 $\bmod n$）
:::
于是
$$
\begin{align*}
\mathcal{S}_{m-1-l}(A_{i}) =&\ \{a_{i+l+1}, \dots, a_{i-l-1}\} \\
\Longrightarrow&\ \mathcal{S}_{m-1-l}(A_{i}) \cap \mathcal{P}_{l}(B_{i}) = \emptyset \\[0.5em]
\mathcal{S}_{m-1-l}(B_{i}) =&\ \{a_{i+l+1}, \dots, a_{i-l-1}\} \setminus \{a_{i+m}\} \\
\mathcal{P}_{l}(A_{i+1}) =&\ \{a_{i-l+1}, \dots, a_{i+l}\} \\
\Longrightarrow&\ \mathcal{S}_{m-1-l}(B_{i}) \cap \mathcal{P}_{l}(A_{i+1}) = \emptyset
\end{align*}
$$
:::right
（下标 $\bmod n$）
:::
:::right
$\square$
:::
::::
### 奇数情况
::::lemma 构造
设 $n = 2m+1$，记所有顶点为 $\{o\} \cup \{a_i\}, i=0, 1, \dots, n-1$，有构造
$$
\providecommand{\concat}{\mathop{\#}}
\providecommand{\bigconcat}{\mathop{\Large{\#}}\limits}
\bigconcat_{i=0}^{m-1} \left( {\color{red}{\bigconcat_{j=1}^{m} (a_{i-j}, a_{i+j-1})}} \right) \concat (a_i, o) \concat \left( {\color{blue}{\bigconcat_{j=1}^{m-1} (a_{i-j}, a_{i+j})}} \right) \concat (a_{i+m}, o)
$$
:::right
（下标 $\bmod n$）
:::
满足 $g = m-1 = \left\lceil\dfrac{n}{2}\right\rceil - 2$。
::::
::::proof
仍然记 $A_i = {\color{red}{\mathop{\Large{\#}}\limits_{j=1}^{m} (a_{i-j}, a_{i+j-1})}}, B_i = {\color{blue}{\mathop{\Large{\#}}\limits_{j=1}^{m-1} (a_{i-j}, a_{i+j})}}$。
由上可知相邻 $A, B$ 的长度和为 $m-1$ 的前后缀的点不重复，由于奇数构造中相邻的 $A, B$ 有一个间隔 $(a_x,o)$，所以 $A, B$ 内的比赛在 $m$ 场内没有重复的点。
于是只需证在中间插入的 $(a_x,o)$ 不会带来 $m$ 场内的重复点，即只需证
$$
\begin{align*}
a_i &\notin \mathcal{S_{m-1-l}}(A_i) \cup \mathcal{P_{l}}(B_{i}) \\
a_{i+m} &\notin \mathcal{S_{m-1-l}}(B_i) \cup \mathcal{P_{l}}(A_{i+1})
\end{align*}
$$
而由上
$$
\begin{align*}
\mathcal{S_{m-1-l}}(A_i) \cup \mathcal{P_{l}}(B_i) &= \{a_{i+l+1}, \dots, a_{i-l-1}\} \cup \{a_{i-l}, \dots, a_{i+l}\} \setminus \{a_i\} \notni a_i \\
\mathcal{S}_{m-1-l}(B_{i}) \cup \mathcal{P}_{l}(A_{i+1}) &= \{a_{i+l+1}, \dots, a_{i-l-1}\} \setminus \{a_{i+m}\} \cup \{a_{i-l+1}, \dots, a_{i+l}\} \notni a_{i+m} \\
\end{align*}
$$
:::right
$\square$
:::
::::
### 结论
根据以上构造，$g$ 能取到上界，即在 $n \ge 3$ 时，有
$$
\boxed{g = \left\lceil \frac{n}{2} \right\rceil - 2}
$$