一類比賽程序的極值問題

黃雙美

比賽程序的安排工作成為選拔人才的一個重要渠道，各負(fù)責(zé)人都在尋求方便可行的方案時，國家有關(guān)權(quán)威人士基于組合數(shù)學(xué)的決策理論，認(rèn)真研討，在2002年中國數(shù)學(xué)奧林匹克第3題給出了一個比賽程序安排的方案。

2002年中國數(shù)學(xué)奧林匹克競賽試題3如下：

18支足球隊(duì)進(jìn)行單循環(huán)賽，即每輪將18球隊(duì)分成9組，每組的兩隊(duì)賽一場，下一輪重新分組進(jìn)行比賽，共賽17輪，使得每隊(duì)都與另外17支隊(duì)各賽一場，按任意可行的程序比賽n輪之后，總存在4支球隊(duì)，它們之間總共只賽1場，求n的最大可能值。

我們現(xiàn)在再來看一下2n支球隊(duì)的情況。

假設(shè)2n支足球隊(duì)進(jìn)行單循環(huán)賽，即每輪將2n支球隊(duì)分成n組，每組的兩隊(duì)賽一場，下一輪重新分組進(jìn)行比賽，共賽（2n-1）輪，使得每隊(duì)都與另外（2n-1）支隊(duì)各賽一場，按任意可行的程序比賽m輪之后，總存在4支球隊(duì)，它們之間總共只賽1場，m的最大可能值是多少呢？

解：m的最大可能值為n-2。證明如下：

（1）首先證明存在一種賽程，使得（n-1）輪之后，在任意4支球隊(duì)中，要么一場未賽，要么至少賽兩場，構(gòu)造賽程如下：

將2n支球隊(duì)平均分成兩組：

A組：A1、A2、…、An;

B組：B1、B2、…、Bn。

記Ai+n=Ai，Bi+n=Bi，i=1，2，…，n。并且設(shè)第k輪是Ai與Bi+k比賽，i=1，2，…，n，k=1，2，…，（n-1），則（n-1）輪之后，任意兩支球隊(duì)都沒有進(jìn)行兩輪或兩輪以上的比賽，且每輪恰有n場比賽，每隊(duì)都參加，因此這樣的賽程合理。

按照這樣的賽程（n-1）輪之后，同組的任意兩支球隊(duì)都沒賽過，Ai與Bi也沒賽過，i=1，2，…，n。其它任意兩支球隊(duì)只賽一場。此時對于其中任意4支球隊(duì)有如下4種情況：

①這4支球隊(duì)同在A組或同在B組，則它們之間從未賽過;②它們中有1支在A組、3支在B組，則A組的那支球隊(duì)與B組的那3支球隊(duì)至少進(jìn)行兩場比賽;③A組和B組中各有兩支球隊(duì)。此時對于A組中的兩支球隊(duì)中的任意一支，它至少與B組中的兩支球隊(duì)中的一支進(jìn)行比賽。此時這4支球隊(duì)之間至少進(jìn)行兩場比賽;④這4支球隊(duì)中3支在A組，1支在B組，同②的考慮，知它們之間至少進(jìn)行兩場比賽。

綜合①，②，③，④，對于任意4支球隊(duì)，它們之間一場未賽或賽兩場。即不可能只進(jìn)行1場比賽。所以m=n-1不合要求。

其次對于m不小于n，仍將這2n支球隊(duì)分成上述證明中的A、B兩組，每組n支球隊(duì)。此時必存在一種賽程使每組內(nèi)的任意兩支球隊(duì)都賽過。這樣一來，對于任意4支球隊(duì)，不管它們以何種方式取自于A、B兩組，則它們之間至少要賽兩場。

以上所述表明，所求m的值不大于n-2。

（2）下面證明m=n-2是可以達(dá)到的。只須證明以任意的方式賽n-2輪之后，總存在4支球隊(duì)，它們之間只賽一場。

