有 $n(n\geqslant 3)$ 名乒乓球选手参加循环赛，每两名选手之间恰比赛一次（比赛无平局）。赛后发现，可以将这些选手排成一圈，使得对于任意三名选手 $A$、$B$、$C$，若 $A$、$B$ 在圈上相邻，则选手 $A$、$B$ 中至少有一人战胜了选手 $C$ 。求 $n$ 的所有可能值。
【难度】
【出处】
2011第10届CGMO试题
【标注】
【答案】
$n$ 的所有可能值为所有大于或等于3的奇数
【解析】
$n$ 的所有可能值为大于或等于3的奇数。理由如下
当 $n$ 是大于或等于3的奇数时，设 $n=2k+1$，$n$ 名选手编号为 ${{A}_{1}},{{A}_{2}},\cdots,{{A}_{2k+1}}$ 构造满足条件的比赛结果如下：
选手 ${{A}_{i}}(1\leqslant i\leqslant 2k+1)$ 战胜了选手 ${{A}_{i+2}},{{A}_{i+4}},\cdots,{{A}_{i+2k}}({{A}_{2k+1+j}}={{A}_{j}})$，输给了其他选手。将这些选手按照 ${{A}_{1}},{{A}_{2}},\cdots ,{{A}_{2k+1}}$ 的顺序顺时针排成一圈，对于任意三名选手 $A$、$B$、$C$（$A$、$B$ 在圈上相邻），不妨设 $A={{A}_{t}}$，$B={{A}_{t+1}}$，$C={{A}_{t+r}}$（$1\leqslant t\leqslant 2k+1$，$2\leqslant r\leqslant 2k$），则 $r$ 与 $r-1$ 中有一个为不大于 $2k$ 的偶数。故选手 $A$、$B$ 中恰有一人战胜了选手 $C$ 。
当 $n$ 是大于或等于4的偶数时，假设题目所述的情况出现。则将这 $n$ 名选手按照在圈上的位置顺时针记为 ${{A}_{1}},{{A}_{2}},\cdots,{{A}_{n}}$，不妨设选手 ${{A}_{1}}$ 战胜了选手 ${{A}_{2}}$ 。由题目条件知选手 ${{A}_{2}}$、${{A}_{3}}$ 中至少有一人战胜了选手 ${{A}_{1}}$，故选手 ${{A}_{3}}$ 战胜了选手 ${{A}_{1}}$ 。再由选手 ${{A}_{1}}$、${{A}_{2}}$ 中至少有一人战胜选手 ${{A}_{3}}$，可知选手 ${{A}_{2}}$ 战胜了选手 ${{A}_{3}}$ 。依此类推，知对任意的 $i(1\leqslant i\leqslant n)$，选手 ${{A}_{i}}$ 战胜了选手 ${{A}_{i+1}}({{A}_{n+1}}={{A}_{1}})$ 。对于每名选手 ${{A}_{i}}$，他输给了选手 ${{A}_{i-1}}$ $({{A}_{0}}={{A}_{n}})$，将剩下的 $n-2$ 人两两相邻配对，由条件知选手 ${{A}_{i}}$ 至少输掉了 $\frac{n-2}{2}$ 场，再加上输给选手 ${{A}_{i-1}}$ 的一场至少输掉 $\frac{n}{2}$ 场。因此，$n$ 名选手共输掉至少 $\frac{{{n}^{2}}}{2}$ 场。
但这与 $C_{n}^{2}=\frac{n(n-1)}{2}<\frac{{{n}^{2}}}{2}$ 矛盾。
综上，$n$ 的所有可能值为所有大于或等于3的奇数。
当 $n$ 是大于或等于3的奇数时，设 $n=2k+1$，$n$ 名选手编号为 ${{A}_{1}},{{A}_{2}},\cdots,{{A}_{2k+1}}$ 构造满足条件的比赛结果如下：
选手 ${{A}_{i}}(1\leqslant i\leqslant 2k+1)$ 战胜了选手 ${{A}_{i+2}},{{A}_{i+4}},\cdots,{{A}_{i+2k}}({{A}_{2k+1+j}}={{A}_{j}})$，输给了其他选手。将这些选手按照 ${{A}_{1}},{{A}_{2}},\cdots ,{{A}_{2k+1}}$ 的顺序顺时针排成一圈，对于任意三名选手 $A$、$B$、$C$（$A$、$B$ 在圈上相邻），不妨设 $A={{A}_{t}}$，$B={{A}_{t+1}}$，$C={{A}_{t+r}}$（$1\leqslant t\leqslant 2k+1$，$2\leqslant r\leqslant 2k$），则 $r$ 与 $r-1$ 中有一个为不大于 $2k$ 的偶数。故选手 $A$、$B$ 中恰有一人战胜了选手 $C$ 。
当 $n$ 是大于或等于4的偶数时，假设题目所述的情况出现。则将这 $n$ 名选手按照在圈上的位置顺时针记为 ${{A}_{1}},{{A}_{2}},\cdots,{{A}_{n}}$，不妨设选手 ${{A}_{1}}$ 战胜了选手 ${{A}_{2}}$ 。由题目条件知选手 ${{A}_{2}}$、${{A}_{3}}$ 中至少有一人战胜了选手 ${{A}_{1}}$，故选手 ${{A}_{3}}$ 战胜了选手 ${{A}_{1}}$ 。再由选手 ${{A}_{1}}$、${{A}_{2}}$ 中至少有一人战胜选手 ${{A}_{3}}$，可知选手 ${{A}_{2}}$ 战胜了选手 ${{A}_{3}}$ 。依此类推，知对任意的 $i(1\leqslant i\leqslant n)$，选手 ${{A}_{i}}$ 战胜了选手 ${{A}_{i+1}}({{A}_{n+1}}={{A}_{1}})$ 。对于每名选手 ${{A}_{i}}$，他输给了选手 ${{A}_{i-1}}$ $({{A}_{0}}={{A}_{n}})$，将剩下的 $n-2$ 人两两相邻配对，由条件知选手 ${{A}_{i}}$ 至少输掉了 $\frac{n-2}{2}$ 场，再加上输给选手 ${{A}_{i-1}}$ 的一场至少输掉 $\frac{n}{2}$ 场。因此，$n$ 名选手共输掉至少 $\frac{{{n}^{2}}}{2}$ 场。
但这与 $C_{n}^{2}=\frac{n(n-1)}{2}<\frac{{{n}^{2}}}{2}$ 矛盾。
综上，$n$ 的所有可能值为所有大于或等于3的奇数。
答案
解析
备注
