Phantom Bird

外观

循环赛最大休息时间问题（草稿）

约 1671 字大约 6 分钟

maths

2025-11-22

问题引入

在比赛中，我们要确保运动员有充足的休息时间。基于这一背景，73Dsi 在 11 月 16 日发布了这一问题：

原始问题

n (n≥5)n\ (n \ge 5) 个人打循环赛，证明存在一种安排比赛顺序的方式，使得一个人不会连续打两场比赛。

这个问题是简单的。在此基础上，我们可以进行推广，继续探究能否将一个人打两场比赛的间隔提高。

问题

n (n≥3)n\ (n \ge 3) 个人打循环赛，每个人的最短比赛间隔的最大值 gg 是多少？

上界

我们将 pp 和 qq 的比赛记作 (p,q)(p,q)。

因为 n≥3n \ge 3，所以至少有 33 场比赛。

记前 (g+2)(g+2) 场比赛分别为 {(p1,p2),(q1,q2),…,(q2g−1,q2g),(r1,r2)}\{(p_1, p_2), (q_1, q_2), \dots, (q_{2g-1}, q_{2g}), (r_1, r_2)\}，由间隔为 gg 有：

  1. pi,qi,rip_i, q_i, r_i 分别各不相同；
  2. p1,p2,r1,r2∉{q1,q2,…,q2g}p_1, p_2, r_1, r_2 \notin \{ q_1, q_2, \dots, q_{2g} \}；
  3. (p1,p2)≠(r1,r2)(p_1, p_2) \ne (r_1, r_2)。

于是 n≥∣{p1,p2,q1,q2,…,q2g,r1,r2}∣≥2g+3n \ge \bigl|\{p_1, p_2, q_1, q_2, \dots, q_{2g}, r_1, r_2\}\bigr| \ge 2g+3，整理可得

g≤⌈n2⌉−2\boxed{ g \le \left\lceil\frac{n}{2}\right\rceil - 2 }

如果存在一种构造能达到 ⌈n2⌉−2\left\lceil\dfrac{n}{2}\right\rceil - 2 的间隔，就能证明 g=⌈n2⌉−2g = \left\lceil\dfrac{n}{2}\right\rceil - 2。

简单情况与拆分

为了避免一上来就写出一大坨形式化构造，我们先从直观的画图讲起。

把每个人画成一个点，用两个点的连线表示一场比赛，我们就能得到像下面一样的图：

图

然而这个图太复杂了，我们先来探究一些简单的图。

圈与链

圈与链是两种较简单的图。在圈和链上面，我们很容易达到 g=⌈n2⌉−2g = \left\lceil \dfrac{n}{2} \right\rceil - 2 的上界，只需要给各个比赛标号，然后先按标号从小到大取奇数标号的比赛，再按标号从小到大取偶数标号的比赛即可，如下图：

圈与环构造
（上图的数字是比赛的标号，不是比赛顺序）

Walecki 分解

于是我们有一种构造思路：将所有比赛拆成若干个圈/链，然后分别处理这些圈/链。而 Walecki 在百年前给出了如下图的巧妙构造：

Walecki 构造
（左图是对于偶数个点的图的构造，在它的基础上增加一个点，即有右图的奇数构造）

基于 Walecki 的构造，我们便得以拆分问题。

错位构造

在每个圈/链上解决问题还不够，我们还需要保证它们合起来之后不会出现新的冲突。而得益于 Walecki 构造的高度对称性，我们有如下的安排方式，恰好将相近的边错开：

最终构造

上图可以让我们直观地理解最终的构造。此处我们不用上图对其进行证明，形式化的构造和证明将在下面给出。

形式化构造及证明

接下来，我们就要进入复杂的形式化证明了。

为了方便地表示构造，约定序列拼接符号：

约定

{a1,a2,…,an}#{b1,b2,…,bm}={a1,a2,…,an,b1,b2,…,bm}\{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\}

#i=1nAi=A1#A2#⋯#An\mathop{\Large{\#}}\limits_{i=1}^{n} A_i = A_1 \mathop{\#} A_2 \mathop{\#} \cdots \mathop{\#} A_n

