$MO$ 太空城由 $99$ 个空间站组成．任两空间站之间有管形通道相连．规定其中 $99$ 条通道为双向通行的主干道，其余通道严格单向通行．如果某四个空间站可以通过它们之间的通道从其中任一站到达另外任一站，则称这四个站的集合为一个互通四站组．
试为 $MO$ 太空城设计一个方案，使得互通四站组的数目最大（请具体算出该最大数，并证明你的结论）．
试为 $MO$ 太空城设计一个方案，使得互通四站组的数目最大（请具体算出该最大数，并证明你的结论）．
【难度】
【出处】
1999第14届CMO试题
【标注】
【答案】
略
【解析】
在下面的讨论中，设 $n$ 是大于 $3$ 的奇数，并记 $m\dfrac{3-n}{2}$．我们将讨论 $n$ 个空间站和 $n$ 条双行主干道的更一般情形对于本题而言 $n= 99,m=\dfrac{n-3}{2} = 48$．
（1）如果某四个空间站中，有一个站与其他三站间的通道都从该站单向发出．那么，这四站的集合必定是不互通的四站组．约定将所有这样的不互通四站组归入 $S$ 类；并将所有不属于 $S$ 类的不互通四站组归入 $T$ 类，则互通四站组的总数为 $C_{n}^{4}-|S|-|T|$．用 $1,2, \cdots,n$ 给 $n$ 个空间站编号．设从第 $i$ 号空间站发出的单行通道数为 $S_i$，则 $S$ 类不互通四站组的总数为 $|S|=\sum_{i=1}^{n} C_{i}^{3}$，这里 $C_{k}^{3}=\frac{k(k-1)(k-2)}{6}$
（2）对于如上定义的 $C_{k}^{3}$ 和 $C_{k}^{2}=\dfrac{k(k-1)}{2}$，熟知有关系（可直接验证）$C_{k}^{3}=C_{k-1}^{3}+C_{k-1}^{2}$ 如果 $s>t+1$，那么 $C_{s}^{3}-C_{s-1}^{3}=C_{s-1}^{2}>C_{i}^{2}=C_{t+1}^{3}-C_{t}^{3}$ 即 $C_{s}^{3}+C_{t}^{3}>C_{s-1}^{3}+C_{t+1}^{3}$ 根据以上探讨，通过“调整法”可以断定 $\displaystyle |S|=\sum\limits_{i=1}^{n} C_{s_{i}}^{3} \geqslant n \mathrm{C}_{m}^{3}$ 其中 $m=\dfrac{1}{n} \sum_{i=1}^{n} s_{i}=\dfrac{1}{n}\left(C_{n}^{2}-n\right)=\dfrac{n-3}{2}$ 据此估计互通四站组总数的上界为 $C_{n}^{4}-|S|-|T| \leqslant C_{n}^{4}-n C_{m}^{3}$
（3）如果能设计一个方案，使得 $S$ 类不互通四站组的数目降到最小值 $n C_{m}^{3}$，并且 $T$ 类不互通四站组的数目也降到最少（实际降到 $0$），那么，该方案的互通四站组的数目达到最大．为此目的，首先将编号为 $1,2,\cdots,n$ 的空间站依顺时针次序安排在一个圆周上．下面将给出满足要求的两种方案．
第一方案：首先将沿圆周相邻的空间站对之间的通道定为主干道．这样设定了 $n$ 条主干道 $\{1,2\},\{2,3 \}, \cdots,\{n-1, n\},\{n, 1\}$ 对于 $i, j \in\{1,2, \cdots, n\}, i \neq j$，如果圆周上沿顺时针方向从 $i$ 到 $j$ 的弧经过奇数个中间站，那么，规定 $i$ 号站与 $j$ 号站之间的通道为 $i\rightarrow j$ 单行道．因为 $n$ 是奇数，从 $k$ 到 $l$ 的顺时针圆弧和从 $l$ 到 $k$ 的顺时针圆弧当中，恰有一条经过奇数个中间站，所以上述单行约
定不会导致矛盾情形．
按照此方案，从每个空间发出的单行道都为 $m= \dfrac{n-3}{2}$ 条．因此，$S$ 类不互通四站组总数降至最小值 $|S|=n \mathrm{C}_{m}^{3}$
下面将指出，按照此方案有 $|T|= 0$．
如果四站组中某两站间有主干道相连，那么，四站组中其余任一站都与这两站互通．因此，这样的四站组为互通四站组．
考察从四站组的某三站到剩下一站的三条通道都单向通往这剩下一站的情形，设在除去剩下一站 $D$ 的圆周上，所述的三站按顺时针方向依次为 $A,B,C$．因为 $A\rightarrow D,B\rightarrow D,C\rightarrow D$，根据方案的单行规定可以判断 $A$ 与 $B$ 之间和 $A$ 与 $D$ 之间的顺时针圆弧上各经过奇数个中间站我们判明通道 $A\rightarrow B,A\rightarrow C,A\rightarrow D$ 的单行方向，因此，这样的不互通四站组\{A，B，C，D\}应归入 $S$ 类．
根据以上的讨论，可以断定 $|T|= 0$．最后，算出互通四站组数的最大值 $C_{n}^{4}-n C_{m}^{3}=\frac{n(n-3)}{48}\left(n^{2}+6 n-31\right)$ 对于 $n = 99$，互通四站组数的最大值为 $99 \times \frac{96}{48} \times(9801+594-31)=,99 \times 2 \times 10364=2052072$
第二方案（同样先将编号为 $1,2, \cdots, n$ 的空间站按顺时针次序安排于一个圆周上．）
如果从 $a$ 号空间站到 $b$ 号空间站的顺时针圆弧恰经过 $\dfrac{n-3}{2}$
个或者 $\dfrac{n-1}{2} $ 个中间站，那么，规定 $ a$ 与 $b$ 间的通道为双行主干道．如果从 $i$ 号空间站到 $j$ 号空间站的顺时针圆弧经过的中间站数少
于 $\dfrac{n-3}{2}$ 则规定 $i$ 与 $j$ 之间的通道单向从 $i$ 通往 $j$．
按照此方案，从每个空间站发出的单行通道数都为 $m=\dfrac{n-3}{2}$ 条．因此，$ S $ 类不互通四站组数降至最小值 $ |S|=n \mathrm{C}_{m}^{3}$
按照此方案，同样可证 $|T|= 0$．事实上，与第一方案类似的验证讨论，可以判定：如果某四站组中有两站间的通道是主干道，那么，这四站组是互通的还可以判定：如果从四站组中某三站到剩下一站 $D$ 的通道都单向通往该站，那么，这三站在除去点 $D$ 的圆周上顺时针方向排头的一站 $A$ 通往其他三站 $B,C,D$ 的通道都单向发出：$A\rightarrow B,A\rightarrow C,A\rightarrow D$．因此，这类四站组 $ \{A,B,C,D\} $ 应归入 $ S $ 类
因此，按照此方案建造的太空城，没有 $ T$ 类不互通四站组，并且互通四站组数达到最大．剩下的计算同第一方案．
（1）如果某四个空间站中，有一个站与其他三站间的通道都从该站单向发出．那么，这四站的集合必定是不互通的四站组．约定将所有这样的不互通四站组归入 $S$ 类；并将所有不属于 $S$ 类的不互通四站组归入 $T$ 类，则互通四站组的总数为 $C_{n}^{4}-|S|-|T|$．用 $1,2, \cdots,n$ 给 $n$ 个空间站编号．设从第 $i$ 号空间站发出的单行通道数为 $S_i$，则 $S$ 类不互通四站组的总数为 $|S|=\sum_{i=1}^{n} C_{i}^{3}$，这里 $C_{k}^{3}=\frac{k(k-1)(k-2)}{6}$
（2）对于如上定义的 $C_{k}^{3}$ 和 $C_{k}^{2}=\dfrac{k(k-1)}{2}$，熟知有关系（可直接验证）$C_{k}^{3}=C_{k-1}^{3}+C_{k-1}^{2}$ 如果 $s>t+1$，那么 $C_{s}^{3}-C_{s-1}^{3}=C_{s-1}^{2}>C_{i}^{2}=C_{t+1}^{3}-C_{t}^{3}$ 即 $C_{s}^{3}+C_{t}^{3}>C_{s-1}^{3}+C_{t+1}^{3}$ 根据以上探讨，通过“调整法”可以断定 $\displaystyle |S|=\sum\limits_{i=1}^{n} C_{s_{i}}^{3} \geqslant n \mathrm{C}_{m}^{3}$ 其中 $m=\dfrac{1}{n} \sum_{i=1}^{n} s_{i}=\dfrac{1}{n}\left(C_{n}^{2}-n\right)=\dfrac{n-3}{2}$ 据此估计互通四站组总数的上界为 $C_{n}^{4}-|S|-|T| \leqslant C_{n}^{4}-n C_{m}^{3}$
（3）如果能设计一个方案，使得 $S$ 类不互通四站组的数目降到最小值 $n C_{m}^{3}$，并且 $T$ 类不互通四站组的数目也降到最少（实际降到 $0$），那么，该方案的互通四站组的数目达到最大．为此目的，首先将编号为 $1,2,\cdots,n$ 的空间站依顺时针次序安排在一个圆周上．下面将给出满足要求的两种方案．
第一方案：首先将沿圆周相邻的空间站对之间的通道定为主干道．这样设定了 $n$ 条主干道 $\{1,2\},\{2,3 \}, \cdots,\{n-1, n\},\{n, 1\}$ 对于 $i, j \in\{1,2, \cdots, n\}, i \neq j$，如果圆周上沿顺时针方向从 $i$ 到 $j$ 的弧经过奇数个中间站，那么，规定 $i$ 号站与 $j$ 号站之间的通道为 $i\rightarrow j$ 单行道．因为 $n$ 是奇数，从 $k$ 到 $l$ 的顺时针圆弧和从 $l$ 到 $k$ 的顺时针圆弧当中，恰有一条经过奇数个中间站，所以上述单行约
定不会导致矛盾情形．
按照此方案，从每个空间发出的单行道都为 $m= \dfrac{n-3}{2}$ 条．因此，$S$ 类不互通四站组总数降至最小值 $|S|=n \mathrm{C}_{m}^{3}$
下面将指出，按照此方案有 $|T|= 0$．
如果四站组中某两站间有主干道相连，那么，四站组中其余任一站都与这两站互通．因此，这样的四站组为互通四站组．
考察从四站组的某三站到剩下一站的三条通道都单向通往这剩下一站的情形，设在除去剩下一站 $D$ 的圆周上，所述的三站按顺时针方向依次为 $A,B,C$．因为 $A\rightarrow D,B\rightarrow D,C\rightarrow D$，根据方案的单行规定可以判断 $A$ 与 $B$ 之间和 $A$ 与 $D$ 之间的顺时针圆弧上各经过奇数个中间站我们判明通道 $A\rightarrow B,A\rightarrow C,A\rightarrow D$ 的单行方向，因此，这样的不互通四站组\{A，B，C，D\}应归入 $S$ 类．
根据以上的讨论，可以断定 $|T|= 0$．最后，算出互通四站组数的最大值 $C_{n}^{4}-n C_{m}^{3}=\frac{n(n-3)}{48}\left(n^{2}+6 n-31\right)$ 对于 $n = 99$，互通四站组数的最大值为 $99 \times \frac{96}{48} \times(9801+594-31)=,99 \times 2 \times 10364=2052072$
第二方案（同样先将编号为 $1,2, \cdots, n$ 的空间站按顺时针次序安排于一个圆周上．）
如果从 $a$ 号空间站到 $b$ 号空间站的顺时针圆弧恰经过 $\dfrac{n-3}{2}$
个或者 $\dfrac{n-1}{2} $ 个中间站，那么，规定 $ a$ 与 $b$ 间的通道为双行主干道．如果从 $i$ 号空间站到 $j$ 号空间站的顺时针圆弧经过的中间站数少
于 $\dfrac{n-3}{2}$ 则规定 $i$ 与 $j$ 之间的通道单向从 $i$ 通往 $j$．
按照此方案，从每个空间站发出的单行通道数都为 $m=\dfrac{n-3}{2}$ 条．因此，$ S $ 类不互通四站组数降至最小值 $ |S|=n \mathrm{C}_{m}^{3}$
按照此方案，同样可证 $|T|= 0$．事实上，与第一方案类似的验证讨论，可以判定：如果某四站组中有两站间的通道是主干道，那么，这四站组是互通的还可以判定：如果从四站组中某三站到剩下一站 $D$ 的通道都单向通往该站，那么，这三站在除去点 $D$ 的圆周上顺时针方向排头的一站 $A$ 通往其他三站 $B,C,D$ 的通道都单向发出：$A\rightarrow B,A\rightarrow C,A\rightarrow D$．因此，这类四站组 $ \{A,B,C,D\} $ 应归入 $ S $ 类
因此，按照此方案建造的太空城，没有 $ T$ 类不互通四站组，并且互通四站组数达到最大．剩下的计算同第一方案．
答案
解析
备注