設(shè)已進(jìn)行了（n-2）輪比賽且任何4隊(duì)都不滿足題中要求。

選取已賽過一場的兩隊(duì)A1和A2，于是，每隊(duì)都和另外（n-3）隊(duì)比賽過，兩個隊(duì)至多與另外（2n-6）支隊(duì)賽過，從而，至少有4隊(duì)B1、B2、B3、B4與A1、A2兩隊(duì)均未賽過，由反證假設(shè)知，B1、B2、B3和B4兩兩已賽過。

B1和B2兩隊(duì)在{B1、B2、B3、B4}4隊(duì)之間各賽了3場，從而，每隊(duì)都與另（2n-4）支隊(duì)中的（n-5）隊(duì)各賽1場，這又導(dǎo)致至少有6隊(duì)C1、C2、…、C6與B1、B2均未賽過，由反證假設(shè)知C1、C2、…、C6兩兩均已賽過。

如此循環(huán)下去，最后可得兩種情況：

①若n為奇數(shù)，則可得，、…、Dn-3兩兩均已賽過。D1和D2兩隊(duì)在{D1、D2、…、Dn-3}中各賽了（n-4）場，從而，每隊(duì)都與另外（n+3）支隊(duì)中的2隊(duì)各賽1場，所以，至少有（n-1）支隊(duì)E1、E2、…、En-1與D1、D2均未賽過，由反證假設(shè)又知這（n-1）隊(duì)之間兩兩均已賽過，這樣一來，E1、E2與另外（n+1）支隊(duì)均未賽過，由于只賽了（n-2）輪，另外（n+1）支隊(duì)中必有兩隊(duì)F1和F2尚未賽過，于是，{E1、E2、F1、F2}之間總共只進(jìn)行1場比賽，此與反證假設(shè)矛盾。

②若n為偶數(shù)，則可得，D1、D2、…、Dn-4兩兩均已賽過。D1和D2兩隊(duì)在{D1、D2、…、Dn-4}中各賽了（n-5）場，從而，每隊(duì)都與另外（n+4）支隊(duì)中的3隊(duì)各賽1場，所以，至少有（n-2）支隊(duì)E1、E2、…、En-2與D1、D2均未賽過，由反證假設(shè)又知E1、E2、…、En-2兩兩均已賽過。

E1和E2兩隊(duì)在{E1、E2、…、En-2}中各賽了（n-3）場，從而，每隊(duì)都與另外（n+2）支隊(duì)中的1隊(duì)進(jìn)行比賽，這導(dǎo)致了有另外n支隊(duì)與E1、E2均未賽過，由于只賽（n-2）輪，另外n支隊(duì)中必有兩隊(duì)F1和F2尚未賽過，于是，{E1、E2、F1、F2}之間總共只進(jìn)行1場比賽，此與反證假設(shè)矛盾。

綜上（1），（2）知，m最大可能值為（n-2）。

綜上可得以下定理：2n支足球隊(duì)進(jìn)行單循環(huán)賽，即每輪將2n支球隊(duì)分成n組，每組的兩隊(duì)賽一場，下一輪重新分組進(jìn)行比賽，共賽（2n-1）輪，使得每隊(duì)都與另外（2n-1）支隊(duì)各賽一場，按任意可行的程序比賽m輪之后，總存在4支球隊(duì)，它們之間總共只賽1場，m的最大可能值為（n-2）。

接下來我們看看將2002年中國數(shù)學(xué)奧林匹克競賽第3題中的18推到2n的情況。

由此可見，看似簡單的比賽程序安排問題，其實(shí)充溢著濃厚的數(shù)學(xué)氣息，上面的講座只是就幾個簡單的情況而言，對于一般的情況，即2n支足球隊(duì)進(jìn)行單循環(huán)賽，按任意可行的程序比賽m輪之后，總存在k支球隊(duì)，它們之間總共只賽l場，求m的最大可能值的計(jì)算，還需要做進(jìn)一步的討論。