同余理論在單循環(huán)比賽中的應(yīng)用

李 文，鄒 都

（平頂山學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，河南 平頂山 467000）

同余理論在單循環(huán)比賽中的應(yīng)用

李 文，鄒 都

（平頂山學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，河南 平頂山 467000）

在文獻(xiàn)[4]給出的單循環(huán)比賽賽程編排方法的基礎(chǔ)上，為了使比賽更具觀賞性，利用同余理論對(duì)單循環(huán)比賽的賽程編排方法進(jìn)行改進(jìn)，并給出了具體證明.

同余理論；單循環(huán)比賽；賽程編排

單循環(huán)比賽的賽程編排存在著多種方法，比如“貝格爾編排法[1]”、“固定1逆時(shí)針輪轉(zhuǎn)法[2]”、“蛇形編排法[3]”等等.文獻(xiàn)[4]給出運(yùn)用同余理論的相關(guān)知識(shí)來編排n支隊(duì)進(jìn)行單循環(huán)比賽賽程的一種方法（具體賽程編排方法請(qǐng)參看文獻(xiàn)[4]第8章的內(nèi)容）.

例1 利用文獻(xiàn)[4]給出的單循環(huán)比賽的賽程編排方法求有7個(gè)球隊(duì)進(jìn)行單循環(huán)比賽的程序表.

解 此時(shí)n=7為奇數(shù)，增加一個(gè)編號(hào)為8的隊(duì)，凡是與第8隊(duì)比賽的隊(duì)即為輪空.循環(huán)比賽安排程序表如表1：

表1 n=7

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

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

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

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

(i)當(dāng)x≠n且

時(shí)，取xi滿足

(i i)當(dāng)x=n時(shí)，取

顯然n≠ni.

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

(a)若x與x'都不等于n，且x,x'都滿足式(1)時(shí)，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)定義，此時(shí)，如果xi=xi'=ni，那么由式(2)和(4)知，當(dāng)i是偶數(shù)時(shí)，有

故

當(dāng)i是奇數(shù)時(shí)，有

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

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

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

①先看球隊(duì)n，如果

由式(3)可知，

因此i1=i2.

②再看球隊(duì)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個(gè)球隊(duì)的循環(huán)比賽.

例2 用“改進(jìn)后的單循環(huán)賽的編排方法”求有7個(gè)球隊(duì)進(jìn)行單循環(huán)比賽的程序表.

解 此時(shí)n=7為奇數(shù)，增加一個(gè)編號(hào)為8的隊(duì)，凡是與第8隊(duì)比賽的隊(duì)即為輪空.循環(huán)比賽安排程序表如表2：

表2 n=7

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

〔1〕董東風(fēng)，肖波.論循環(huán)賽“貝格爾編排法”[J].長沙通信職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2010，9(3):92-95.

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

〔3〕董東風(fēng)，宋小春.循環(huán)賽中倒輪次編排方法的研究[J].長沙通信職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2007，6(1)：93-96.

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

O 12-49

A

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

平頂山學(xué)院校級(jí)教研項(xiàng)目（2010-YJ14）