物理

一道经典CMO难题

IMO 太空站由 99 个空间站组成，任两个空间站之间有管形通道相连，规定其中 99 条通道为双向通行的主干道，其余通道严格单向通行。如果某 4 个空间站可以通过它们之间的通道从其中任一站到达另外任一站，就称这些站组成的集合为一个互通四站组。

试求互通四站组个数的最大值，并证明你的结论。（1999CMO3）

解析：

由正面求“四通组”的个数是比较困难的，因为其条件较为苛刻，而满足非互通的四站组的条件相对容易。

比如，想象一个空间站“无回路”即可。由此想到考察从一点引出的所有单向通道，每 3 条这样的通道对应一个非互通的四站组。

当然，还可能有其他的非互通的四站组，但那些非互通的四站组并非必定存在，也就是说，也许可以选择一个方案，使那些非互通的四站组的个数为零，从而可以略去这些非互通的四站组的个数估计。

假设 99 个空间站为 $ A_1, A_2, \cdots, A_{99} $，由 $ A_i $ 出发的单向通道条数、指向 $ A_i $ 的单向通道条数、通过 $ A_i $ 的主干道条数分别为 $ w_i, l_i, k_i $。

由条件，有  

$w_i + l_i + k_i = 98,$

$k_1 + \cdots + k_{99} = 198,$

$w_1 + \cdots + w_{99} = l_1 + \cdots + l_{99},$  

于是

$\sum_{i=1}^{99} w_i = \sum_{i=1}^{99} l_i = \frac{1}{2} \sum_{i=1}^{99} (w_i + l_i)$

$= \frac{1}{2} \sum_{i=1}^{99} (w_i + l_i + k_i) - \frac{1}{2} \sum_{i=1}^{99} k_i$

$= 4752.$

因为 $ A_i $ 引出 $ w_i $ 条单向通道，其中任何 3 条组成一个输出型三面角，这个三面角的四个顶点是一个不互通四站组，而且同一个不互通的四站组不可能包含两个输出三面角

所以非互通四站组的数目  

$S \geqslant \sum_{i=1}^{99} C_{w_i}^3.$

下面求 $ \displaystyle \sum_{i=1}^{99} C_{w_i}^3 $ 的最小值。

方法 1：

首先，由于满足 $ w_1 + \cdots + w_{99} = 4752 $ 的数组 $ (w_1, \cdots, w_{99}) $ 只有有限个，从而最小值一定存在。

其次，从直观猜测，当 $ w_1 = \cdots = w_{99} = 48 $ 时，$ \displaystyle \sum_{i=1}^{99} C_{w_i}^3 $ 最小。

反设结论不然，则必有一个 $ i $，使 $ w_i \lt 48 $，也必有一个 $ j $，使 $ w_j \gt 48 $。将 $ w_i $ 改为 $ w_i + 1 $，$ w_j $ 改为 $ w_j - 1 $，得到一个新的数组

由于

$C_{w_i}^3 + C_{w_j}^3 - C_{w_i+1}^3 - C_{w_j-1}^3 = \frac{1}{2}(w_j - 1)(w_j - 2) - \frac{1}{2}w_i(w_i - 1) \gt 0 \quad (\text{因为 } w_j - 1 \gt w_i),$

所以新数组对应的和比原数组小，矛盾。

于是 $ \displaystyle \sum_{i=1}^{99} C_{w_i}^3 $ 的最小值为 $ 99 C_{48}^3 $

而互通的四站组不多于  

$C_{99}^4 - 99 C_{48}^3 = 2\,052\,072.$

方法 2：

由幂平均不等式，有

$\sum_{i=1}^{99} w_i^3 \geqslant \frac{1}{\sqrt[3]{99}} \left( \sum_{i=1}^{99} w_i^2 \right)^{\frac{3}{2}},$

$\sum_{i=1}^{99} C_{w_i}^3 = \frac{1}{6} \sum_{i=1}^{99} w_i^3 - \frac{1}{2} \sum_{i=1}^{99} w_i^2 + \frac{1}{3} \sum_{i=1}^{99} w_i$

