2007第6届CGMO试题

• 知识点

  >

  二试组合部分

$f\left( m \right)\text{=}2m-3$

先证明两个引理。 引理1：当 $n\geqslant m$ 时，如果 $n$ 个棋手的赛况具有性质 $P\left( m \right)$，则必有一个棋手全胜。 引理1的证明：当 $n\text{=}m$ 时，命题显然成立。假设命题对 $n$ 成立。则对 $n+1$ 个棋手，从中任取 $n$ 个棋手，由归纳假设，这 $n$ 个棋手必有一个棋手全胜。不妨设 ${{A}_{1}}\text{,}{{A}_{2}}\text{,}\cdots\text{,}{{A}_{n}}$ 中 ${{A}_{1}}$ 全胜。对另一个棋手 ${{A}_{n+1}}$：若 ${{A}_{1}}$ 胜 ${{A}_{n+1}}$，则在 $n+1$ 个棋手中，${{A}_{1}}$ 全胜；若 ${{A}_{1}}$ 平 ${{A}_{n+1}}$，考察棋手 ${{A}_{1}}\text{,}{{A}_{2}}\text{,}\cdots\text{,}{{A}_{n-1}}\text{,}{{A}_{n+1}}$，这个棋手中没有人全胜，不可能；若 ${{A}_{n+1}}$ 胜 ${{A}_{1}}$，考察棋手 ${{A}_{1}},{{A}_{3}},{{A}_{4}}\cdots,{{A}_{n}},{{A}_{n+1}}$，全胜的只能是 ${{A}_{n+1}}$，即 ${{A}_{n+1}}$ 胜 ${{A}_{3}}\text{,}{{A}_{4}}\text{,}\cdots\text{,}{{A}_{n}}\text{,}{{A}_{n+1}}$ 。同理，${{A}_{n+1}}$ 也胜 ${{A}_{2}}$ 。因此，在这 $n+1$ 个棋手中 ${{A}_{n+1}}$ 全胜。由归纳原理知，命题对任意 $n\geqslant m$ 成立。 类似地可证：引理2：当 $n\geqslant m$ 时，如果 $n$ 个棋手的赛况具有性质 $P\left( m \right)$，则必有一个棋手全败。 回到原题。接下来证明：当 $n\ge2m-3$ 时，所有棋手的得分必各不相同。 由引理1，有一个棋手 ${{A}_{1}}$ 胜了其余 $n-1$ 个棋手，有一个棋手 ${{A}_{2}}$ 胜了除 ${{A}_{1}}$ 外的 $n-2$ 个棋手，……有一个棋手 ${{A}_{n-m+1}}$ 胜了除 ${{A}_{1}}\text{,}{{A}_{2}}\text{,}\cdots\text{,}{{A}_{n-m}}$ 外的 $m-1$ 个棋手。 由引理2，有一个棋手 ${{A}_{n}}$ 负于其余 $n-1$ 个棋手，有一个棋手 ${{A}_{n-1}}$ 负于除 ${{A}_{n}}$ 外的 $n-2$ 个棋手，……有一个棋手 ${{A}_{n-m+3}}$ 负于除 ${{A}_{n}}\text{,}{{A}_{n-1}}\text{,}\cdots\text{,}{{A}_{n-m+4}}$ 外的 $n-m+2$ 个棋手，另外还有一名棋手为 ${{A}_{n-m+2}}$ 。 这样，这 $n$ 个棋手 ${{A}_{1}}\text{,}{{A}_{2}}\text{,}\cdots\text{,}{{A}_{n}}$ 编号小的棋手都战胜了编号大的棋手，因此他们的得分为 $n-1\text{,}n-2\text{,}\cdots\text{,}1\text{,}0$ 各不相同。 对 $n\text{=}2m-4$，设 $n$ 个棋手水平为 $1\text{,}2\text{,}\cdots \text{,}m-3\text{,}m-2\text{,}m-1\text{,}\cdots\text{,}2m-5$，其中，编号小的棋手胜编号大的棋手，编号相等的棋手打平。则对任取 $m$ 个棋手，必有一个最小编号为 $i\left( 1\leqslant i\leqslant m-3 \right)$，另一个最大编号为 $j\left( m-1\leqslant j\leqslant 2m-5 \right)$，从而，在这 $m$ 个棋手中编号为 $i$ 的棋手全胜，编号为 $j$ 的棋手全败。所以这 $n$ 个棋手的赛况具有性质 $P\left(m \right)$，但其中有两个棋手的得分相同。综上，$f\left( m \right)\text{=}2m-3$ 。