$18$ 支足球队进行单循环赛，即每轮将 $18$ 支球队分成 $9$ 组，每组的两队赛一场，下一轮重新分组进行比赛，共赛 $17$ 轮，使得每队都与另外 $17$ 支队各赛一场．按任意可行的程序比赛了 $n$ 轮之后，总存在 $4$ 支球队，它们之间总共只赛了 $1$ 场．求 $n$ 的最大可能值．
【难度】
【出处】
2002第17届CMO试题
【标注】
【答案】
略
【解析】
考察如下的比赛程序：
$1 .(1,2)(3,4)(5,6)(7,8)(9,18)(10,11)(12,13)(14,15)(16,17)$
$2 .(1,3)(2,4)(5,7)(6,9)(8,17)(11,12)(11,13)(14,16)(15,18)$
$3 .(1,4)(2,5)(3,6)(8,9)(7,16)(10,13)(11,14)(12,15)(17,18)$
$4.(1,5)(2,7)(3,8)(4,9)(6,15)(10,14)(11,16)(12,17)(13,18)$
$5.(1,6)(2,8)(3,9)(4,7)(5,14)(10,15)(11,17)(12,18)(13,16)$
$6 .(1,7)(2,9)(3,5)(6,8)(4,13)(10,16)(11,18)(12,18)(15,17)$
$7.(1,8)(2,6)(4,5)(7,9)(3,12)(10,17)(11,15)(13,14)(16,18)$
$8 .(1,9)(3,7)(4,6)(5,8)(2,11)(10,18)(12,16)(13,15)(14,17)$
$9 .(2,3)(4,8)(5,9)(6,7)(1,10)(11,12)(13,17)(14,18)(15,16)$
$10. (1,11)(2,12)(3,13)(4,14)(5,15)(6,16)(7,17)(8,18)(9,10)$
$11.(1,12)(2,13)(3,14)(4,15)(5,1 s)(s, 17)(7,18)(8,10)(9,11)$
$12.(1,13)(2,14)(3,15)(4,16)(5,17)(s, 18)(7,10)(8,11)(9,12)$
$\cdots\cdots$
$17.(1,18)(2,10)(3,11)(4,12)(5,13)(6,14)(7,15)(8,16)(9,17)$
将前 $9$ 队称为 $A$ 组，后 $9$ 队称为 $B$ 组．易见 $9$ 轮之后，凡同组两队均已赛过．所以任何 $4$ 队之间至少已赛过两场，当然不满足题 中要求．
如果把上述程序颠倒过来，然后按新序进行比赛，则 $8$ 轮过后，同组任何两队均未赛过，每个队都是与另一组中 $9$ 支队中的 $8$ 支队各赛 $1$ 场．这时同组 $4$ 支队之间一场未赛，而不全同组的 $4$ 队之间至少已赛了两场，当然都不能满足题中要求．
以上所述表明，所求 $n$ 的最大可能值不大于 $7$．
设已进行了 $7$ 轮比赛且任何 $4$ 队都不满足题中要求．
选取已赛过一场的两队 $A_{1}$ 和 $A_{2}$，于是，每队都和另外 $6$ 队比赛过，两个队至多与另外 $12$ 支队赛过．从而，至少有 $4$ 队 $B_{1}, B_{2},B_{3}, B_{4}$ 与 $A_{1}, A_{2}$ 均未赛过．由反证假设知，$B_{1}, B_{2}, B_{3},B_{4}$ 两两均已赛过．
$B_{1}$ 和 $B_{2}$ 两队在 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ $4$ 队之间各赛了 $3$ 场．从而，每队都与另 $14$ 支队中的 $4$ 队各赛 $1$ 场．这又导致至少有 $6$ 队 $C_{1},C_{2}, \cdots, C_{6}$ 与 $B_{1}, B_{2}$ 均未赛过．由反证假设知 $C_{1}, C_{2}, \cdots, C_{6}$ 两两均已赛过．
$C_{1}$ 和 $C_{2}$ 两队在 $\left\{C_{1}, C_{2}, \cdots, C_{6}\right\}$ 中各赛了 $5$ 场从而，每队都 与另外 $12$ 支队中的 $2$ 队各赛 $1$ 场，所以至少有 $8$ 队 $D_{1}, D_{2}, \cdots, D_{8}$ 与 $C_{1}, C_{2}$ 均未赛过．由反证假设又知这 $8$ 支队之间两两均已赛过．这样一来，$D_{1}, D_{2}$ 与另外 $10$ 支队均未赛过．由于只赛了 $7$ 轮，另外 $10$ 支队中必有两队 $E_1$ 和 $E_2$ 尚未赛过．于是，$\left\{D_{1}, D_{2}, E_{1}, E_{2}\right\}$ 之间总共进行了 $1$ 场比赛，此与反证假设矛盾．
综上可知，最多能进行 $7$ 轮比赛．
$1 .(1,2)(3,4)(5,6)(7,8)(9,18)(10,11)(12,13)(14,15)(16,17)$
$2 .(1,3)(2,4)(5,7)(6,9)(8,17)(11,12)(11,13)(14,16)(15,18)$
$3 .(1,4)(2,5)(3,6)(8,9)(7,16)(10,13)(11,14)(12,15)(17,18)$
$4.(1,5)(2,7)(3,8)(4,9)(6,15)(10,14)(11,16)(12,17)(13,18)$
$5.(1,6)(2,8)(3,9)(4,7)(5,14)(10,15)(11,17)(12,18)(13,16)$
$6 .(1,7)(2,9)(3,5)(6,8)(4,13)(10,16)(11,18)(12,18)(15,17)$
$7.(1,8)(2,6)(4,5)(7,9)(3,12)(10,17)(11,15)(13,14)(16,18)$
$8 .(1,9)(3,7)(4,6)(5,8)(2,11)(10,18)(12,16)(13,15)(14,17)$
$9 .(2,3)(4,8)(5,9)(6,7)(1,10)(11,12)(13,17)(14,18)(15,16)$
$10. (1,11)(2,12)(3,13)(4,14)(5,15)(6,16)(7,17)(8,18)(9,10)$
$11.(1,12)(2,13)(3,14)(4,15)(5,1 s)(s, 17)(7,18)(8,10)(9,11)$
$12.(1,13)(2,14)(3,15)(4,16)(5,17)(s, 18)(7,10)(8,11)(9,12)$
$\cdots\cdots$
$17.(1,18)(2,10)(3,11)(4,12)(5,13)(6,14)(7,15)(8,16)(9,17)$
将前 $9$ 队称为 $A$ 组，后 $9$ 队称为 $B$ 组．易见 $9$ 轮之后，凡同组两队均已赛过．所以任何 $4$ 队之间至少已赛过两场，当然不满足题 中要求．
如果把上述程序颠倒过来，然后按新序进行比赛，则 $8$ 轮过后，同组任何两队均未赛过，每个队都是与另一组中 $9$ 支队中的 $8$ 支队各赛 $1$ 场．这时同组 $4$ 支队之间一场未赛，而不全同组的 $4$ 队之间至少已赛了两场，当然都不能满足题中要求．
以上所述表明，所求 $n$ 的最大可能值不大于 $7$．
设已进行了 $7$ 轮比赛且任何 $4$ 队都不满足题中要求．
选取已赛过一场的两队 $A_{1}$ 和 $A_{2}$，于是，每队都和另外 $6$ 队比赛过，两个队至多与另外 $12$ 支队赛过．从而，至少有 $4$ 队 $B_{1}, B_{2},B_{3}, B_{4}$ 与 $A_{1}, A_{2}$ 均未赛过．由反证假设知，$B_{1}, B_{2}, B_{3},B_{4}$ 两两均已赛过．
$B_{1}$ 和 $B_{2}$ 两队在 $\left\{B_{1}, B_{2}, B_{3}, B_{4}\right\}$ $4$ 队之间各赛了 $3$ 场．从而，每队都与另 $14$ 支队中的 $4$ 队各赛 $1$ 场．这又导致至少有 $6$ 队 $C_{1},C_{2}, \cdots, C_{6}$ 与 $B_{1}, B_{2}$ 均未赛过．由反证假设知 $C_{1}, C_{2}, \cdots, C_{6}$ 两两均已赛过．
$C_{1}$ 和 $C_{2}$ 两队在 $\left\{C_{1}, C_{2}, \cdots, C_{6}\right\}$ 中各赛了 $5$ 场从而，每队都 与另外 $12$ 支队中的 $2$ 队各赛 $1$ 场，所以至少有 $8$ 队 $D_{1}, D_{2}, \cdots, D_{8}$ 与 $C_{1}, C_{2}$ 均未赛过．由反证假设又知这 $8$ 支队之间两两均已赛过．这样一来，$D_{1}, D_{2}$ 与另外 $10$ 支队均未赛过．由于只赛了 $7$ 轮，另外 $10$ 支队中必有两队 $E_1$ 和 $E_2$ 尚未赛过．于是，$\left\{D_{1}, D_{2}, E_{1}, E_{2}\right\}$ 之间总共进行了 $1$ 场比赛，此与反证假设矛盾．
综上可知，最多能进行 $7$ 轮比赛．
答案
解析
备注