与其他序列拼接时，只有一项的序列可以省略大括号。

偶数情况

构造

设 n=2mn = 2m，记所有顶点为 ai,i=0,1,…,2m−1a_i, i=0, 1, \dots, 2m-1，有构造

#i=1m(#j=1m(ai−j,ai+j−1))#(#j=1m−1(ai−j,ai+j))\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)

（下标  mod 2m\bmod 2m）

满足 g=m−2=⌈n2⌉−2g = m-2 = \left\lceil\dfrac{n}{2}\right\rceil - 2。

证明

将构造分割为子串 Ai=#j=1m(ai−j,ai+j−1),Bi=#j=1m−1(ai−j,ai+j)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})}}，

因为 Ai,BiA_i, B_i 内部不重且长度均 ≥m−1\ge m-1，要证此构造在 (m−1)(m-1) 轮内的点（选手）不重复，只需证相邻子串长度和为 m−1m-1 的前后缀的点不重复。

记 Pl(Ai)\mathcal{P}_l(A_i) 为 AiA_i 的长度为 ll 的前缀包含的点，Sl(Ai)\mathcal{S}_l(A_i) 为 AiA_i 的长度为 ll 的后缀包含的点，类似地定义 Pl(Bi),Sl(Bi)\mathcal{P}_l(B_i), \mathcal{S}_l(B_i)，则

Pl(Ai)={ai−l,…,ai+l−1}Sl(Ai)={ai+m−l,…,ai+m+l−1}Pl(Bi)={ai−l,…,ai+l}∖{ai}Sl(Bi)={ai+m−l,…,ai+m+l}∖{ai+m}\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*}

（下标  mod 2m\bmod 2m）

于是

Sm−1−l(Ai)= {ai+l+1,…,ai−l−1}⟹ Sm−1−l(Ai)∩Pl(Bi)=∅Sm−1−l(Bi)= {ai+l+1,…,ai−l−1}∖{ai+m}Pl(Ai+1)= {ai−l+1,…,ai+l}⟹ Sm−1−l(Bi)∩Pl(Ai+1)=∅\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*}

（下标  mod 2m\bmod 2m）

□\square

奇数情况

构造

设 n=2m+1n = 2m+1，记所有顶点为 {o}∪{ai},i=0,1,…,2m−1\{o\} \cup \{a_i\}, i=0, 1, \dots, 2m-1，有构造

#i=0m−1(#j=1m(ai−j,ai+j−1))#(ai,o)#(#j=1m−1(ai−j,ai+j))#(ai+m,o)\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)

（下标  mod 2m\bmod 2m）

满足 g=m−1=⌈n2⌉−2g = m-1 = \left\lceil\dfrac{n}{2}\right\rceil - 2。

证明

仍然记 Ai=#j=1m(ai−j,ai+j−1),Bi=#j=1m−1(ai−j,ai+j)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,BA, B 的长度和为 m−1m-1 的前后缀的点不重复，由于奇数构造中相邻的 A,BA, B 有一个间隔 (ax,o)(a_x,o)，所以 A,BA, B 内的比赛在 mm 场内没有重复的点。

于是只需证在中间插入的 (ax,o)(a_x,o) 不会带来 mm 场内的重复点，即只需证

ai∉Sm−1−l(Ai)∪Pl(Bi)ai+m∉Sm−1−l(Bi)∪Pl(Ai+1)\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*}

而由上

Sm−1−l(Ai)∪Pl(Bi)={ai+l+1,…,ai−l−1}∪{ai−l,…,ai+l}∖{ai}∌aiSm−1−l(Bi)∪Pl(Ai+1)={ai+l+1,…,ai−l−1}∖{ai+m}∪{ai−l+1,…,ai+l}∌ai+m\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*}

□\square

结论

根据以上构造，gg 能取到上界，即在 n≥3n \ge 3 时，有

g=⌈n2⌉−2\boxed{g = \left\lceil \frac{n}{2} \right\rceil - 2}

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)