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

一类比赛程序的极值问题 　　比赛程序的安排工作成为选拔人才的一个重要渠道，各负责人都在寻求方便可行的方案时，国家有关权威人士基于组合数学的决策理论，认真研讨，在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; 　　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轮之后，总存在4支球队，它们之间只赛一场。 　　设已进行了（n-2）轮比赛且任何4队都不满足题中要求。 　　选取已赛过一场的两队A1和A2，于是，每队都和另外（n-3）队比赛过，两个队至多与另外（2n-6）支队赛过，从而，至少有4队B1、B2、B3、B4与A1、A2两队均未赛过，由反证假设知，B1、B2、B3和B4两两已赛过。 　　B1和B2两队在{B1、B2、B3、B4}4队之间各赛了3场，从而，每队都与另（2n-4）支队中的（n-5）队各赛1场，这又导致至少有6队C1、C2、…、C6与B1、B2均未赛过，由反证假设知C1、C2、…、C6两两均已赛过。 　　如此循环下去，最后可得两种情况： 　　①若n为奇数，则可得，、…、Dn-3两两均已赛过。D1和D2两队在{D1、D2、…、Dn-3}中各赛了（n-4）场，从而，每队都与另外（n+3）支队中的2队各赛1场，所以，至少有（n-1）支队E1、E2、…、En-1与D1、D2均未赛过，由反证假设又知这（n-1）队之间两两均已赛过，这样一来，E1、E2与另外（n+1）支队均未赛过，由于只赛了（n-2）轮，另外（n+1）支队中必有两队F1和F2尚未赛过，于是，{E1、E2、F1、F2}之间总共只进行1场比赛，此与反证假设矛盾。 　　②若n为偶数，则可得，D1、D2、…、Dn-4两两均已赛过。D1和D2两队在{D1、D2、…、Dn-4}中各赛了（n-5）场，从而，每队都与另外（n+4）支队中的3队各赛1场，所以，至少有（n-2）支队E1、E2、…、En-2与D1、D2均未赛过，由反证假设又知E1、E2、…、En-2两两均已赛过。 　　E1和E2两队在{E1、E2、…、En-2}中各赛了（n-3）场，从而，每队都与另外（n+2）支队中的1队进行比赛，这导致了有另外n支队与E1、E2均未赛过，由于只赛（n-2）轮，另外n支队中必有两队F1和F2尚未赛过，于是，{E1