40 个球队参加比赛，为使任何三队中至少有两队相互交手过，至少需进行几场比赛？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，
欢迎大家一起来想想如何解答：

40個隊伍參加比賽,為使三隊中至少有兩隊相互交手過,至少需進行幾場比賽?

ans: 380

luyuanhong

[这个贴子最后由luyuanhong在 2013/03/24 07:47pm 第 2 次编辑]

题  40 个球队参加比赛，为使任何三队中至少有两队相互交手过，至少需进行几场比赛？

解  将 40 个球队平均分成两组，每一组 20 个球队。
    在每一组的内部，任何两队之间都要进行一场比赛，这样每一组的 20 个队共要进行
20×(20-1)/2 = 20×19/2 = 190 场比赛，两个组共要进行 190*2 = 380 场比赛。
    这时，从中任意选取三个队，至少有两个队是属于同一组的，这两个队必定比赛过，
所以必定满足题目的要求。
    下面证明：要满足题目要求，至少要进行 380 场比赛。
    如果任何两个队之间都进行比赛，共要进行 40×(40-1)/2 = 40×39/2 = 780 场比赛。
假设比赛场次少于 380 ，则 780 场比赛中至少要取消 401 场比赛。把 40 个队看作是平
面上 40 个点，两队之间如果取消比赛，就在两点之间连一条线段，一共要连 401 条线段。
可以证明一个命题：如果平面上有 n 个点，作 [n^2/4]+1 条连线，则其中必有 3 条连线
构成一个三角形（证明见下面的帖子）。现在恰好有 [40^2/4]+1 = 401 条线段，所以必定
可以找到 3 条连线构成一个三角形，也就是说，可以找到 3 个队相互之间都没有比赛过，
这就与题目的要求发生矛盾，所以，比赛场次不能少于 380 场。  

luyuanhong