problemset

C1. 在由 $100$ 个点构成的点集

$$D = \{(a, b) \mid a = 1, 2, \dots, 10, b = 1, 2, \dots, 10\}$$

中，选择若干个点染成红色。 要求点集 $D$ 中的每个点不能与两个（或更多个）红色点的距离为 $\sqrt{5}$。 求点集 $D$ 中的红色点的个数的最大可能值。

注：将 $10$ 改为一般的 $n$，答案量级为 $\dfrac18n^2+O(n)$，构造可以仿照解答中的构造，证明可以去统计每个红格与普通格形成的马步。

C2. 设 $G$ 是一个 $n(n\ge6)$ 阶简单无向图。求同构于一条边并两个孤立点的 $4$ 阶诱导子图个数的最大值。

C3. 给定正整数 $m\ge2$。简单无向正则二部图 $G=(A,B,E)$ 满足：

1. $|A|=|B|=\dbinom{m}{2}+1$；
2. $A$ 中的点度数均为 $m$；
3. 任意两个 $B$ 中不同点 $u,v$，$u,v$ 在 $A$ 中恰有两个公共邻居。

证明 $G$ 有长（边数）为 $2\lfloor\frac{(m+1)^2}{4}\rfloor-1$ 的路径。

C4. 求最小的正整数 $n_0$，使得对任意 $n\ge n_0$ 阶简单无向图 $G$，若补图 $\overline{G}$ 无 $K_{3,3}$ 子图（不一定是诱导子图），则 $G$ 中有长（边数）为 $n-3$ 的路径。

C5. 给定正整数 $n\ge2$，是否存在 $\Z^+$ 的 $n$ 个两两不交的子集 $A_1,\cdots,A_n$，满足对任意无限（正）素数集 $P$，存在正整数 $m$ 和 $n$ 个元素 $a_1\in A_1,\cdots,a_n\in A_n$，使得 $a_1,\cdots,a_n$ 都可以表示为 $P$ 中的 $m$ 的不同素数的乘积。

C6. 在半径为 $1$ 的圆盘内部（不含边界）有 $n$ 个不同点 $P_1,P_2,\cdots,P_n$，满足折线长 $\sum\limits_{k=1}^{n-1}|P_kP_{k+1}|=90$。证明折线外角和 $\sum\limits_{k=2}^{n-1}(\pi-\angle P_{k-1}P_kP_{k+1})>14\times2\pi$。这里 $\angle P_{k-1}P_kP_{k+1}\in[0,\pi]$ 且共线时可以取到 $0$ 或 $\pi$。

C7. 求所有非负实数 $\lambda$，使得存在正整数 $n$ 与 $3n$ 个两两不同的实数 $a_i^{(t)}(i=1,2,\cdots,n;t=1,2,3)$ 满足 $\forall t=1,2,3:|\{(i,j)\in\{1,2,\cdots,n\}^2:a_i^{(t)}>a_j^{(t+1)}\}|\ge\lambda n^2$，其中 $t$ 处的上标 $\bmod3$ 理解。 若将 $3$ 推广到一般的 $d\in\Z^+,d\ge2$，$\lambda_d$ 的范围是？

C1

解答

1. 等价转化与染色

将点集 $D$ 视为 $10 \times 10$ 的方格表。两点距离为 $\sqrt{5}$ 等价于它们在方格表上可以通过“马步”走到（即坐标差为 $(\pm 1, \pm 2)$ 或 $(\pm 2, \pm 1)$）。 题目条件“每个点不能与两个或更多红色点的距离为 $\sqrt{5}$”等价于：任意两个红点不能拥有公共的“马步邻居”（即不存在一个点 $P$，使得它到两个红点的距离都为 $\sqrt{5}$）。

将方格表按 $x+y$ 的奇偶性进行黑白交替染色（$x+y$ 为偶数的点染黑，为奇数的点染白）。 由于马步必然改变 $x+y$ 的奇偶性，所以黑点的马步邻居必然为白点，反之亦然。 因此，黑点中的红点与白点中的红点互不影响，我们可以分别计算黑格红点和白格红点的最大数量，然后相加。由对称性，黑格与白格的最大值相同。

2. 证明黑格红点最多 8 个

我们只需证明在 $10 \times 10$ 的黑格中，最多能选出 $8$ 个互不共享马步邻居的红点。 将 $10 \times 10$ 分为上下两个 $5 \times 10$ 的区域。由于上下对称，只需证明上方 $5 \times 10$ 中最多有 $4$ 个黑格红点。

将上方 $5 \times 10$ 区域分为左、右两个 $5 \times 5$ 的子区域。

• 左侧 $5 \times 5$ 最多 3 个红点：左侧 $5 \times 5$ 中共有 $13$ 个黑格。通过分类讨论或坐标枚举可知，若在此区域放置 $4$ 个红点，由于边界限制，必然会导致其中两个红点共享一个马步邻居（白格），从而违反条件。因此左侧最多放置 $3$ 个红点。并且，当左侧恰好放置 $3$ 个红点时，其构型是唯一的（在对称意义下），即必须沿对角线分布，例如取 $(1,1), (3,3), (5,5)$。
• 右侧 $5 \times 5$ 最多 2 个红点：右侧 $5 \times 5$ 共有 $12$ 个黑格，显然最多放置 $2$ 个红点。
• 不可能达到 $3+2=5$ 个：假设上方 $5 \times 10$ 有 $5$ 个红点，则必然是左侧 $3$ 个、右侧 $2$ 个。根据唯一构型，左侧的 $3$ 个红点为 $(1,1), (3,3), (5,5)$。此时，它们的马步邻居已经占用了右侧的一些关键白格（如 $(6,3), (7,4)$ 等）。若右侧还要放置 $2$ 个红点，它们需要至少 $4$ 个互不重叠且未被占用的白格邻居，但在边界限制下，右侧 $5 \times 5$ 中无法找到这样的 $2$ 个点。因此上方最多 $4$ 个红点。

同理，下方 $5 \times 10$ 区域也最多 $4$ 个红点。 所以，整个 $10 \times 10$ 黑格中最多有 $4+4=8$ 个红点。 白格同理，最多也有 $8$ 个红点。 因此，红点总数最多为 $8 + 8 = 16$ 个。

3. 构造 16 个红点

下面给出一个包含 $16$ 个红点的合法构造。

黑格部分取

$$B=\{(x,y)\in D: x+y=2,10,\ 2\nmid x,y \text{ 或 } x+y=18,\ 2\mid x,y\}.$$

具体地，$B$ 中的点为

$$(1,1);\ (1,9),(3,7),(5,5),(7,3),(9,1);\ (8,10),(10,8),$$

共 $1+5+2=8$ 个黑格点。

白格部分取 $B$ 关于水平中线 $y=5.5$ 的对称

$$W=\{(x,11-y)\in D:(x,y)\in B\}.$$

具体地，$W$ 中的点为

$$(1,10),(1,2),(3,4),(5,6),(7,8),(9,10),(8,1),(10,3),$$

共 $8$ 个白格点。

容易验证，$B$ 中任意两个点的马步邻居集合互不相交，$W$ 中任意两个点的马步邻居集合也互不相交；且由于黑白格马步邻居分属异色，$B$ 与 $W$ 之间也不会共享马步邻居。因此这 $16$ 个红点满足题目条件。

综上所述，红点个数的最大可能值为 $\boxed{16}$。

检查

• 题意理解：正确理解了“每个点不能与两个或更多红点距离为 $\sqrt{5}$”等价于“红点之间不能有公共的马步邻居”。
• 推理过程：黑白染色解耦正确；利用抽屉原理和极端情况分析（左侧 $3$ 个时构型唯一，导致右侧无法放置 $2$ 个）证明上界为 $8$ 的逻辑严谨；构造的 $16$ 个点经过坐标验证无冲突。
• 计算与符号：新构造 $B$ 与 $W$ 分别恰有 $8$ 个点，总数 $16$；$B$ 中条件“$2\nmid x,y$”表示 $x,y$ 均为奇数，“$2\mid x,y$”表示 $x,y$ 均为偶数，与 $x+y$ 的奇偶性一致，故 $B$ 全为黑格，$W$ 全为白格。
• 边界情况：在 $5 \times 5$ 区域的讨论中，考虑了边界对马步邻居数量的限制，未出现跳步。构造中的对称映射 $y \mapsto 11-y$ 在 $D$ 内封闭，无越界点。
• 最终结论：完整回答了题目，最大值为 $16$。

核心思路总结

本题最关键、最具创造性的步骤有两点：

1. 等价转化与黑白染色：将距离条件转化为“无公共马步邻居”，并通过 $x+y$ 的奇偶性将问题拆解为两个独立的子问题，大大降低了问题的复杂度。
2. 局部上界与极端情况分析：通过将 $10 \times 10$ 划分为 $5 \times 10$ 甚至 $5 \times 5$ 的小区域，利用“抽屉原理”和“唯一构型”分析，证明了单色点最多为 $8$ 个。这种方法避免了复杂的全局图论计算，非常适合竞赛数学的书写。

参考资料

无

C2

解答

记 $H=K_2\sqcup K_1\sqcup K_1$，并记 $h(G)$ 为图 $G$ 中诱导出 $H$ 的四元顶点集个数。每个四元集只计一次。

