同余理論在單循環比賽中的應用

李 文，鄒 都

（平頂山學院 數學與信息科學學院，河南 平頂山 467000）

同余理論在單循環比賽中的應用

李 文，鄒 都

（平頂山學院 數學與信息科學學院，河南 平頂山 467000）

在文獻[4]給出的單循環比賽賽程編排方法的基礎上，為了使比賽更具觀賞性，利用同余理論對單循環比賽的賽程編排方法進行改進，并給出了具體證明.

同余理論；單循環比賽；賽程編排

單循環比賽的賽程編排存在著多種方法，比如“貝格爾編排法[1]”、“固定1逆時針輪轉法[2]”、“蛇形編排法[3]”等等.文獻[4]給出運用同余理論的相關知識來編排n支隊進行單循環比賽賽程的一種方法（具體賽程編排方法請參看文獻[4]第8章的內容）.

例1 利用文獻[4]給出的單循環比賽的賽程編排方法求有7個球隊進行單循環比賽的程序表.

解 此時n=7為奇數，增加一個編號為8的隊，凡是與第8隊比賽的隊即為輪空.循環比賽安排程序表如表1：

表1 n=7

文獻[4]給出的單循環比賽賽程編排的算法，能夠實現計算機對其的操作，在實際中有很強的可運用性，但是在某些情況下它又存在著相應的不足之處.以表1為例，不難發現上述編排方法的缺陷：(1)當比賽的球隊編號是按各隊的實力強弱及上年比賽的成績好壞而編排時，上述編排法確實存在著明顯的弊端：1、2號隊在第三輪比賽中相逢，使比賽的高潮過早出現，不能為全場比賽起到壓軸作用，這顯然不符合觀眾觀賞的需要，影響整個比賽的觀賞性.(2)當參賽隊數為奇數時，在實力相當且最強的兩隊1、2相遇之前，1號隊經歷了兩場比賽且第一場是與最弱隊比、第二場比賽又是輪空，這對2號隊顯然很不公平，使其能“黑馬”出現的希望變得更加渺茫.針對上述編排法存在的這兩點不足，我們試著對其進行某些方面的改進，使其既保持了上述編排方法的優點又能彌補一下它的不足，進而使得整個比賽更加完美和合理.

若參賽隊n為奇數時，我們把一個“假想的”隊A加到這n個球隊中，就有了n+1球隊.現在，在每一輪比賽中對這n+1個球隊進行安排，并且規定：凡被安排與隊A比賽的球隊就是輪空的球隊.這樣，n為奇數的情形即可轉化為n為偶數的情形.因此，在下面的討論中總假設n為偶數.

下面用同余理論給出改進后的n支隊進行單循環比賽的賽程編排方法，并證明只進行n-1輪比賽即可.

用i(1≤i≤n-1)來表示輪次，用xi(1≤i≤n-1)表示第i輪比賽中與隊x進行比賽的隊，則要給出所要求的單循環比賽的程序表時，只須確定出第i(1≤i≤n-1)輪比賽中與隊x比賽的隊xi，且xi滿足下列的兩點要求：

(i)當x≠n且

時，取xi滿足

(i i)當x=n時，取

顯然n≠ni.

證明 首先指出，在每一輪比賽中，不同球隊的比賽對手是不同的，即若x≠x'，則xi≠xi'(1≤i≤n-1)，分以下三種情況進行討論：

(a)若x與x'都不等于n，且x,x'都滿足式(1)時，xi與xi'由式(2)確定，由于1≤x,x'≤n-1，于是x-x'堍0(m o d n-1).由式(2)得

于是

因此得xi≠xi'.

(b)若x=n，x'=ni則xi=ni,xi'=n，顯然xi≠xi'.

(c)若x=n，但x'滿足(1)，則xi'可由式(2)定義，此時，如果xi=xi'=ni，那么由式(2)和(4)知，當i是偶數時，有

故

當i是奇數時，有

但是，根據對x'的假定，式(5)和式(6)都不能成立，因此xi≠xi'(1≤i≤n-1).

其次指出，每一個隊x在每一輪比賽中的對手都不是他自身，即對于1≤i≤n-1，必定x≠xi.事實上，當x=n時，由式(3)可知n≠ni；當1≤i≤n-1且式(1)滿足時，若x=xi，則由式(2)給出2 x≡x+xi≡n-i(m o d n-1).再根據一次同余式有解的充要條件和(2,n-1)=1可知：2 x≡n-i(m o d n-1)，在1≤x≤n-1內有且僅有一解.從而說明x≠xi.

最后指出，對于每一個確定的隊，它在各輪比賽中的對手是不同的，即當i1≠i2時必有xi1≠xi2(1≤i1,i2≤n-1)，分兩種情況討論：

①先看球隊n，如果

由式(3)可知，

因此i1=i2.

②再看球隊x(1≤x≤n-1)，如果xi1=xi2=n，則ni1=ni2(1≤i1, i2≤n-1)，因此由①中的討論可知i1=i2；如果xi1=xi2≠n，那么由式(2)得到

因此i1=i2.

以上討論說明，用上面的方法可以在n-1輪比賽中完

故成n個球隊的循環比賽.

例2 用“改進后的單循環賽的編排方法”求有7個球隊進行單循環比賽的程序表.

解 此時n=7為奇數，增加一個編號為8的隊，凡是與第8隊比賽的隊即為輪空.循環比賽安排程序表如表2：

表2 n=7

通過比較改進前后的兩種單循環賽的編排方法及表1、表2我們可以看出，改進后的編排方法不僅能夠保留改進前的編排方法的優點：便于實現計算機對其的操作，而且改進后的編排方法確實在一定程度上能夠避免改進前的編排方法中存在的一些不足.下面就以表1、表2為例來具體分析一下，從表1與表2的對比我們可以清晰的看到：(1)在第一輪中，實力相當的3、4隊相逢，可以作為開幕式的開幕戰，能夠吸引觀眾，提高觀眾的看賽熱情.(2)全賽的高潮放在了最后面的的三輪上，使比賽進行的波瀾起伏.(3)表2中不僅對1、2隊相當公平，而且對6、7號隊也是比較公平的，尤其是對2隊和7隊的出線能夠創造更大的可能性，使比賽進行的更加激烈，可觀賞性更強.由表1、表2相比的優缺點可以看出：改進后的單循環比賽的賽程編排方法不僅有利于“黑馬隊”的出現，使其取得的成績和平時的付出成正比，而且1、2號隊在比賽的倒數第三輪相遇，使比賽的高潮在適當的時候出現，可以提高觀眾的看賽熱情，使比賽更具觀賞性.

〔1〕董東風，肖波.論循環賽“貝格爾編排法”[J].長沙通信職業技術學院學報，2010，9(3):92-95.

〔2〕傅企明，趙成，劉繼領.增強循環制編排合理性的探索[J].中國體育科技，2007，43(2)：136-143.

〔3〕董東風，宋小春.循環賽中倒輪次編排方法的研究[J].長沙通信職業技術學院學報，2007，6(1)：93-96.

〔4〕王丹華,楊海文,劉詠梅.初等數論[M].北京:北京航空航天大學出版社,2008.

O 12-49

A

1673-260 X（2012）09-0003-02

平頂山學院校級教研項目（2010-YJ14）