设 $n$（$n\geqslant 4$）为正整数．$n$ 个人两两之间各打一场乒乓球比赛（每场比赛都分出胜负）．求 $n$ 的最小值，使得比赛结束后，总存在一个有序四人组 $(A_1 , A_2 , A_3 , A_4 )$，满足当 $1\leqslant i<j\leqslant 4$ 时，$A_i$ 胜 $A_j$．
【难度】
【出处】
2014中国东南数学奥林匹克试题(高一)
【标注】
【答案】
略
【解析】
首先证明，当 $n=8$ 时，总存在满足题意的有序四人组．
由于 $8$ 人之间共进行了 $C_8^2 =28$ 场比赛，必有一人胜了至少 $\left[\dfrac{28}{8}\right]=4$ 场，不妨设 $A_1$ 胜了 $a_1 , a_2 , a_3 , a_4$．在 $a_1 , a_2 , a_3 , a_4$ 之间共进行了 $6$ 场比赛，必有一人胜了其中至少 $\left[\dfrac{6}{4}\right]=2$ 场，不妨设 $a_1$ 胜 $a_2 , a_3$，又不妨设 $a_2$ 胜了 $a_3$，那么将 $A_2 , A_3 , A_4$ 分别取为 $a_1 , a_2 , a_3$，则有序四人组 $(A_1 , A_2 , A_3 , A_4)$ 满足条件．
下面证明，当 $n\leqslant 7$ 时未必存在满足条件的有序四人组．只需对 $n=7$ 予以否定即可．将 $7$ 个人记为 $b_1 , b_2 , \ldots , b_7$，约定 $b_{7+k}=b_k$．我们构造以下情形：
对 $i=1,2,\ldots,7$，令 $b_i$ 胜 $b_{i+1},b_{i+2},b_{i+4}$，但负于 $b_{i+3},b_{i+5},b_{i+6}$，这样恰好确定了每场比赛的胜负．假如存在符合题意的有序四人组 $(A_1 , A_2 , A_3 , A_4 )$，由于 $A_1$ 必是某个 $b_i$，故 $A_2 , A_3 , A_4$ 只能是 $b_{i+1},b_{i+2},b_{i+4}$ 这三人的排列，但因 $b_{i+1}$ 胜 $b_{i+2}$，$b_{i+2}$ 胜 $b_{i+4}$，$b_{i+4}$ 胜 $b_{i+1}$，故 $b_{i+1},b_{i+2},b_{i+4}$ 三人中没有一人可作为 $A_4$，矛盾．
综上所述，满足条件的 $n$ 的最小值为 $8$．
由于 $8$ 人之间共进行了 $C_8^2 =28$ 场比赛，必有一人胜了至少 $\left[\dfrac{28}{8}\right]=4$ 场，不妨设 $A_1$ 胜了 $a_1 , a_2 , a_3 , a_4$．在 $a_1 , a_2 , a_3 , a_4$ 之间共进行了 $6$ 场比赛，必有一人胜了其中至少 $\left[\dfrac{6}{4}\right]=2$ 场，不妨设 $a_1$ 胜 $a_2 , a_3$，又不妨设 $a_2$ 胜了 $a_3$，那么将 $A_2 , A_3 , A_4$ 分别取为 $a_1 , a_2 , a_3$，则有序四人组 $(A_1 , A_2 , A_3 , A_4)$ 满足条件．
下面证明，当 $n\leqslant 7$ 时未必存在满足条件的有序四人组．只需对 $n=7$ 予以否定即可．将 $7$ 个人记为 $b_1 , b_2 , \ldots , b_7$，约定 $b_{7+k}=b_k$．我们构造以下情形：
对 $i=1,2,\ldots,7$，令 $b_i$ 胜 $b_{i+1},b_{i+2},b_{i+4}$，但负于 $b_{i+3},b_{i+5},b_{i+6}$，这样恰好确定了每场比赛的胜负．假如存在符合题意的有序四人组 $(A_1 , A_2 , A_3 , A_4 )$，由于 $A_1$ 必是某个 $b_i$，故 $A_2 , A_3 , A_4$ 只能是 $b_{i+1},b_{i+2},b_{i+4}$ 这三人的排列，但因 $b_{i+1}$ 胜 $b_{i+2}$，$b_{i+2}$ 胜 $b_{i+4}$，$b_{i+4}$ 胜 $b_{i+1}$，故 $b_{i+1},b_{i+2},b_{i+4}$ 三人中没有一人可作为 $A_4$，矛盾．
综上所述，满足条件的 $n$ 的最小值为 $8$．
答案
解析
备注
