楊玲

（涼山衛(wèi)生學校 數(shù)理化教研室，四川 西昌 615000）

同余理論在單循環(huán)比賽程序表編排中的應用

楊玲

（涼山衛(wèi)生學校 數(shù)理化教研室，四川 西昌 615000）

單循環(huán)比賽需要詳細確定每1輪的參賽隊對陣，應用同余理論可以很好地完成單循環(huán)比賽程序表的編排.

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

0 引言

所謂單循環(huán)比賽，就是所有參加比賽的隊都相互比賽1次，最后按照所有比賽過程中勝負場數(shù)與得分多少排列名次.這是1種比較公平合理的競賽方法，在比賽隊伍數(shù)量不多、競賽時間充足的情況下多采用這種方法.

假設有N個隊參加比賽，當N為奇數(shù)時，在每一輪比賽中總有1支隊伍要輪空；當N為偶數(shù)時就不會出現(xiàn)輪空的情況.為了解決這一問題，可以在N為奇數(shù)時人為加進1個隊，使比賽隊伍數(shù)量變?yōu)榕紨?shù).然后安排一個N+1個隊的比賽程序表，在每1輪比賽中，被安排和加進的隊就輪空.這樣就可以假設有偶數(shù)個隊進行比賽，并按國內(nèi)比賽或世界性比賽慣例，給每個隊1個編號.

一般國內(nèi)比賽，各隊以上屆比賽所取得的名次數(shù)作為代號，如第1名為“1”，第2名為“2”，依次類推；世界性比賽則大都采用東道主代號為“1”，上屆第1名為“2”，依次類推.這樣自然就給加進的隊1個最大的編號.并且很容易知道，在單循環(huán)比賽中，每個隊所要進行的比賽的總場數(shù)為N-1，比賽輪次為N-1輪.

為了下面證明需要，先給出有關同余式的一些性質.

引理1[1]同余理論：設0≠m∈Z，a，b∈Z，如果m∣b-a，就稱b同余于a模m，記作 b≡a（mod m）.

引理2[1]（i）a≡a（mod m）；

（ii）若b≡a（mod m），則a≡b（mod m）；

（iii）若c≡b（mod m），b≡a（mod m），則c≡a（mod m）.引理3[2]（i）若a≡b（mod m），c≡d（mod m），則a+c≡b+d（mod m）；

（ii）若a+b≡c（mod m），則a≡c-b（mod m）.

引理4[3]若ac≡bc（mod m），（c，m）=1則a≡b（mod m）.

1 比賽程序表推導

現(xiàn)假定x，r∈A={1，2，…，N-1}，則可用同余式

來確定在第r輪比賽中，第x隊的對手是第y隊.

但我們的任務是要使不同的隊在每1輪比賽中有不同的對手，讓所有參加比賽的隊都相互比賽1次.下面就（1）式證明以下幾點.

則由（2）（3）式可得

所以y≡z（mod N-1），又y，z∈A，所以y=z.

這就說明了每1個隊在每1輪比賽中對手是唯一的.

（二）在每1輪比賽中，若為x隊確定的對手是y隊，則為y隊確定的對手也是x隊.

證明 設在第r輪比賽中，x隊的對手是y隊，y隊的對手是z隊，且x，y，z∈A，則

由（1）式有

則由（4）（5）式可得

又因為x，z∈A，所以x=z.

即在每1輪比賽中，若為x隊確定的對手是y隊，則為y隊確定的對手也是x隊.

（三）每1個隊在每1輪比賽中都和不同的對手進行比賽.

證明 設第x隊在第r輪和第s輪的對手分別為y，z，且x，r，s∈A，r≠s，則由（1）式有

若y=z，則r=s，出現(xiàn)矛盾，所以y≠z.

故每1個隊在每1輪比賽中都和不同的對手進行比賽.

