2015第31届CMO试题

• 知识点

  >

  二试组合部分

略

考虑选手总数为 $n$ 的情形（在本题中 $n= 100$）．
下面对所有整数 $n\geqslant 4$ 证明（1）的结论，并对所有整数 $n
\geqslant 11$，证明（2）中 $m(T)$ 的最小值等于 $3$．
（1）将赛事结果 $T$ 看作一个以选手为顶点、战胜关系为有向边的竞赛图，选手总数 $n$ 即为图 $T$ 的顶点数，$T$ 为友好的等价于图 $T$ 为强连通的．
先证明三个引理．
引理一：当 $n\geqslant 3$ 时，图 $T$ 有一个长度为 $n$ 的圈．
引理一的证明：首先，图 $T$ 中必有圈（事实上，任取 $x,y$，不妨设 $x \rightarrow y$，由图 $T$ 的强连通性，知存在从 $y$ 到 $x$ 的一条最短路径 $y \longrightarrow \cdots \rightarrow x$，则 $x \rightarrow y \rightarrow \cdots \rightarrow x$ 为一个圈）．
设 $v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{p} \rightarrow v_{1}$ 为图 $T$ 中一个最长的圈．
假如 $p\leqslant n-1$，任取 $u\notin\left\{v_{1}, v_{2}, \cdots, v_{p}\right\}$．
若对所有 $i=1,2,\cdots ,p$ 均有 $u\rightarrow v_i$，考虑从 $\left\{v_{1}, v_{2}, \cdots, v_{p}\right\}$ 到 $u$ 的最短有向路，不妨设为
$v_{p} \rightarrow z_{1} \rightarrow \cdots \rightarrow z_{k} \rightarrow u$ 则 $k\geqslant 1$，且所有 $z_{1}, z_{2}, \cdots, z_{k}$ 均不属于 $\left\{v_{1}, v_{2}, \cdots, v_{p}\right\}$．
于是，存在长度为 $p+k+1>p$ 的圈 $v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{p} \rightarrow z_{1} \rightarrow \cdots \rightarrow z_{k} \rightarrow u \rightarrow v_{1}$，矛盾．
若对所有 $i=1,2,\cdots ,p$ 均有 $v_i\rightarrow u$，考虑从 $u$ 到 $\left\{v_{1}, v_{2}, \cdots, v_{p}\right\}$ 的最短有向路，不妨设为 $u \rightarrow z_{1} \rightarrow \cdots \rightarrow z_{k} \rightarrow v_{1}$，则 $k\geqslant 1$，且所有 $z_{1}, z_{2}, \cdots, z_{k}$ 均不属于 $\left\{v_{1}, v_{2}, \cdots, v_{p}\right\}$．
于是，存在长度为 $p+k+1>p$ 的圈 $v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{p} \rightarrow u \rightarrow z_{1} \rightarrow \cdots \rightarrow z_{k} \rightarrow v_{1}$，矛盾．
其余情形下，存在 $i, j \in\{1,2, \cdots, p\}$，使得 $v_{i} \rightarrow u \rightarrow v_{j}$，不妨设 $u \rightarrow v_{p}$，$k$ 为满足 $v_{i} \rightarrow u$ 的最大正整数 $i$，则必有 $k<p$，且 $v_{k} \rightarrow u \rightarrow v_{k+1}$．
于是，存在长度为 $p+1$ 的圈 $v_{1} \rightarrow \cdots \rightarrow v_{k} \rightarrow u \rightarrow v_{k+1} \rightarrow \cdots \rightarrow v_{p} \rightarrow v_{1}$，矛盾．
从而，$p=n$，即图 $T$ 中有长度为 $n$ 的圈．
引理二：当 $n\geqslant 4$ 时，图 $T$ 有一个长度为 $n-1$ 的圈．
引理二的证明：由引理一，知图 $T$ 中有长度为 $n$ 的圈 $x_{1} \rightarrow x_{2} \rightarrow \cdots \rightarrow x_{n} \rightarrow x_{1}$．
无论 $x_{1} \rightarrow x_{3}$ 还是 $x_{3} \rightarrow x_{1}$，图 $T$ 中必存在长度不超过 $n-1$ 的圈，该圈的所有顶点生成图 $T$ 的一个强连通的真子图．
设图 $H$ 为图 $T$ 中顶点个数最大的一个强连通真子图，图 $H$ 的顶点为 $v_{1}, v_{2}, \cdots, v_{p}$．
用反证法证明：$p=n-1$．
假设 $p<n-1$．
任取 $u \notin\left\{v_{1}, v_{2}, \cdots, v_{p}\right\}$，设 $U_{1}=\left\{v \in T | v \rightarrow v_{1}\right\}, U_{2}=\left\{v \in T | v_{1} \rightarrow v\right\}$．
若 $u \in U_{1}$，则 $u \rightarrow v_{i}(1 \leqslant i \leqslant p)$（否则，$u, v_{1}, v_{2}, \cdots, v_{p}$ 生成 $p+1$ 阶强连通的真子图，与 $p$ 的最大性矛盾）．
类似地，若 $u \in U_{2}$，则 $v_{i} \rightarrow u(1 \leqslant i \leqslant p)$．
由于图 $T$ 是强连通的，故 $U_{1}, U_{2} \neq \varnothing$，且存在 $u_{1} \in U_{1}, u_{2} \in U_{2}$ 使得 $u_{2} \rightarrow u_{1}$．
则 $u_{1}, u_{2}, v_{1}, v_{2}, \cdots, v_{p-1}$ 生成 $p+1$ 阶强连通的真子图，与 $p$ 的最大性矛盾．
因此，$p=n -1$．
故对图 $H$ 应用引理一，知引理二的结论成立．
引理三：当 $n\geqslant 3$ 时，对任意整数 $m\geqslant n^2-3n+3$，存在非负整数 $ \lambda,\mu$，使得 $m=\lambda n+\mu(n-1)$．
引理三是数论中熟知的结果．
回到原题．
由引理 $1、2$，知图 $T$ 有一个长度为 $n$ 的圈 $C_1$ 和一个长度为 $n-1$ 的圈 $C_2$．对任意两位选手 $x,y$，由于图 $T$ 是强连通的，故能找到 $s(s\geqslant n)$ 位选手 $w_{1}, w_{2}, \cdots, w_{s}$，使得 $x=w_{1} \rightarrow w_{2} \rightarrow \cdots \rightarrow w_{s}=y$．
当整数 $m \geqslant n^{2}-2 n+3$ 时，$m-s \geqslant n^{2}-3 n+3$．
由引理三，知存在非负整数 $ \lambda,\mu$，使得 $\lambda n+\mu(n-1)=m-s$．
故圈 $C_2$ 至少包含 $x,y$ 之一．
若圈 $C_2$ 包含 $x$，则可用 $\lambda$ 个圈 $C_1$ 和 $\mu$ 个圈 $C_2$ 拼接成一条边数为 $m-s$ 的有向回路 $x=z_{1} \rightarrow z_{2} \rightarrow \cdots \rightarrow z_{m-s} \rightarrow x$．故 $x=z_{1} \rightarrow z_{2} \rightarrow \cdots \rightarrow z_{m-s} \rightarrow x=w_{1} \rightarrow w_{2}\rightarrow \cdots \rightarrow w_{s}=y$
从而，$z_{1}, z_{2}, \cdots, z_{m-s}, w_{1}, w_{2}, \cdots, w_{s}$ 为满足要求的长度为 $m$ 的选手序列．
若圈 $C_2$：包含 $y$，则可用 $\lambda$ 个圈 $C_1$ 和 $\mu$ 个圈 $C_2$，拼接成一条边数为 $m-s$ 的有向回路 $y \rightarrow z_{1} \rightarrow z_{2} \rightarrow \cdots \rightarrow z_{m-s}=y$．
故 $x=w_{1} \rightarrow w_{2} \rightarrow \cdots \rightarrow w_{s}=y \rightarrow z_{1} \rightarrow z_{2}\rightarrow \cdots \rightarrow z_{m-s}=y$．
从而，$w_{1}, w_{2}, \cdots, w_{s}, z_{1}, z_{2}, \cdots, z_{m-s}$ 为满足要求的长度为 $m$ 的选手序列．
因此，（1）得证．
（2）对任意一个强连通的 $n(n\geqslant 11)$ 阶竞赛图 $T$，设 $x \rightarrow y$ 为图 $T$ 的一条边．则从 $y$ 到 $x$ 的有向路至少有三个顶点，故，$m(T)\geqslant 13$．
下面证明：$2n$ 为最小可能数．
假设平面内 $N$ 条直线的并集包含 $S$，但不包含原点，设其方程为 $a_{i} x+b_{i} y+c_{i}=0(1 \leqslant i \leqslant N)$．
考虑多项式 $\displaystyle P(x, y)=\prod\limits_{i=1}^{N}\left(a_{i} x+b_{i} y+c_{i}\right)$．
则其阶为 $N$，且对任意 $(x,y)\in S$，有 $P(x, y)=0, P(0,0) \neq 0$．
记 $Q(y)=y(y-1) \cdots(y-n)$，并记 $R(x,y)$ 为 $P(x,y)$ 被 $Q(y)$ 除的余式．
由多项式 $Q(y)$ 以 $y=0,1, \cdots, n$ 为 $n+1$ 个零点，知 $P(x, y)=R(x, y)$ 对所有 $x, y \in\{0,1, \cdots, n\}$ 均成立．
注意到，$\operatorname{deg} Q(y)=n+1$．
故 $\operatorname{deg}_{y} R(x, y) \leqslant n$，且显然有 $N=\operatorname{deg} P(x, y) \geqslant \operatorname{deg} R(x, y)$．
将多项式 $R(x,y)$ 表示成 $y$ 的降幂形式 $R(x, y)=R_{n}(x) y^{n}+R_{n-1}(x) y^{n-1}+\cdots+R_{0}(x)$．
因为 $R(0,0)=P(0,0) \neq 0$，所以，$R(0, y)$ 不为零多项式．
又对于 $i \in\{1,2, \cdots, n\}$，当 $y=0,1, \cdots, n$ 时，均有 $R(i, y)=P(i, y)=0$．
这表明，$R(i,y)$ 至少有 $n+1$ 个根．
而 $\operatorname{deg} R(i, y) \leqslant n$，则 $R(i, y)$ 为零多项式．
故对于任意 $i \in\{1,2, \cdots, n\}, R_{n}(i)=0$．
于是，$R_n (x )$ 至少有 $n$ 个根．
而 $R_n(0)$ 不为零多项式，因此，$\operatorname{deg} R(x) \geqslant n$．
于是，$\operatorname{deg} R(x, y) \geqslant \operatorname{deg} R(x)+n \geqslant 2 n$．
进而，$N\geqslant 2n$．
综上，至少要 $2n$ 条直线才能满足题设条件．