某次体育比赛，每两名选手都进行一场比赛，每场比赛一定决出胜负．通过比赛确定优秀选手．选手 $A$ 被确定为优秀选手的条件是：对任何其他选手 $B$，或者 $A$ 胜 $B$；或者存在选手 $C $，$ C $ 胜 $ B $，$ A $ 胜 $ C$．
如果按上述规则确定的优秀选手只有一名，求证：这名选手胜所有其他的选手．
如果按上述规则确定的优秀选手只有一名，求证：这名选手胜所有其他的选手．
【难度】
【出处】
1987第2届CMO试题
【标注】
【答案】
略
【解析】
证法一
为了叙述方便，约定若 $ A $ 胜 $ C $，$ C $ 胜 $ B$，则称 $A$ 间接胜 $B$．
（1）先证按题设规则必存在优秀选手．因选手人数有限，故必存在胜场次数最多的选手，设其中之一为 $A$．若 $A$ 胜其余选手，则 $A$ 为优秀选手无疑；若 $A$ 胜 $B_{1}, B_{2}, \cdots, B_{k}$，但败于 $B^{\prime}_{1}, B_{2}^{\prime}, \cdots,B^{\prime}_{r}$（$k,r$ 为正整数），则 $B_{i}^{\prime}(i=1,2, \cdots, r)$ 必不能全胜 $B_{1}, B_{2}, \cdots,B_{k}$，否则 $B^{\prime}_{i}$ 至少胜 $k+1$ 场，比 $A$ 胜场数还多，引出矛盾．从而至少有一 $B_{j} $ 胜 $B^{\prime}_i$，因此 $A$ 间接胜 $B^{\prime}_i$（即 $A$ 胜 $B_{j}, B_{j}$ 胜 $B_{i}^{\prime}$），按规则，$A$ 为优秀选手．
（2）再证若优秀选手唯一，则必全胜其他选手．设 $A$ 为唯一的优秀选手，若 $A$ 胜 $B_{1}, B_{2}, \cdots, B_{k}$，但败于 $B^{\prime}_{1}, B^{\prime}_{2}, \cdots, B_{r}^{\prime}$（$k,r$ 为正整数），则由（1）知 $B^{\prime}_{1}, B^{\prime}_{2}, \cdots, B^{\prime}$ 共 $r$ 人中也有"局部的"优秀选手 $B^{\prime}_{i}$，从而 $B^{\prime}_{i}$ 胜或间接胜 $B^{\prime}_{1}, B^{\prime}_{2}, \cdots, B_{r}^{\prime}$ 中其余选手，并且 $B^{\prime}_{i}$ 胜 $A$，$A$ 胜 $B_{1}, B_{2}, \cdots, B_{k}$，即 $B^{\prime}_{i}$ 胜或间接胜 $B_{1}, B_{2}, \cdots, B_{k}$，按规则，$B^{\prime}_{i}$ 也为优秀选手，与 $A$ 的唯一性矛盾．所以 $A$ 全胜其他选手．证毕．
证法二
对人数 $n$ 采用数学归纳法
$n=1,2$ 时命题显然成立．设命题对 $n$ 人成立．现在有 $n+1$ 人的集合 $\alpha$，$A$ 为 $\alpha$ 中唯一的优秀选手．设 $A$ 败于 $B$，$\alpha$ 去掉 $B$ 后得到 $n$ 人的集合 $\beta$，易见 $A$ 仍为 $\beta$ 中的优秀选手．设 $\beta$ 中另有一优秀选手 $A^\prime$，则因 $\alpha$ 中优秀选手唯一，故 $A^\prime$ 不能胜 $B$，也不能间接胜 $B$．设 $\beta$ 中有选手 $C$ 胜 $B$，则 $C$ 胜 $A^\prime$（否则 $A^\prime$ 间接胜 $B$，引出矛盾），但 $A^\prime$ 为 $\beta$ 中的优秀选手，故有 $D$，$A^\prime$ 胜 $D$，$D$ 胜 $C$；此 $D$ 不能胜 $B$（否则 $A^\prime$ 间接胜 $B$，矛盾），从而 $B$ 胜 $D$，$D$ 胜 $C$．所以 $B$ 胜或间接胜 $\beta$ 中全部选手，这样 $B$ 也成为 $\alpha$ 中的优秀选手，引出矛盾．此矛盾表明 $A$ 亦为 $\beta$ 中唯一的优秀选手，由归纳假设法，$A$ 胜 $\beta$ 中所有其他选手，但 $B$ 胜 $A$，故 $B$ 胜或间接胜 $\beta$ 中全部选手，$B$ 也为 $\alpha$ 中的优秀选手，引出矛盾．所以 $A$ 战胜 $\alpha$ 中其余全部选手．故命题成立．
为了叙述方便，约定若 $ A $ 胜 $ C $，$ C $ 胜 $ B$，则称 $A$ 间接胜 $B$．
（1）先证按题设规则必存在优秀选手．因选手人数有限，故必存在胜场次数最多的选手，设其中之一为 $A$．若 $A$ 胜其余选手，则 $A$ 为优秀选手无疑；若 $A$ 胜 $B_{1}, B_{2}, \cdots, B_{k}$，但败于 $B^{\prime}_{1}, B_{2}^{\prime}, \cdots,B^{\prime}_{r}$（$k,r$ 为正整数），则 $B_{i}^{\prime}(i=1,2, \cdots, r)$ 必不能全胜 $B_{1}, B_{2}, \cdots,B_{k}$，否则 $B^{\prime}_{i}$ 至少胜 $k+1$ 场，比 $A$ 胜场数还多，引出矛盾．从而至少有一 $B_{j} $ 胜 $B^{\prime}_i$，因此 $A$ 间接胜 $B^{\prime}_i$（即 $A$ 胜 $B_{j}, B_{j}$ 胜 $B_{i}^{\prime}$），按规则，$A$ 为优秀选手．
（2）再证若优秀选手唯一，则必全胜其他选手．设 $A$ 为唯一的优秀选手，若 $A$ 胜 $B_{1}, B_{2}, \cdots, B_{k}$，但败于 $B^{\prime}_{1}, B^{\prime}_{2}, \cdots, B_{r}^{\prime}$（$k,r$ 为正整数），则由（1）知 $B^{\prime}_{1}, B^{\prime}_{2}, \cdots, B^{\prime}$ 共 $r$ 人中也有"局部的"优秀选手 $B^{\prime}_{i}$，从而 $B^{\prime}_{i}$ 胜或间接胜 $B^{\prime}_{1}, B^{\prime}_{2}, \cdots, B_{r}^{\prime}$ 中其余选手，并且 $B^{\prime}_{i}$ 胜 $A$，$A$ 胜 $B_{1}, B_{2}, \cdots, B_{k}$，即 $B^{\prime}_{i}$ 胜或间接胜 $B_{1}, B_{2}, \cdots, B_{k}$，按规则，$B^{\prime}_{i}$ 也为优秀选手，与 $A$ 的唯一性矛盾．所以 $A$ 全胜其他选手．证毕．
证法二
对人数 $n$ 采用数学归纳法
$n=1,2$ 时命题显然成立．设命题对 $n$ 人成立．现在有 $n+1$ 人的集合 $\alpha$，$A$ 为 $\alpha$ 中唯一的优秀选手．设 $A$ 败于 $B$，$\alpha$ 去掉 $B$ 后得到 $n$ 人的集合 $\beta$，易见 $A$ 仍为 $\beta$ 中的优秀选手．设 $\beta$ 中另有一优秀选手 $A^\prime$，则因 $\alpha$ 中优秀选手唯一，故 $A^\prime$ 不能胜 $B$，也不能间接胜 $B$．设 $\beta$ 中有选手 $C$ 胜 $B$，则 $C$ 胜 $A^\prime$（否则 $A^\prime$ 间接胜 $B$，引出矛盾），但 $A^\prime$ 为 $\beta$ 中的优秀选手，故有 $D$，$A^\prime$ 胜 $D$，$D$ 胜 $C$；此 $D$ 不能胜 $B$（否则 $A^\prime$ 间接胜 $B$，矛盾），从而 $B$ 胜 $D$，$D$ 胜 $C$．所以 $B$ 胜或间接胜 $\beta$ 中全部选手，这样 $B$ 也成为 $\alpha$ 中的优秀选手，引出矛盾．此矛盾表明 $A$ 亦为 $\beta$ 中唯一的优秀选手，由归纳假设法，$A$ 胜 $\beta$ 中所有其他选手，但 $B$ 胜 $A$，故 $B$ 胜或间接胜 $\beta$ 中全部选手，$B$ 也为 $\alpha$ 中的优秀选手，引出矛盾．所以 $A$ 战胜 $\alpha$ 中其余全部选手．故命题成立．
答案
解析
备注