先给出最大值的显式公式。设图的阶数为 $n\ge6$。对于 $k\in\{3,4,5\}$，定义

$$q_k=\left\lfloor\frac nk\right\rfloor,\qquad r_k=n-kq_k,\qquad Q_k=(k-r_k)q_k^2+r_k(q_k+1)^2,$$

以及

$$\begin{aligned} F_k(n)=\frac14\Bigl[& (k-r_k)q_k(q_k-1) \bigl((n-q_k)^2-Q_k+q_k^2\bigr)\\ &+r_kq_k(q_k+1) \bigl((n-q_k-1)^2-Q_k+(q_k+1)^2\bigr) \Bigr]. \end{aligned}$$

则所求最大值为

$$\boxed{\max\{F_3(n),F_4(n),F_5(n)\}}.$$

这是只需比较三个显式数的精确公式。对于取得最大值的 $k$，取 $k-r_k$ 个 $q_k$ 阶完全图和 $r_k$ 个 $(q_k+1)$ 阶完全图的不交并，即可达到最大值。例如，$n=6$ 时三个候选值依次为 $12,10,6$，答案为 $12$。

下面证明公式。

一、可以取一个由若干完全图不交并而成的极值图。

对顶点 $v$，记其闭邻域为

$$N[v]=\{v\}\cup\{u:uv\in E(G)\}.$$

按闭邻域相同将顶点分成等价类。每个等价类内部是完全图，任意两个等价类之间要么没有边，要么所有可能的边都存在。

在所有使 $h(G)$ 最大的图中，取等价类数目最少的一个。假设其中两个不同的等价类 $A,B$ 之间有边。于是 $A\cup B$ 是完全图。设

$$|A|=a,\quad |B|=b,\quad s=a+b,\quad W=V(G)\setminus(A\cup B).$$

固定 $G[W]$。记 $U_A,U_B\subseteq W$ 分别为 $A,B$ 中顶点在 $W$ 内的非邻点集合。对 $U\subseteq W$，用 $I(U)$ 表示 $G[U]$ 中无边顶点对的个数。令

$$\alpha=I(U_A),\qquad \beta=I(U_B),\qquad \gamma=I(U_A\cap U_B).$$

现在允许改变两类的大小，保持总大小 $s$，并保持两种顶点与 $W$ 的连接方式。类内及两类之间仍全部连边，类的大小可以为零。

因为 $A\cup B$ 是完全图，一个被计数的四元集在其中至多选两个顶点。恰选一个顶点的贡献关于两类大小是线性的；恰选两个顶点时，这两个点必须构成唯一的边。因此，两类大小为 $x,s-x$ 时，计数具有如下形式：

$$f(x)=C+xL_A+(s-x)L_B +\binom{x}{2}\alpha+\binom{s-x}{2}\beta +x(s-x)\gamma,$$

其中 $C,L_A,L_B$ 不随 $x$ 改变。

由于 $U_A\cap U_B$ 是 $U_A,U_B$ 的子集，

$$\gamma\le\alpha,\qquad \gamma\le\beta.$$

所以 $f(x)$ 的二次项系数满足

$$\frac{\alpha+\beta}{2}-\gamma\ge0.$$

从而

$$f(a)\le\frac{s-a}{s}f(0)+\frac as f(s) \le\max\{f(0),f(s)\}.$$

也就是说，把 $A\cup B$ 的全部顶点改成同一种连接方式，至少有一种选择不会使计数减少。

这样的操作把 $A,B$ 合成一个等价类；原来其余的每个等价类也不会被拆开，因为其中的顶点与 $A,B$ 的连接方式分别相同。因此，所得图仍为极值图，但等价类数目更少，矛盾。

所以不同等价类之间没有边，所取极值图确为若干完全图的不交并。

二、在这样的极值图中，可以使各完全图的阶数至多相差一。

若各完全图阶数为 $a_1,\ldots,a_k$，则

$$\sum_{i=1}^k a_i=n,$$

且计数为

$$T(a_1,\ldots,a_k) =\sum_{i=1}^k\binom{a_i}{2} \sum_{\substack{j<\ell\\j,\ell\ne i}}a_ja_\ell. \tag{1}$$

这是因为唯一的边来自一个完全图，而两个孤立点必须分别来自另外两个不同的完全图。

在达到全局最大值的完全图不交并中，选取完全图个数 $k$ 最少的一个。任选两部分，设其阶数为 $a,b$，其余部分的阶数为 $c_1,\ldots,c_{k-2}$，并记

$$s=a+b,\qquad t=\sum_{i=1}^{k-2}c_i,\qquad Q=\sum_{i=1}^{k-2}c_i^2.$$

固定其余各部分以及 $s$。设

$$E=\sum_{i<j}c_ic_j=\frac{t^2-Q}{2},\qquad B=\sum_i\binom{c_i}{2}=\frac{Q-t}{2}.$$

公式 $(1)$ 中随 $a,b$ 的分配而改变的项恰为

$$\left(\binom a2+\binom b2\right)E +\left(\binom a2b+\binom b2a\right)t+abB.$$

利用

$$\binom a2+\binom b2=\binom s2-ab,\qquad \binom a2b+\binom b2a=\frac{ab(s-2)}2,$$

可将总计数写为

$$T=C+abD,\qquad D=\frac{2Q-t^2+t(s-3)}2, \tag{2}$$

其中 $C,D$ 都不随 $a,b$ 在固定和 $s$ 下的分配而改变。这里 $C$ 也正是把两部分合并成一个 $s$ 阶完全图后的计数。

若 $D\le0$，将这两部分合并，使 $ab$ 变为零，计数不会减少，而部分数减少。这与 $k$ 的最小性矛盾。因此，每两部分都满足 $D>0$。

若 $a\ge b+2$，将它们改为 $a-1,b+1$，则乘积增加

$$(a-1)(b+1)-ab=a-b-1>0.$$

由 $(2)$，计数严格增加，矛盾。因此所有部分的阶数至多相差一。

三、只需考虑三个、四个或五个完全图。

只有一个或两个完全图时，公式 $(1)$ 的值为零；而 $n\ge6$ 时，三个阶数至少为 $2$ 的完全图的不交并给出正的计数。因此 $k\ge3$。

下面排除 $k\ge6$。由第二步，所有阶数都为 $q$ 或 $q+1$，其中

$$q=\left\lfloor\frac nk\right\rfloor\ge1.$$

选取最小的两个部分，其阶数和 $s$ 满足 $s\le2q+1$。其余部分满足

$$t\ge(k-2)q,\qquad Q\le(q+1)t.$$

代入 $(2)$，得到

$$\begin{aligned} 2D &=2Q-t^2+t(s-3)\\ &\le2(q+1)t-t^2+t(2q-2)\\ &=t(4q-t)\\ &\le(6-k)qt\le0. \end{aligned}$$

这与第二步所得 $D>0$ 矛盾。故

$$k\in\{3,4,5\}.$$

四、计算三个候选并达到上界。

对于固定的候选 $k$，各部分阶数为 $q_k$ 或 $q_k+1$，分别出现 $k-r_k$ 次和 $r_k$ 次，阶数平方和为 $Q_k$。对于阶数为 $a$ 的那一部分，其余各部分中选两个不同部分、各取一个顶点的方式数为

$$\sum_{\substack{j<\ell\\j,\ell\ne i}}a_ja_\ell =\frac{(n-a)^2-(Q_k-a^2)}2.$$

将 $a=q_k$ 和 $a=q_k+1$ 分别代入 $(1)$，即得开头定义的 $F_k(n)$。

前三步保证至少有一个极值图属于这三个候选；另一方面，三个候选图都确实存在，且分别取得计数 $F_3(n),F_4(n),F_5(n)$。所以它们的最大值就是所求最大值。

检查

• 计数口径： 计数对象是四元顶点集。唯一的边确定其所属完全图，另外两点所在的部分按无序对选择，故公式 $(1)$ 没有重复计数，也没有把含额外边的四元集计入。
• 图的变换： 第一部分按四元集与 $A\cup B$ 的交集大小完整分类；交集大小至少为三时含三角形，确实不贡献计数。二次项非负保证可取端点；原等价类不会被拆分，故最少类数的论证成立。
• 配平与合并： 公式 $(2)$ 同时适用于正的两部分和合并后的零大小部分。先由最少部分数推出 $D>0$，再配平，未预先假定配平一定有利。
• 边界： $n\ge6$ 保证三个候选的部分阶数均为正；最小情形 $n=6$ 得到 $12$，由 $3K_2$ 达到。排除 $k\ge6$ 时只用了 $q\ge1$，涵盖了含单点部分的情形。
• 独立交叉核查： 用直接计数穷举了六阶的全部 $32768$ 个带标号简单图，最大值为 $12$；对从 $6$ 到 $30$ 的所有整数阶，枚举全部整数分拆所得的最大值均与最终公式一致。另外对 $256$ 组参数核验了合并前后的计数差恒等式。上述计算仅作核查，任意阶数的结论由正文证明。
• 结论与取等： 最终公式只涉及三个由 $n$ 显式确定的数；选取对应的平衡完全图不交并即可达到最大值，因而同时给出了普遍上界和取等构造。

核心思路总结