但當（1）式中x=y時，這種情況就違反了比賽規(guī)則.而事實上，這種情況又是不可避免的，現(xiàn)在就來證明這種情況的存在.

證明 由（1）式有

這里x，r∈A，并且僅有1個這樣的x滿足（6）式.

若y∈A，也滿足（6）式，則2y≡r（mod N-1）.

又2x≡r（mod N-1），所以2x≡2y（mod N-1）.

因為N-1是奇數(shù)，所以（2，N-1）=1，x≡y（mod N-1）.

又因為x，y∈A，所以x=y.

即在每1輪比賽中，滿足（4）式中的第x隊是唯一的.并且很容易知道（6）式在集合A中總有一解為

從而，除了滿足（6）式的那個例外的隊外，通過（1）式，對集合A中的每1個隊，都已經(jīng)指定了它在第r輪比賽中的對手，而讓滿足（6）式這個例外的隊與第N個隊進行比賽.

于是，接下來的任務就是要對這個特殊的第N隊進行像（一），（二），（三）的證明，即如下結論.

（四）第N個隊在每1輪比賽中，對手x是唯一的.

前面已證明在每1輪比賽中，滿足（6）式中的第x隊是唯一的.所以第N個隊在每1輪比賽中，對手x是唯一的.

（一）每1個隊在每1輪比賽中，對手是唯一的.

證明 ∵在第r輪比賽中，對x隊確定對手y隊，z隊，且x，y，z∈A，則

由（1）式有

（五）在每1輪比賽中，若為N隊確定的對手是x隊，則為x隊確定的對手也是N隊.

因為讓滿足（6）式這個例外的x隊與第N隊進行比賽，所以N隊確定的對手是x隊，則為x隊確定的對手也是N隊.

（六）第N隊在每,1輪中都和不同的對手進行比賽.

證明 假設在第s輪和第r輪中（s≠r）有

這里x，y，s，r∈A，若x=y，則s≡r（mod N-1）.

又因為s，r∈A，所以s=r，出現(xiàn)矛盾，因此x≠y.

即第N隊在每1輪比賽中都和不同的對手進行比賽.

以上就證明了（1）式能夠使在每1輪比賽中，不同的隊有不同的對手，而且在整個比賽中，對于有N個隊參加的比賽，各個隊的對手均為N-1個隊，又比賽總共N-1場，則每兩隊恰好比賽了1次.這就是單循環(huán)比賽，所有參加比賽的隊都相互比賽1次.

2 比賽程序表編排

現(xiàn)在用（1）式來安排單循環(huán)比賽的程序表.現(xiàn)就一般情況給出這張程序表，即來排一張有N個隊參加的單循環(huán)賽程序表，這里N為偶數(shù)，所要比賽的輪次為N-1輪，即r∈{1，2，…，N-1}.按照（1）式得到的詳細單循環(huán)賽程序表見表1.

表1 單循環(huán)賽對陣表

以上結果表明，同余理論可以很好地應用到單循環(huán)比賽程序表的編排中.

[1]閔嗣鶴，嚴士健.初等數(shù)論[M].北京：高等教育出版社，2004.

[2]潘承洞，潘承彪.初等代數(shù)數(shù)論[M].濟南：山東大學出版社，1991.

[3][美]杜德利.基礎數(shù)論[M].上海：上?？茖W技術出版社，1980.

（責任編輯 鈕效鹍）

Application of Congruence Theory in Round-robin Tournament Schedule

YANG Ling
（Department of Math，Physics and Chemistry，Lianshang Health School，Xichang，Sichuan 615000，China）

A round-robin tournament is a competition in which each contestant meets all other contestants in turn.Congruence theory can be applied to generate the schedule fast and effectively.

congruence theory；round-robin tournament；schedule；arrangement

O156

A

1673-1972（2015）03-0028-03

2015-02-15

楊玲（1982-），女，四川西昌人，助教，主要從事數(shù)學教學研究.