math-ai/BlueMO

1{2    "source_file": "./raw_volume-zh/volume11/exercise10.tex",3    "problem_type": "calculation",4    "problem": "问题7. 有 20 个队参加全国足球冠军赛, 为了使已比赛过的任何三个队中都有两个队互相比赛过,最少要进行多少场比赛?",5    "solution": "设经过 $S$ 场比赛可使已经比赛过的任何三个队中都有两个队互相比赛过.\n我们选出其中一个比赛场次最少的队 $A$, 设 $A$ 队比赛了 $k$ 场, 于是与 $A$ 比赛过的 $k$ 个队 $B_1, B_2, \\cdots, B_k$ 都至少比赛了 $k$ 场, 从与 $A$ 没有比赛过的 $19-k$ 个队 $C_1, C_2, \\cdots, C_{19-k}$ 中任取两队 $C_i, C_j(1 \\leqslant i<j \\leqslant 19-k)$, 则 $A, C_i, C_j$ 中必有两队比赛过一场.\n但 $A$ 与 $C_i, A$ 与 $C_j$ 没有比赛过, 故只可能 $C_i$ 与 $C_j$ 比赛一场.\n因此 $C_1, C_2, \\cdots, C_{19-k}$ 中每个队至少与其余 $18-k$ 个队比赛过一场.\n从而 20 个队比赛场次的总和至少为 $k(k+1)+(19-k)(18- k)$, 上述计数中每场比赛计算了两次.\n所以 $S \\geqslant \\frac{1}{2}[k(k+1)+(19-k)(18- k)]=(k-9)^2+90 \\geqslant 90$. 另一方面, 如果将 20 个队平分为两组, 同组 10 个队中任何两队安排一场比赛, 不同组的任何两队不安排比赛, 则一共比赛了 $2 \\mathrm{C}_{10}^2=90$ 场, 任何三个队中必有 $\\left[\\frac{3-1}{2}\\right]+1=2$ 个队属于同一组, 它们互相比赛过一队.\n综上可知, 最少要安排 90 场比赛.",6    "remark": "",7    "figures": []8}