最关键的一步是利用闭邻域等价类之间的凸性变换，将任意极值图化为完全图的不交并。随后，固定两部分阶数之和，计数对其乘积呈线性关系；“部分数最少”排除了非正系数，从而同时推出各部分必须平衡，并排除六个及更多部分。这样，无须搜索一般图或所有整数分拆，只需计算三个明确的候选。

核心工具是诱导子图的分类计数、二次函数凸性及保持总和的配平变换。正文已证明所需的变换性质，未引用外部极值图定理。

参考资料

无。

C3

解答

以下只假设 $A$ 中每个顶点的度数为 $m$，不预先假设 $B$ 中顶点的度数。其余条件保持不变。

记

$$v=\binom m2+1,\qquad s=\left\lfloor\frac{m+1}{2}\right\rfloor,\qquad L=\left\lfloor\frac{(m+1)^2}{4}\right\rfloor.$$

我们将证明存在至少含 $2L$ 个顶点的简单路径，再截取其中连续的 $2L$ 个顶点，即得到边数恰为 $2L-1$ 的路径。

一、由单侧度数条件推出全图正则。

记 $N(x)$ 为顶点 $x$ 的邻居集合。固定任意 $b\in B$，对集合

$$\mathcal T_b=\{(a,b'):a\in N(b),\ b'\in B\setminus\{b\},\ ab'\in E\}$$

作两次计数。

先选 $a\in N(b)$。由于 $a\in A$ 的度数为 $m$，它除 $b$ 外还有 $m-1$ 个邻居，因此

$$|\mathcal T_b|=\deg(b)(m-1).$$

先选 $b'\in B\setminus\{b\}$。根据公共邻居条件，$b,b'$ 恰有两个公共邻居可作为 $a$，因此

$$|\mathcal T_b|=2(|B|-1)=2\binom m2=m(m-1).$$

比较两式，并利用 $m\ge2$，得到

$$\deg(b)=m.$$

由于 $b$ 任意，$B$ 中所有顶点的度数也都为 $m$，所以 $G$ 必为 $m$ 正则二部图。这说明在其余条件下，单侧度数条件已经蕴含原来的全图正则性。

二、证明公共邻居条件在两侧都成立。

题设已给出任意两个不同的 $B$ 中顶点恰有两个公共邻居。下面证明 $A$ 侧也有同样的性质。

固定 $a\in A$，对每个 $x\in A\setminus\{a\}$，记

$$r_x=|N(x)\cap N(a)|,$$

$N(a)$ 含有 $m$ 个顶点，每个顶点除 $a$ 外还有 $m-1$ 个邻居，因此

$$\sum_{x\in A\setminus\{a\}}r_x=m(m-1)=2(v-1).$$

另一方面，$N(a)$ 中任意两个不同顶点都是 $B$ 中的顶点，恰有两个公共邻居。其中一个为 $a$，另一个在 $A\setminus\{a\}$ 中。因此，对 $N(a)$ 中的无序顶点对计数，得到

$$\sum_{x\in A\setminus\{a\}}\binom{r_x}{2} =\binom m2=v-1.$$

从而

$$\begin{aligned} \sum_{x\in A\setminus\{a\}}(r_x-2)^2 &=2\sum_x\binom{r_x}{2}-3\sum_xr_x+4(v-1)\\ &=2(v-1)-6(v-1)+4(v-1)=0. \end{aligned}$$

每一项都是非负数，所以所有 $r_x$ 均为 $2$。由于 $a$ 任意，任意两个不同的 $A$ 中顶点也恰有两个公共邻居。

由此，若 $T$ 是同一侧的 $s$ 个不同顶点组成的集合，则

$$\begin{aligned} |N(T)| &\ge sm-2\binom s2\\ &=s(m+1-s)=L. \tag{1} \end{aligned}$$

这里 $N(T)=\bigcup_{x\in T}N(x)$。为说明不等式，依次加入这 $s$ 个顶点的邻居集合：加入第 $j$ 个集合时，它与此前每个集合恰有两个公共元素，故与此前各集合之并的交集至多有 $2(j-1)$ 个元素，新增加的元素至少为 $m-2(j-1)$。求和即得式 $(1)$。最后的等式使用了 $s=\lfloor(m+1)/2\rfloor$。

三、通过最长路径的旋转寻找足够大的邻域。

取 $G$ 中一条顶点数最多的简单路径

$$P=v_1v_2\cdots v_k.$$

前两部分表明两侧的度数条件与公共邻居条件均对称，所以必要时交换 $A,B$ 的名称，可设 $v_1\in A$。

由路径的最长性，端点 $v_1$ 的全部 $m$ 个邻居都在 $P$ 上：若有路径外的邻居，将其接在 $v_1$ 前便可延长路径。

对于每个满足 $v_1v_i\in E$ 的下标 $i$，都有 $i\ge2$，并且

$$P_i=v_{i-1}v_{i-2}\cdots v_1v_iv_{i+1}\cdots v_k$$

是一条简单路径。当 $i=2$ 时，前一段只有顶点 $v_1$；当 $i=k$ 时，后一段只有顶点 $v_k$。这条路径先逆向经过原路径的前 $i-1$ 个顶点，再沿边 $v_1v_i$ 接上其余顶点，因此恰好经过 $P$ 的全部顶点而无重复，也是最长路径。

于是，$P_i$ 的端点 $v_{i-1}$ 的全部邻居也都在 $V(P)$ 中，否则可以把 $P_i$ 延长。

由于图是二部图且 $v_1\in A$，所有邻居 $v_i$ 都在 $B$ 中，其前驱 $v_{i-1}$ 均在 $A$ 中。$v_1$ 有 $m$ 个不同邻居，而不同下标有不同前驱，所以

$$R=\{v_{i-1}:v_1v_i\in E\}$$

是 $A$ 中含有 $m$ 个不同顶点的集合，并且

$$N(R)\subseteq V(P)\cap B.$$

因为 $s\le m$，可以在 $R$ 中任取 $s$ 个顶点组成 $T$。由式 $(1)$，

$$|V(P)\cap B|\ge |N(T)|\ge L.$$

路径 $P$ 从 $A$ 侧开始，沿途两侧顶点交替出现，因此其 $A$ 侧顶点数不少于 $B$ 侧顶点数。故

$$k=|V(P)\cap A|+|V(P)\cap B|\ge2L.$$

取 $P$ 上连续的 $2L$ 个顶点，便得到一条恰有

$$\boxed{2\left\lfloor\frac{(m+1)^2}{4}\right\rfloor-1}$$

条边的简单路径，完成证明。

检查

• 目标口径： 最新题目要求路径有恰好 $2L$ 个顶点，即恰好 $2L-1$ 条边。正文先得到至少 $2L$ 个顶点，再截取连续的一段，已保证确切数量。
• 弱化条件： 第一部分只使用 $A$ 侧度数为 $m$、$|B|=\binom m2+1$ 及 $B$ 侧公共邻居条件，逐点推出 $\deg(b)=m$；没有先行使用全图正则性。
• 新增计数： $\mathcal T_b$ 中每个元素对应一条从固定顶点 $b$ 出发、经 $a$ 到另一顶点 $b'$ 的两边路径。按中间顶点计数得到 $\deg(b)(m-1)$，按末端顶点计数得到 $2(|B|-1)$。$m\ge2$ 保证约去 $m-1$ 合法。
• 其余条件使用： 推导出 $m$ 正则性后，才将其用于公共邻居计数、邻居集合大小及端点邻居数；$|A|=v$ 用于平方和中的项数。交换两侧之前，已证明 $A$ 侧具有同样的公共邻居性质。
• 计数核验： 对 $N(a)$ 中每一对顶点，除 $a$ 外恰有一个公共邻居，所以它在 $\sum_x\binom{r_x}{2}$ 中恰好被计一次。恒等式 $(r-2)^2=2\binom r2-3r+4$ 的各项系数正确。
• 邻域下界： 估计与此前集合之并的交集时使用上界 $2(j-1)$；即使多个交集重合，上界仍成立，因此不需要假设三个或更多顶点没有公共邻居。
• 路径旋转： 每条旋转后的路径保持原顶点集合不变，只反向遍历前段并使用已有边 $v_1v_i$ 连接后段。所有得到的端点都属于同一侧，且各自没有原路径之外的邻居。$i=2$ 和 $i=k$ 的情形也合法。
• 参数边界： 若 $m=2r$，则 $s=r$、$s(m+1-s)=r(r+1)=L$；若 $m=2r+1$，则 $s=r+1$、$s(m+1-s)=(r+1)^2=L$。特别地，$m=2$ 时 $G=K_{2,2}$，目标为四个顶点、三条边的路径，正文论证同样适用。
• 图的整体结构： 证明没有额外假设图连通，也没有把路径延伸误作闭合成圈；所有使用最长性的步骤都只涉及简单路径。

独立复核后，单侧度数条件确实推出全图正则性，后续公共邻居对称性、路径旋转、邻域估计及最终顶点数的推理也均成立。因此弱化后的条件仍足以保证所求路径存在。

核心思路总结

新增的关键是固定 $B$ 中一个顶点，对从它出发的两边路径作双重计数。$A$ 侧的固定度数与 $B$ 侧的固定公共邻居数共同迫使该顶点的度数也为 $m$，从而恢复全图正则性。

随后把一条最长路径的单个端点扩展成一批可作为最长路径端点的顶点：沿原端点的每一条邻边作一次路径旋转，就得到同一侧的 $m$ 个不同端点，它们的全部邻居都被限制在原路径内。

再利用任意两个同侧顶点恰有两个公共邻居，选出约一半的端点，得到邻域下界 $s(m+1-s)$。这个二次式的最大整数值恰为题目中的 $L$。公共邻居条件在两侧的对称性，则由两次计数及平方和为零得到。

核心工具是双重计数、非负平方和、集合并的计数下界、最长路径旋转，以及二部图路径的交替性。

参考资料

无。

C4

解答

所求阈值为 $n_0=7$。本节证明结论对所有 $n\ge7$ 成立；阈值的最小性在“检查”中核验。

补图不含普通子图 $K_{3,3}$，等价于以下性质：

任意两个互不相交的三元顶点集之间，在 $G$ 中至少有一条边。

下文称此为性质 $(*)$。各三元集内部是否有边不影响这一等价关系。

先注意：当 $n\ge7$ 时，不能有三个度数为 $1$、且邻居相同的顶点。否则取这三个顶点为一组，除去它们和共同邻居后还剩至少三个顶点，任选三个为另一组，两组之间没有边，违反 $(*)$。

一、存在至少含四个顶点的路径。

假设不存在这样的路径。如果连含三个顶点的路径也不存在，则每个连通分支至多有两个顶点：一个含至少三个顶点的连通分支必有度数至少为 $2$ 的顶点，从而含三个顶点的路径。依次取若干整个连通分支，直到其顶点总数首次达到 $3$，则共取了 $3$ 或 $4$ 个顶点，余下至少三个顶点。在已取和未取的顶点中各选三个，就违反 $(*)$。

因此可取三个顶点的最长路径 $x-a-y$。由最长性，$x,y$ 均不与路径外的顶点相邻。若 $a$ 也没有路径外的邻居，则这三个顶点与路径外任意三个顶点违反 $(*)$。

故 $a$ 有路径外的邻居 $u$。边 $xy$ 不能存在，否则 $u-a-x-y$ 是四个顶点的路径。顶点 $u$ 不能有另一邻居 $v$：$v=x,y$ 已由端点的最长性排除；若 $v$ 在路径外，则 $x-a-u-v$ 又是四个顶点的路径。因此 $x,y,u$ 都是仅与 $a$ 相邻的度数为 $1$ 的顶点，与前述观察矛盾。

二、若最长路径漏掉至少三个顶点，则其两端的度数均为一。

取一条最长路径

$$P=v_1v_2\cdots v_k,\qquad k\ge4.$$

反设 $k\le n-3$，记

$$U=V(G)\setminus V(P),\qquad |U|\ge3.$$

由最长性，$v_1,v_k$ 均没有 $U$ 中的邻居。

若有边 $v_1v_i$，其中 $3\le i\le k$，则

$$v_{i-1}v_{i-2}\cdots v_1v_iv_{i+1}\cdots v_k$$

也是一条包含 $V(P)$ 中全部顶点的最长路径。因此它的端点 $v_{i-1}$ 也没有 $U$ 中的邻居。三个不同顶点 $v_1,v_k,v_{i-1}$ 与 $U$ 中任意三个顶点之间均无边，违反 $(*)$。

所以 $v_1$ 只能与 $v_2$ 相邻。将路径次序反转，同理可知 $v_k$ 只能与 $v_{k-1}$ 相邻。这一论证适用于任意最长路径。

令

$$x=v_1,\quad a=v_2,\quad b=v_{k-1},\quad y=v_k.$$

由 $k\ge4$，这四个顶点互不相同。性质 $(*)$ 应用于 $\{x,y,a\}$ 和 $U$ 中任意三个顶点，说明 $a$ 在 $U$ 中有邻居 $u$。于是

$$u,v_2,v_3,\ldots,v_k$$

也是最长路径。由刚才的结论，$u$ 的度数为 $1$，唯一邻居为 $a$。

因此，三个顶点 $x,u,y$ 的全部邻居都属于 $\{a,b\}$。如果 $n\ge8$，除去 $x,u,y,a,b$ 后还有至少三个顶点，它们与 $\{x,u,y\}$ 违反 $(*)$。

三、处理剩下的临界情形。

只需考虑 $n=7$。此时 $4\le k\le n-3=4$，所以最长路径恰为

$$x-a-b-y.$$

性质 $(*)$ 应用于 $\{x,y,b\}$ 和 $U$，说明 $b$ 也有 $U$ 中的邻居 $w$。以 $w$ 替换路径端点 $y$，再次由第二步知，$w$ 的唯一邻居是 $b$。由于 $u$ 的唯一邻居是 $a$，故 $w\ne u$。

记最后一个顶点为 $t$。四个顶点 $x,u,y,w$ 的度数均为 $1$，所以 $t$ 只能与 $a,b$ 相邻。它不能同时与二者相邻，否则 $x-a-t-b-y$ 是五个顶点的路径，违背最长性。余下三种情况分别如下：

• 若 $t$ 只与 $a$ 相邻，则 $\{x,u,t\}$ 与 $\{b,y,w\}$ 之间没有边。
• 若 $t$ 只与 $b$ 相邻，则 $\{y,w,t\}$ 与 $\{a,x,u\}$ 之间没有边。
• 若 $t$ 为孤立点，则 $\{a,x,u\}$ 与 $\{y,w,t\}$ 之间没有边。

每种情况都违反 $(*)$，矛盾。

因此，反设 $k\le n-3$ 不成立，最长路径至少有 $n-2$ 个顶点。取其中连续的 $n-2$ 个顶点，便得到恰有 $n-3$ 条边的路径。结论对所有 $n\ge7$ 成立。

检查

阈值的最小性。 在 $n_0-1=6$ 阶时，取星图 $G=K_{1,5}$，中心为 $c$，叶顶点为 $v_1,\ldots,v_5$。其补图为

$$\overline G=K_5\sqcup K_1.$$

孤立点不能属于 $K_{3,3}$ 子图，剩余顶点又只有五个，因此补图不含普通子图 $K_{3,3}$。另一方面，星图中只有中心可以作为简单路径的内部顶点，最长路径恰有两条边，小于要求的 $6-3=3$ 条边。因此任何不超过 $6$ 的正整数阈值都不成立。结合正文，最小阈值确为 $7$。

条件与推理核验。

• 性质 $(*)$ 只限制两组三元集之间的边，不限制各组内部的边，准确使用了“子图不一定是诱导子图”的条件。
• 第一部分排除了最长路径顶点数不足四的所有情形，且没有假设图连通。
• 第二部分的路径旋转保留原路径的全部顶点；三个端点彼此不同，并均不与同一个集合 $U$ 相邻。替换端点所得路径也达到全图的最大顶点数，故可以再次应用已证结论。
• 当 $n\ge8$ 时，去掉五个不同顶点后至少剩三个；当 $n=7$ 时，单独列尽最后一个顶点的全部可能邻接关系，没有遗漏临界情形。
• 全文以不同顶点组成的简单路径为准，最终由至少 $n-2$ 个顶点截取恰好 $n-2$ 个连续顶点，得到的是恰好 $n-3$ 条边。

程序交叉检查。 穷举了七个标号顶点上的全部 $2^{21}=2097152$ 个简单无向图。其中不含五个顶点路径的图有 $20056$ 个，逐一检查发现其补图均含普通子图 $K_{3,3}$。另行核验了六阶星图的补图条件及最长路径长度。穷举仅用于核查边界，正文对任意 $n\ge7$ 的证明不依赖计算。

独立复核以上各步后，证明及阈值最小性的论证均成立。

核心思路总结

关键是把补图条件转化为“不存在两组互不相交且彼此无边的三元顶点集”。若最长路径外至少有三个顶点，一次路径旋转就会产生第三个不与路径外顶点相邻的端点；因此最长路径两端只能是度数为 $1$ 的顶点。再替换端点，得到额外的度数为 $1$ 的顶点，其邻居集中在两个顶点上，由此处理较大阶数。最后单独排除七阶的有限邻接情形。

核心工具是最长路径的不可延长性、路径旋转、端点替换和顶点计数。

参考资料

无。

C5

解答

存在。 下面对任意给定的正整数 $n\ge2$ 构造满足要求的集合，且这些集合实际上构成正整数集的一个划分。

对正整数 $a$，记 $\omega(a)$ 为其不同素因子的个数，其中 $\omega(1)=0$。定义

$$f(a)=\bigl|\{p:p\text{ 为素数},\ p\mid a,\ p\le\omega(a)\}\bigr|.$$

也就是说，$f(a)$ 只统计不超过 $\omega(a)$ 的那些不同素因子。令

$$A_i=\{a\in\mathbb Z^+:f(a)\equiv i-1\pmod n\}, \qquad 1\le i\le n.$$

一个整数模 $n$ 的余数唯一，所以这些集合两两不交，并集为 $\mathbb Z^+$。这一构造只依赖于 $n$，不依赖于随后给定的素数集。

任取一个无限正素数集 $P$。从中选出 $n-1$ 个素数，依次记为

$$p_1<p_2<\cdots<p_{n-1}.$$

取共同的正整数

$$m=\max\{n,p_{n-1}\}.$$

这样，所有 $p_j$ 都不超过 $m$。由于不超过 $m$ 的正整数只有有限个，而 $P$ 无限，可以再从 $P$ 中选出 $m$ 个不同素数

$$q_1<q_2<\cdots<q_m,\qquad q_1>m.$$

对每个 $i\in\{1,\ldots,n\}$，定义

$$a_i=\left(\prod_{j=1}^{i-1}p_j\right) \left(\prod_{j=1}^{m-i+1}q_j\right),$$

其中当 $i=1$ 时，第一个乘积为空乘积，取值为 $1$。

两组素数分别不超过 $m$ 和大于 $m$，因此互不重合；每组内部也没有重复。于是 $a_i$ 是 $P$ 中恰好

$$(i-1)+(m-i+1)=m$$

个不同素数的乘积，故由素因数分解的唯一性，$\omega(a_i)=m$。

在这些素因子中，不超过 $\omega(a_i)=m$ 的恰好是 $p_1,\ldots,p_{i-1}$，从而

$$f(a_i)=i-1.$$

因此 $a_i\in A_i$。所有 $a_i$ 使用的都是同一个 $m$，满足题目要求。由于 $P$ 是任意无限正素数集，构造得证。

检查

• 量词顺序： 先由给定的 $n$ 定义所有 $A_i$；随后对任意无限素数集 $P$ 选取一个共同的 $m$，再构造各 $a_i$。没有让集合依赖于 $P$，也没有为不同集合使用不同的 $m$。
• 选择的可行性： $P$ 无限，故能选出 $n-1$ 个素数；删去不超过有限界 $m$ 的素数后仍有无限多个，故还能选出所需的 $m$ 个 $q_j$。
• 下标与边界： $m\ge n$，所以对所有 $1\le i\le n$，都有 $1\le m-i+1\le m$。当 $i=1$ 时取零个 $p_j$；当 $i=n$ 时取全部 $n-1$ 个 $p_j$，均合法。
• 乘积与归属： 每个乘积恰有 $m$ 个互不相同的素因子，且恰有 $i-1$ 个不超过 $m$，因此 $\omega(a_i)=m$、$f(a_i)=i-1$，没有把不同素因子个数与重数混淆。
• 集合条件： 模 $n$ 的余数保证各 $A_i$ 两两不交；所构造的 $a_i$ 也证明每一部分非空。不同乘积之间可以共用素数，题目只要求每个乘积内部的素数不同。由于 $a_i$ 分属不交集合，它们自身也彼此不同。
• 特殊整数： $\omega(1)=f(1)=0$，故 $1\in A_1$；非平方自由整数也按同一规则归类。题目不要求集合中的每个元素都充当所需乘积，因此这些整数不影响证明。

独立复核后，该构造对每个给定的 $n\ge2$ 和每个无限正素数集均成立，满足最新题面的全部条件。

核心思路总结

关键是让分类规则同时读取“素因子总数”和“其中较小素因子的个数”。先把共同的乘积长度 $m$ 取得足够大，使给定素数集中至少有 $n-1$ 个素数不超过 $m$；然后分别选取其中零个、一个、直到 $n-1$ 个，再用大于 $m$ 的素数补足到同样的 $m$ 个。这样保持乘积长度不变，却能让分类指标依次取遍模 $n$ 的所有余数。

核心工具是素因数分解的唯一性、无限集合删去有限集后仍无限，以及按余数分类的构造。

参考资料

无。

C6

解答

设圆心为原点，记 $P_k$ 的位置向量为 $x_k$。由于所有点都在单位圆盘内部，

$$|x_k|<1\qquad(1\le k\le n).$$

各点两两不同，因此每条线段的长度均为正，可以定义沿折线前进的单位方向向量

$$u_k=\frac{x_{k+1}-x_k}{|x_{k+1}-x_k|}, \qquad 1\le k\le n-1.$$

记各外角及其总和为

$$\theta_k=\pi-\angle P_{k-1}P_kP_{k+1},\qquad T=\sum_{k=2}^{n-1}\theta_k.$$

在顶点 $P_k$，射向前一顶点的方向是 $-u_{k-1}$，射向后一顶点的方向是 $u_k$，故 $u_{k-1}$ 与 $u_k$ 的夹角恰为 $\theta_k\in[0,\pi]$。由余弦定理及 $\sin t\le t$，

$$|u_{k-1}-u_k| =\sqrt{2-2\cos\theta_k} =2\sin\frac{\theta_k}{2} \le\theta_k.$$

下面把折线长度按各顶点重新分组。用 $\langle\cdot,\cdot\rangle$ 表示内积，有

$$\begin{aligned} 90 &=\sum_{k=1}^{n-1}|x_{k+1}-x_k|\\ &=\sum_{k=1}^{n-1}\langle x_{k+1}-x_k,u_k\rangle\\ &=\langle x_n,u_{n-1}\rangle-\langle x_1,u_1\rangle +\sum_{k=2}^{n-1}\langle x_k,u_{k-1}-u_k\rangle. \end{aligned}$$

由柯西不等式和 $|x_k|<1$，两个端点项的和严格小于 $2$，每个内部顶点项则不超过 $|u_{k-1}-u_k|$。因此

$$90 <2+\sum_{k=2}^{n-1}|u_{k-1}-u_k| \le2+\sum_{k=2}^{n-1}\theta_k =2+T.$$

于是 $T>88$。再用圆周率的经典上界 $\pi<22/7$，得到

$$14\times2\pi=28\pi<28\times\frac{22}{7}=88<T,$$

即为所求。

检查

• 点与方向： 点两两不同保证相邻线段非零，所有单位方向向量均有定义。总长度为 $90$，也排除了只有一个点的情形。
• 外角含义： 内角由 $-u_{k-1}$ 与 $u_k$ 构成，因此外角正好是相邻前进方向之间的夹角，并未误用有向转角或转角的代数和。
• 共线情形： 直行时 $\theta_k=0$，方向向量差为零；折返时 $\theta_k=\pi$，方向向量差的长度为 $2\le\pi$。两种情形均包含在正文的不等式中。
• 分组恒等式： 每个内部顶点 $x_k$ 分别从前一线段贡献 $\langle x_k,u_{k-1}\rangle$、从后一线段贡献 $-\langle x_k,u_k\rangle$；两端各保留一项，符号与下标一致。
• 严格性： $\langle x_n,u_{n-1}\rangle\le|x_n|<1$，且 $-\langle x_1,u_1\rangle\le|x_1|<1$，故端点项之和严格小于 $2$。内部项即使为零，也不影响整体的严格不等式。
• 数值与适用范围： $90-2=88$，而 $28\times(22/7)=88$。证明不要求折线简单、凸或不自交，因而覆盖题目允许的所有折线。

独立复核后，外角约定、边界情形及严格不等号均已处理，结论成立。

核心思路总结

关键是用每段的单位方向向量表示线段长度，再按顶点分组。分组后，端点贡献由圆盘半径控制，内部顶点贡献由相邻单位方向向量之差控制；而这个差的长度不超过对应外角。由此直接把总长度转化为外角总和的下界。

核心工具是内积的分组恒等式、柯西不等式、$2\sin(\theta/2)\le\theta$ 及 $\pi<22/7$。

参考资料

无。

---

解答

设

$$\alpha_k=\angle P_{k-1}P_kP_{k+1}\quad (2\le k\le n-1),$$

则题目要求证明的外角和为

$$\sum_{k=2}^{n-1}(\pi-\alpha_k).$$

记

$$\delta_k=\pi-\alpha_k.$$

将折线展开：取 $Q_1,Q_2,\dots,Q_n$ 在一条直线上顺次排列，使得

$$|Q_iQ_{i+1}|=|P_iP_{i+1}|\quad (1\le i\le n-1).$$

令 $Q_1=0$，则由于折线总长为 $90$，

$$Q_n=90.$$

按提示构造点 $O_1,O_2,\dots,O_{n-1}$：对每个 $i=1,2,\dots,n-1$，使三角形 $O_iQ_iQ_{i+1}$ 与三角形 $OP_iP_{i+1}$ 全等，并且连续选取时满足

$$\angle O_iQ_{i+1}O_{i+1}=\pi-\angle P_iP_{i+1}P_{i+2}=\delta_{i+1} \quad (1\le i\le n-2).$$

因此

$$|O_iQ_{i+1}|=|O_{i+1}Q_{i+1}|=|OP_{i+1}|<1.$$

在三角形 $O_iQ_{i+1}O_{i+1}$ 中，两边长均为 $r_{i+1}=|OP_{i+1}|<1$，夹角为 $\delta_{i+1}$。由弦长公式，

$$|O_iO_{i+1}| =2r_{i+1}\sin\frac{\delta_{i+1}}2 \le 2\cdot 1\cdot \frac{\delta_{i+1}}2 =\delta_{i+1}.$$

这里用了 $\sin x\le x$。于是

$$\sum_{k=2}^{n-1}\delta_k =\sum_{i=1}^{n-2}\delta_{i+1} \ge \sum_{i=1}^{n-2}|O_iO_{i+1}|.$$

另一方面，由三角不等式，折线 $O_1O_2\cdots O_{n-1}$ 的长度不小于其两端点之间的距离：

$$\sum_{i=1}^{n-2}|O_iO_{i+1}| \ge |O_1O_{n-1}|.$$

设 $O_i$ 的横坐标为 $x_i$。因为 $Q_1=0$，且

$$|O_1Q_1|=|OP_1|<1,$$

所以

$$x_1<1.$$

又因为 $Q_n=90$，且

$$|O_{n-1}Q_n|=|OP_n|<1,$$

所以

$$x_{n-1}>89.$$

因此

$$|O_1O_{n-1}|\ge |x_{n-1}-x_1|>89-1=88.$$

从而

$$\sum_{k=2}^{n-1}\delta_k >88.$$

最后，由经典估计 $\pi<\frac{22}{7}$，有

$$28\pi<28\cdot \frac{22}{7}=88.$$

故

$$\sum_{k=2}^{n-1}(\pi-\angle P_{k-1}P_kP_{k+1}) =\sum_{k=2}^{n-1}\delta_k >88>28\pi=14\times 2\pi.$$

证毕。

检查

• 题意理解：外角和为 $\sum_{k=2}^{n-1}(\pi-\angle P_{k-1}P_kP_{k+1})$，需证明其大于 $14\times 2\pi=28\pi$。解答中记为 $\delta_k$，索引对应正确。
• 折线展开：令 $Q_1=0$、$Q_n=90$，因为 $|Q_iQ_{i+1}|=|P_iP_{i+1}|$ 且总长为 $90$，所以 $Q_n-Q_1=90$，横坐标设置无误。
• 辅助点构造：按提示构造 $O_i$，使得相邻外角对应为 $\delta_{i+1}$，且 $|O_iQ_{i+1}|=|OP_{i+1}|<1$。该构造合法。
• 弦长估计：在等腰三角形 $O_iQ_{i+1}O_{i+1}$ 中，两边长为 $r_{i+1}<1$，夹角为 $\delta_{i+1}$，所以$$|O_iO_{i+1}|=2r_{i+1}\sin\frac{\delta_{i+1}}2\le \delta_{i+1}.$$由于 $r_{i+1}<1$ 且 $\sin x\le x$，不等式成立。
• 横坐标估计：$|O_1Q_1|<1$ 推出 $x_1<1$；$|O_{n-1}Q_n|<1$ 推出 $x_{n-1}>89$。因此两端点水平距离大于 $88$。
• 数值比较：$28\pi<88$ 由 $\pi<22/7$ 得到，严格成立。故最终不等式严格大于。
• 边界情况：若某些外角为 $0$ 或 $\pi$，上述弦长估计仍成立；$n$ 足够大使折线总长可达 $90$，构造不退化。结论完整回答题目。

核心思路总结

关键步骤是将原折线展开到一条长度为 $90$ 的直线上，并构造辅助点 $O_i$，使每个外角 $\delta_{i+1}$ 控制相邻辅助点距离 $|O_iO_{i+1}|$。利用单位圆盘条件 $|OP_i|<1$，得到 $|O_iO_{i+1}|\le \delta_{i+1}$。再由辅助折线两端点的横坐标分别位于 $(-1,1)$ 与 $(89,91)$，其水平位移大于 $88$，从而外角和大于 $88$，而 $88>28\pi$。核心工具是折线展开、弦长公式、三角不等式以及经典估计 $\pi<22/7$。

参考资料

无

---

解答

设

$$\delta_k=\pi-\angle P_{k-1}P_kP_{k+1}\qquad (2\le k\le n-1).$$

题目要证明

$$\sum_{k=2}^{n-1}\delta_k>14\times 2\pi=28\pi.$$

取随机方向单位向量 $u$，均匀分布在单位圆上。将各点 $P_i$ 投影到方向 $u$ 上，记

$$R_i=P_i\cdot u.$$

对每个 $k=2,\dots,n-1$，定义

$$I_k(u)= \begin{cases} 1,& (R_{k-1}-R_k)(R_{k+1}-R_k)>0,\\ 0,&\text{否则}. \end{cases}$$

令

$$T(u)=\sum_{k=2}^{n-1}I_k(u),$$

即投影折线在 $u$ 方向上的总折返次数。

---

引理 1：对每个 $k$，有

$$\mathbb E I_k=\frac{\delta_k}{\pi}.$$

证明：令

$$a=P_k-P_{k-1},\qquad b=P_{k+1}-P_k.$$

则 $a$ 与 $b$ 的夹角为 $\delta_k$。设 $A=a\cdot u$，$B=b\cdot u$。折返条件

$$(R_{k-1}-R_k)(R_{k+1}-R_k)>0$$

等价于

$$(-A)B>0,$$

即

$$AB<0.$$

固定 $a$ 的方向角为 $\phi$，则 $b$ 的方向角为 $\phi+\delta_k$。设 $u$ 的方向角为 $\theta$。事件 $A>0$ 对应 $\theta$ 落在长度为 $\pi$ 的区间；事件 $B>0$ 也对应长度为 $\pi$ 的区间。这两个区间的交集长度为 $\pi-\delta_k$，因此 $AB<0$ 的总角度为

$$2\delta_k.$$

于是

$$\mathbb P(AB<0)=\frac{2\delta_k}{2\pi}=\frac{\delta_k}{\pi}.$$

故

$$\mathbb E I_k=\frac{\delta_k}{\pi}.$$

引理 1 得证。

由线性期望，

$$\mathbb E T =\sum_{k=2}^{n-1}\mathbb E I_k =\frac1\pi\sum_{k=2}^{n-1}\delta_k. \tag{1}$$

---

引理 2：对几乎每个方向 $u$，有

$$\sum_{i=1}^{n-1}|R_i-R_{i+1}| \le 2T(u)+|R_1|+|R_n|. \tag{2}$$

证明：随机方向下，几乎必然没有某条线段投影为 $0$，即所有 $|R_i-R_{i+1}|>0$。记

$$\Delta_i=R_{i+1}-R_i,\qquad s_i=\operatorname{sgn}\Delta_i.$$

此时 $T(u)$ 正好是相邻符号 $s_i$ 发生改变的次数。

令

$$L=\sum_{i=1}^{n-1}|R_i-R_{i+1}|.$$

因为所有 $R_i$ 都是单位圆盘内点的投影，所以

$$|R_i|\le 1.$$

下面归纳证明

$$L\le 2T(u)+|R_1|+|R_n|.$$

若 $T(u)=0$，则序列 $R_1,\dots,R_n$ 单调，于是

$$L=|R_n-R_1|\le |R_1|+|R_n|,$$

成立。

若 $T(u)>0$，取第一个折返点 $R_j$，即 $s_{j-1}\ne s_j$。从 $R_1$ 到 $R_j$ 单调，长度为

$$|R_j-R_1|\le |R_j|+|R_1|.$$

剩余序列 $R_j,\dots,R_n$ 的折返次数为 $T(u)-1$。由归纳假设，其总变差不超过

$$2(T(u)-1)+|R_j|+|R_n|.$$

因此

$$\begin{aligned} L &\le |R_j-R_1|+2(T(u)-1)+|R_j|+|R_n|\\ &\le (|R_j|+|R_1|)+2T(u)-2+|R_j|+|R_n|\\ &=2T(u)+|R_1|+|R_n|+2|R_j|-2\\ &\le 2T(u)+|R_1|+|R_n|, \end{aligned}$$

因为 $|R_j|\le 1$。引理 2 得证。

---

对 (2) 取期望。首先，

$$\mathbb E L =\sum_{i=1}^{n-1}\mathbb E|(P_{i+1}-P_i)\cdot u|.$$

对任意向量 $v$，若其长度为 $|v|$，则

$$\mathbb E|v\cdot u|=|v|\cdot \frac1{2\pi}\int_0^{2\pi}|\cos\theta|\,d\theta =|v|\cdot \frac2\pi.$$

因此

$$\mathbb E L =\frac2\pi\sum_{i=1}^{n-1}|P_iP_{i+1}| =\frac2\pi\cdot 90 =\frac{180}{\pi}.$$

同理，

$$\mathbb E|R_1|=\frac2\pi |OP_1|,\qquad \mathbb E|R_n|=\frac2\pi |OP_n|.$$

由于 $P_1,P_n$ 都在单位圆盘内部，故

$$|OP_1|<1,\qquad |OP_n|<1.$$

于是

$$\mathbb E|R_1|+\mathbb E|R_n| <\frac2\pi+\frac2\pi =\frac4\pi.$$

由 (2) 取期望得

$$\frac{180}{\pi} \le 2\mathbb E T+\mathbb E|R_1|+\mathbb E|R_n| <2\mathbb E T+\frac4\pi.$$

所以

$$2\mathbb E T>\frac{176}{\pi},$$

即

$$\mathbb E T>\frac{88}{\pi}.$$

又由经典估计

$$\pi<\frac{22}{7},$$

可得

$$\frac{88}{\pi}>\frac{88}{22/7}=28.$$

因此

$$\mathbb E T>28.$$

最后由 (1)，

$$\sum_{k=2}^{n-1}\delta_k =\pi\,\mathbb E T >28\pi =14\times 2\pi.$$

即

$$\sum_{k=2}^{n-1}(\pi-\angle P_{k-1}P_kP_{k+1})>14\times 2\pi.$$

证毕。

---

检查

• 题意理解正确：外角和为 $\sum_{k=2}^{n-1}(\pi-\angle P_{k-1}P_kP_{k+1})$，目标为大于 $28\pi$。
• 投影折返概率计算正确：相邻线段方向夹角为 $\delta_k$ 时，投影方向使两步反向的概率为 $\delta_k/\pi$。
• 一维折返不等式证明完整：利用归纳法，并用到投影点均在 $[-1,1]$ 内这一事实。
• 期望计算正确：随机方向投影长度的期望为原长度的 $2/\pi$，端点投影绝对值的期望为 $2|OP_i|/\pi$。
• 严格不等式来源清楚：$|OP_1|<1$、$|OP_n|<1$ 给出端点项严格小于 $4/\pi$，且 $\pi<22/7$ 给出最终严格大于 $28\pi$。
• 零步长情况已用“几乎必然”处理，不影响期望。
• 结论完整，符合题目要求。

核心思路总结

关键想法是随机投影：把原折线的外角转化为投影后一维折线的折返次数期望。每个外角 $\delta_k$ 对应折返概率 $\delta_k/\pi$，因此外角和等于 $\pi$ 乘总折返次数的期望。再利用一维折返次数与总投影路程的不等式

$$L\le 2T+|R_1|+|R_n|,$$

取期望后，由原折线总长 $90$ 和单位圆盘条件，推出折返次数期望大于 $28$，从而外角和大于 $28\pi$。

核心工具：随机投影、线性期望、一维折返不等式、经典估计 $\pi<22/7$。

参考资料

无

C7

解答

三组情形的答案是

$$\boxed{0\le\lambda<\frac{\sqrt5-1}{2}}.$$

一般地，记

$$\alpha_d=1-\frac{1}{4\cos^2\!\dfrac{\pi}{d+2}}.$$

对于给定的整数 $d\ge2$，全部可行的非负参数为

$$\boxed{ \begin{cases} [0,\frac12],&d=2,\\ [0,\frac23],&d=4,\\ [0,\alpha_d),&d\ge3,\ d\ne4. \end{cases}}$$

下面统一证明上界、构造及端点的取舍。一般上界是本题的主要难点；为保持证明自洽，先证明所需的有限支撑化简和递推引理。

一、将计数改写为比较概率，并化简每组的取值。

在第 $t$ 组中等概率地选取一个数，得到随机变量 $X_t$；各组的选择相互独立。则

$$\Pr(X_t>X_{t+1}) =\frac{|\{(i,j):a_i^{(t)}>a_j^{(t+1)}\}|}{n^2}.$$

下标按组数循环理解。由于题目要求所有实数两两不同，不同组的取值集合没有交点。

为证明上界，我们允许各取值具有不相等的概率。这只扩大了需要考虑的范围。以下称概率为正的取值为支撑点。

化简引理： 对有限支撑、支撑集合两两不交的独立随机变量 $X_1,\ldots,X_d$，可以在不减小任何循环比较概率的前提下，使每个变量至多有两个支撑点。

证明如下。若 $X_t$ 有至少三个支撑点，任选三个，记为 $z_1,z_2,z_3$，其概率为 $w_1,w_2,w_3>0$。令

$$c_j=\Pr(X_{t-1}>z_j),\qquad e_j=\Pr(z_j>X_{t+1}).$$

两个齐次线性方程

$$\sum_{j=1}^3h_j=0,\qquad \sum_{j=1}^3c_jh_j=0$$

有非零解 $(h_1,h_2,h_3)$。必要时把该解乘以 $-1$，可使 $\sum e_jh_j\ge0$。将三个概率改为 $w_j+\tau h_j$，其中

$$\tau=\min_{h_j<0}\frac{w_j}{-h_j}>0.$$

非零向量 $h$ 的分量和为零，所以确有负分量。上述修改保持各概率非负及总和不变，并使至少一个支撑点的概率变为零。同时，$\Pr(X_{t-1}>X_t)$ 不变，$\Pr(X_t>X_{t+1})$ 不减；其他比较概率不受影响。反复操作，支撑点总数不断减少，最终得到所需化简。各变量始终可按修改后的分布独立选取。引理得证。

二、证明一个递推引理。

本部分固定 $d\ge3$，简记

$$\theta=\frac{\pi}{d+2},\qquad q=\frac1{4\cos^2\theta},\qquad p=1-q=\alpha_d.$$

于是 $1/4<q<1/2$、$p>q$。定义

$$f(x)=1-\frac qx\qquad(x>0).$$

我们需要以下两个性质：

1. 存在严格递减的序列$$s_0=1>s_1=p>\cdots>s_{d-1}=q>s_d=0, \qquad s_{j+1}=f(s_j)\quad(0\le j\le d-1).$$
2. 对每个 $x\in[p,1]$，前 $d-1$ 次迭代均有定义，且$$x\bigl(1-f^{\,d-1}(x)\bigr)\le p.$$ 这里 $f^{\,k}$ 表示复合迭代 $k$ 次，不是函数值的幂。

为证明它们，令

$$H_{-1}=0,\quad H_0=H_1=1,\quad H_j=H_{j-1}-qH_{j-2}\quad(j\ge2).$$

由正弦加法公式可核验

$$H_j=\frac{\sin((j+1)\theta)}{(2\cos\theta)^j\sin\theta} \qquad(j\ge0).$$

所以 $H_0,\ldots,H_d$ 都为正，而 $H_{d+1}=0$。取

$$s_j=\frac{H_{j+1}}{H_j}\qquad(0\le j\le d),$$

便有 $s_0=1$、$s_1=p$、$s_d=0$ 和递推关系 $s_{j+1}=f(s_j)$。又由 $H_{d+1}=H_d-qH_{d-1}=0$ 得 $s_{d-1}=q$。由于对 $x>0$，

$$f(x)-x=-\frac{(x-\frac12)^2+q-\frac14}{x}<0,$$

上述序列严格递减，第一条性质成立。

在各次迭代有定义时，归纳代入 $f(x)=1-q/x$，可得

$$f^{\,k}(x) =\frac{H_kx-qH_{k-1}}{H_{k-1}x-qH_{k-2}}.$$

函数 $f$ 在正半轴严格递增。由于从 $p=s_1$ 出发直到第 $d-2$ 次迭代都为正，从任意 $x\in[p,1]$ 出发的前 $d-1$ 次迭代也都有定义。

利用 $H_d=qH_{d-1}$ 及递推式，有

$$\frac{H_{d-1}}{H_{d-2}}=\frac qp, \qquad \frac{qH_{d-3}}{H_{d-2}}=1-\frac qp.$$

因此

$$f^{\,d-1}(x)=\frac{q(x-p)}{px-p+q}.$$

当 $x\in[p,1]$ 时，分母至少为 $p^2-p+q=q^2>0$，并且

$$x\bigl(1-f^{\,d-1}(x)\bigr)-p =\frac{(p-q)(x-p)(x-1)}{px-p+q}\le0.$$

第二条性质也得证。

三、证明统一上界。

我们证明：对任意有限支撑、支撑集合两两不交的独立随机变量，

$$\min_{1\le t\le d}\Pr(X_t>X_{t+1})\le\alpha_d.$$

对 $d$ 归纳。$d=2$ 时，两种比较互补，故其概率之和为 $1$，较小者不超过 $1/2=\alpha_2$。

设 $d\ge3$，反设所有循环比较概率都严格大于 $p=\alpha_d$。由第一部分，可以假设每个变量至多有两个支撑点。记其最小、最大支撑点为 $l_t,h_t$。

若某一组的全部取值大于下一组，即 $l_t>h_{t+1}$，就删除 $X_{t+1}$。因为 $X_t$ 的每个取值都大于 $X_{t+1}$ 的每个取值，

$$\Pr(X_t>X_{t+2})\ge\Pr(X_{t+1}>X_{t+2})>p.$$

这样得到的 $d-1$ 个变量仍具有所有循环比较概率大于 $p$。但 $\alpha_d>\alpha_{d-1}$，与归纳假设矛盾。反之，若 $h_t<l_{t+1}$，则原来该次比较概率为零，也不可能。因此，以下可假定每对相邻支撑区间都有交叠。

令 $b_t$ 为 $X_t$ 取较小支撑点的概率；若只有一个支撑点，约定 $l_t=h_t$、$b_t=1$。相邻区间交叠保证 $l_t<h_{t+1}$，所以

$$b_t(1-b_{t+1}) \le\Pr(X_t<X_{t+1})<q. \tag{1}$$

只要 $b_t>0$，这就推出

$$b_{t+1}\ge f(b_t). \tag{2}$$

先考虑存在一对区间满足

$$l_t<l_{t+1}<h_t<h_{t+1}.$$

此时 $X_t>X_{t+1}$ 当且仅当 $X_t$ 取较大值、$X_{t+1}$ 取较小值，故

$$(1-b_t)b_{t+1}>p.$$

沿循环从 $b_{t+1}$ 开始到 $b_t$ 结束，依次记这 $d$ 个数为 $x_1,\ldots,x_d$。则 $x_1>p$，由式 $(2)$、$f$ 的递增性及第二部分的正性结论，逐次得到

$$x_d\ge f^{\,d-1}(x_1).$$

因此，第二部分的递推引理给出

$$p<x_1(1-x_d) \le x_1\bigl(1-f^{\,d-1}(x_1)\bigr)\le p,$$

矛盾。

剩下的情形是不存在上述交叉顺序。循环序列 $l_1,\ldots,l_d$ 中必有一次上升 $l_t<l_{t+1}$；由于相邻区间交叠、且已排除该交叉顺序，只能有

$$l_t<l_{t+1}\le h_{t+1}<h_t.$$

于是 $X_t$ 胜过 $X_{t+1}$ 当且仅当它取较大值，所以 $1-b_t>p$，即 $b_t<q$。称此边为包含边。

同样，循环序列 $h_1,\ldots,h_d$ 中必有一次上升 $h_v<h_{v+1}$。此时只能有

$$l_{v+1}<l_v\le h_v<h_{v+1},$$

故比较概率为 $b_{v+1}>p$。这条边与包含边不同。

从 $b_{v+1}>p$ 出发，沿循环前进至一条包含边的起点 $b_t<q$，途中不经过边 $v\to v+1$。将经过的数记为 $x_1,\ldots,x_r$，则 $r\le d-1$。再次迭代式 $(2)$，得到

$$x_r\ge f^{\,r-1}(x_1) >f^{\,r-1}(p)=s_r\ge s_{d-1}=q,$$

与 $x_r<q$ 矛盾。当 $r=1$ 时，矛盾直接来自同一个数既大于 $p$ 又小于 $q$。

两种情形均矛盾，故统一上界成立。特别地，题目中的参数必满足 $\lambda\le\alpha_d$。

四、构造所有严格小于上界的参数。

固定 $d\ge3$ 及 $0\le\lambda<p=\alpha_d$，沿用第二部分的 $s_j$。取正整数

$$n>\max\left\{\frac1q,\frac2{p-\lambda}\right\},$$

并对 $2\le t\le d$ 令

$$k_t=\lfloor ns_{t-1}\rfloor,\qquad b_t=\frac{k_t}{n}.$$

由于 $q\le s_{t-1}\le p<1$，有 $1\le k_t\le n-1$，且

$$|b_t-s_{t-1}|<\frac1n.$$

第 $1$ 组取一个含 $n$ 个数的中间块 $C$。对于第 $t$ 组，分别取含 $k_t$ 个数的低位块 $L_t$、含 $n-k_t$ 个数的高位块 $U_t$。把全部 $dn$ 个不同整数 $1,\ldots,dn$ 按以下块顺序依次分配：

$$L_d<L_{d-1}<\cdots<L_2<C<U_d<U_{d-1}<\cdots<U_2.$$

这里两个块之间的 $<$ 表示前一块的每个数都小于后一块的每个数。第 $1$ 组为 $C$，第 $t$ 组为 $L_t\cup U_t$，故每组恰有 $n$ 个数，且所有数两两不同。

各循环比较的比例为

$$\begin{aligned} \Pr(X_1>X_2)&=b_2,\\ \Pr(X_t>X_{t+1})&=1-b_t(1-b_{t+1})\quad(2\le t\le d-1),\\ \Pr(X_d>X_1)&=1-b_d. \end{aligned}$$

第二行的唯一失败情形是从第 $t$ 组取低位数、从第 $t+1$ 组取高位数。

理想比例 $b_t=s_{t-1}$ 时，第一、最后一个比较比例都是 $p$；中间的比例也因

$$s_{t-1}(1-s_t)=q$$

而等于 $p$。对于实际取整后的比例，首尾误差小于 $1/n$。中间项由

$$|b_t(1-b_{t+1})-s_{t-1}(1-s_t)| \le |b_t-s_{t-1}|+|b_{t+1}-s_t|<\frac2n$$

知，其误差也小于 $2/n$。因此所有比较比例都严格大于

$$p-\frac2n>\lambda.$$

这就构造出了每个 $0\le\lambda<\alpha_d$。

五、判定上界能否取到。

每个实际比较比例都是分母为 $n^2$ 的有理数。如果 $\alpha_d$ 无理，那么所有比较比例都至少为 $\alpha_d$ 就意味着它们全都严格大于 $\alpha_d$，与第三部分的上界矛盾。因此无理上界不能取到。

下面证明 $\alpha_d$ 仅在 $d=2,4$ 时为有理数。若 $\alpha_d$ 有理，则

$$z=\frac1{1-\alpha_d}-2 =2\cos\frac{2\pi}{d+2}$$

也是有理数。定义整系数多项式

$$Q_0(x)=2,\quad Q_1(x)=x,\quad Q_j(x)=xQ_{j-1}(x)-Q_{j-2}(x).$$

对 $j\ge1$，$Q_j$ 为首一多项式；余弦加法公式给出

$$Q_j(2\cos u)=2\cos(ju).$$

所以 $Q_{d+2}(z)-2=0$。首一整系数多项式的有理根必为整数：将既约分数代入并清除分母，分母必须整除首项系数 $1$。故 $z$ 为整数。又因 $d\ge2$，有 $0\le z<2$，只能取 $z=0$ 或 $z=1$，分别对应 $d=2$ 或 $d=4$。

这两个上界都能取到：

• 当 $d=2$ 时，取 $n=2$，两组分别为 $\{1,4\}$ 和 $\{2,3\}$。两个方向的比较比例均为 $1/2$。
• 当 $d=4$ 时，取 $n=6$，四组依次为$$\begin{aligned} A^{(1)}&=\{10,11,12,13,14,15\},\\ A^{(2)}&=\{6,7,8,9,23,24\},\\ A^{(3)}&=\{3,4,5,20,21,22\},\\ A^{(4)}&=\{1,2,16,17,18,19\}. \end{aligned}$$这是第四部分中低位比例依次取 $2/3,1/2,1/3$ 的构造。四个循环比较比例分别为$$\frac23,\qquad 1-\frac23\left(1-\frac12\right),\qquad 1-\frac12\left(1-\frac13\right),\qquad 1-\frac13,$$均等于 $2/3$。

这两个端点构造也适用于所有更小的非负参数。最后，$d=3$ 时，第二部分中的 $H_4=1-3q+q^2=0$，结合 $1/4<q<1/2$ 得

$$q=\frac{3-\sqrt5}{2},\qquad \alpha_3=1-q=\frac{\sqrt5-1}{2}.$$

该数无理，故三组情形的右端点不取。所有结论得证。

检查

• 题意与概率模型： 每组独立等概率选取一个元素，每个有序指标对的概率恰为 $1/n^2$，准确对应题目的计数。循环的最后一次比较是第 $d$ 组对第 $1$ 组。
• 上界的适用范围： 不等权概率仅用于证明更广范围内的上界；最终构造全部恢复为每组 $n$ 个不同数的等权模型。化简时只删除原支撑点，保持不同组的支撑集合不交。
• 化简与归纳： 概率扰动保持总质量和前一比较概率，后一比较概率不减。删除完全较低的一组时，新比较概率不小于被替换的比较概率；$d=2$ 的互补比较已单独作为归纳起点。
• 区间情形完整性： 相邻区间若不交，比较概率只能为零或一，已处理。交叠时先排除一种交叉顺序；余下情形利用最小值和最大值循环序列各必有上升，分别得到一个包含关系和一个被包含关系，覆盖单支撑点的退化区间。
• 递推的合法性： $H_0,\ldots,H_d>0$；从 $p$ 出发的前 $d-2$ 次迭代为正。上界证明中从更大的数出发，逐次比较均可在正半轴进行，没有除以零。终端公式的分母至少为 $q^2>0$。
• 构造及边界： 取整误差严格小于 $1/n$，乘积项误差小于 $2/n$；所选 $n$ 同时保证每个低位块和高位块非空。使用整数 $1,\ldots,dn$ 保证全部数两两不同。$\lambda=0$ 包含在构造范围中，无理上界的排除依赖于有限计数比例必为有理数。

独立核验。 对递推式和终端恒等式重新进行代数核算，所得式子与正文一致；另外对 $3\le d\le30$ 作数值代入检查，对 $3\le d\le20$ 的取整构造作直接比较计数。两个可取端点的有限构造也已逐对计数：两组例子的胜出对数均为 $2$，四组例子的四个胜出对数均为 $24$，分别对应 $2/4=1/2$ 和 $24/36=2/3$。还穷举了 $(d,n)=(2,2),(3,2),(3,3),(3,4),(4,2),(5,2)$ 时所有带组别的大小排列，均符合上界。这些计算只用于交叉核查，任意组数的结论由正文证明。

核心思路总结

最难的一步是统一上界。先通过概率质量的线性扰动，把每组化简为至多两个取值；相邻支撑区间的相对位置随后把循环比较转化为 $b_t(1-b_{t+1})\le q$，即分式递推 $b_{t+1}\ge1-q/b_t$。这个递推的临界参数由正弦递推式确定，并同时控制两种可能的区间排列。

构造沿用同一临界递推：一组放在中间，其余各组分成低位、高位两块，安排块的次序，使每次比较的失败概率都等于相邻两块比例的乘积。将比例取整便得到真正的等大小有限数组。最后用比较比例的有理性，区分最优上界与可取的最大值。

核心工具是独立选取的概率解释、有限支撑的线性扰动、分式递推与三角恒等式、有理数逼近，以及首一整系数多项式的有理根性质。

参考资料

无。