一类比赛程序的极值问题.doc

一类比赛程序的极值问题.doc1 一类比赛程序的极值问题比赛程序的安排工作成为选拔人才的一个重要渠道,各负责人都在寻求方便可行的方案时,国家有关权威人士基于组合数学的决策理论,认真研讨,在 2002 年中国数学奥林匹克第 3 题给出了一个比赛程序安排的方案。 2002 年中国数学奥林匹克竞赛试题 3 如下: 18 支足球队进行单循环赛,即每轮将 18 球队分成 9 组,每组的两队赛一场, 下一轮重新分组进行比赛, 共赛 17轮, 使得每队都与另外 17支队各赛一场, 按任意可行的程序比赛 n 轮之后, 总存在 4 支球队, 它们之间总共只赛 1 场,求 n 的最大可能值。我们现在再来看一下 2n 支球队的情况。假设 2n 支足球队进行单循环赛, 即每轮将 2n 支球队分成 n组, 每组的两队赛一场, 下一轮重新分组进行比赛, 共赛( 2n-1 )轮, 使得每队都与另外( 2n-1 ) 支队各赛一场, 按任意可行的程序比赛 m 轮之后, 总存在 4 支球队,它们之间总共只赛 1 场, m 的最大可能值是多少呢? 解: m 的最大可能值为 n-2 。证明如下: (1) 首先证明存在一种赛程, 使得( n-1 ) 轮之后, 在任意 4 支球队中,要么一场未赛,要么至少赛两场,构造赛程如下: 将 2n 支球队平均分成两组: A 组: A1、 A2、…、 An; 2 B 组: B1、 B2、…、 Bn。记 Ai+n=Ai , Bi+n=Bi , i=1 ,2,…,n。并且设第 k 轮是 Ai与 Bi+k 比赛, i=1 ,2,…,n, k=1 ,2,…,( n-1 ) ,则( n-1 )轮之后,任意两支球队都没有进行两轮或两轮以上的比赛, 且每轮恰有 n 场比赛, 每队都参加, 因此这样的赛程合理。按照这样的赛程( n-1 )轮之后,同组的任意两支球队都没赛过, Ai 与 Bi 也没赛过, i=1 ,2,…,n 。其它任意两支球队只赛一场。此时对于其中任意 4 支球队有如下 4 种情况: ①这4 支球队同在 A 组或同在 B 组,则它们之间从未赛过;②它们中有1 支在 A 组、 3 支在 B 组,则 A 组的那支球队与 B 组的那 3 支球队至少进行两场比赛;③A 组和 B 组中各有两支球队。此时对于 A 组中的两支球队中的任意一支,它至少与 B 组中的两支球队中的一支进行比赛。此时这 4 支球队之间至少进行两场比赛;④这4 支球队中 3 支在 A 组, 1 支在 B组, 同②的考虑,知它们之间至少进行两场比赛。综合①,②,③,④, 对于任意 4 支球队, 它们之间一场未赛或赛两场。即不可能只进行 1 场比赛。所以 m=n-1 不合要求。其次对于 m 不小于 n, 仍将这 2n 支球队分成上述证明中的 A、B 两组, 每组 n 支球队。此时必存在一种赛程使每组内的任意两支球队都赛过。这样一来,对于任意 4 支球队,不管它们以何种方式取自于 A、B 两组,则它们之间至少要赛两场。以上所述表明,所求 m 的值不大于 n-2 。(2 )下面证明 m=n-2 是可以达到的。只须证明以任意的方式赛 n-2 3 轮之后,总存在 4 支球队,它们之间只赛一场。设已进行了( n-2 )轮比赛且任何 4 队都不满足题中要求。选取已赛过一场的两队 A1和 A2, 于是, 每队都和另外( n-3 ) 队比赛过,