$\geqslant \frac{1}{6\sqrt{99}} \left( \sum_{i=1}^{99} w_i^2 \right)^{\frac{3}{2}} - \frac{1}{2} \sum_{i=1}^{99} w_i^2 + \frac{1}{3} \times 4752.$

注意到

$\frac{1}{6\sqrt{99}} x^{\frac{3}{2}} - \frac{1}{2} x = \frac{1}{6} x \left( \sqrt{\frac{x}{99}} - 3 \right)$

严格递增，且

$\sum_{i=1}^{99} w_i^2 \geqslant \frac{1}{99} \left( \sum_{i=1}^{99} w_i \right)^2 = 228096,$

故

$\sum_{i=1}^{99} C_{w_i}^3 \geqslant \frac{1}{6\sqrt{99}} \times 228\,096^{\frac{3}{2}} - \frac{1}{2} \times 228\,096 + \frac{1}{3} \times 4752 =$ $1712304,$

从而互通四站组的数目不多于  

$C_{99}^4 - 1712304 = 2052072.$

下面证明等号可以成立。先将所有通道设成单向，方向如下规定：对 $ i \lt j $，若 $ i,j $ 同奇偶，则由 $ A_i $ 指向 $ A_j $，否则 $ A_j $ 指向 $ A_i $。此时每个点恰发出 49 条单向通道。现将 99 条通道 $ A_iA_{i+1} $（$ i=1,2,\cdots,99 $，$ A_{100}=A_1 $）改为双向通道，则每个点发出和进入的单向通道恰有一条被改为双向通道，故 $ w_i = l_i = 48 $（$ i=1,2,\cdots,99 $），故有中心的四站组个数为 $ 99 C_{48}^3 = 1\,712\,304 $

下面证明每一个非互通四站组都有一个中心（向其他三点引出单向通道的点）。

事实上，设 $ (A_i,A_j,A_k,A_t) $ 是任意一个无中心的非互通四站组（以下仅用 $ i $ 代表 $ A_i $）

若其中有一条双向通道 $ ij $，则 $ ik $ 和 $ jk $ 不可能都由 $ k $ 发出，或都指向 $ k $（若 $ j=i+1 $ 或 $ j=i-1 $，则 $ k $ 要么比 $ i,j $ 都大，要么都小，而 $ i,j $ 不同奇偶

若 $ \{i,j\}=\{1,99\} $，则 $ i,j $ 同奇偶，但 $ k $ 比一个大，比另一个小），对 $ t $ 也一样，故 $ ijkt $ 是互通的，矛盾，故其中无双向通道。

由于 $ ijkt $ 不互通，故其中有一个站（设为 $ i $），它和其余三个站之间的通道都是单向的，而且都指向 $ i $。

故 $ j,k,t $ 只有两种情况：要么比 $ i $ 小且与 $ i $ 同奇偶（称为 I 型），要么比 $ i $ 大且奇偶性不同（称为 II 型）。

如果 $ j,k,t $ 都为 I 型，则 $ j,k,t $ 同奇偶，故其中最小的是 $ (ijkt) $ 的一个中心，矛盾。如果 $ j,k,t $ 都为 II 型，则 $ j,k,t $ 中最小的是 $ (ijkt) $ 的一个中心，矛盾。

如果 $ j,k,t $ 中有两个，比如 $ j,k $ 为 I 型，则 $ t $ 比 $ j,k $ 都大且不同奇偶，故 $ t $ 是 $ (ijkt) $ 的中心，矛盾。

如果 $ j,k,t $ 中有一个，比如 $ j $ 为 I 型，则 $ k,t $ 比 $ i,j $ 大且不同奇偶，故 $ k,t $ 中必有一个为中心，矛盾。

这就证明了每个非互通四站组必有中心。

于是，非互通四站组共有 $ 1712304 $ 个，从而互通四站组有 $ 2052072 $ 个。

综上所述，所求最大值为2052072