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

楊玲

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

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

楊玲

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

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

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

0 引言

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

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

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

為了下面證明需要，先給出有關(guān)同余式的一些性質(zhì).

引理1[1]同余理論：設(shè)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 比賽程序表推導(dǎo)

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

來(lái)確定在第r輪比賽中，第x隊(duì)的對(duì)手是第y隊(duì).

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

則由（2）（3）式可得

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

這就說(shuō)明了每1個(gè)隊(duì)在每1輪比賽中對(duì)手是唯一的.

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

證明 設(shè)在第r輪比賽中，x隊(duì)的對(duì)手是y隊(duì)，y隊(duì)的對(duì)手是z隊(duì)，且x，y，z∈A，則

由（1）式有

則由（4）（5）式可得

又因?yàn)閤，z∈A，所以x=z.

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

（三）每1個(gè)隊(duì)在每1輪比賽中都和不同的對(duì)手進(jìn)行比賽.

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

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

故每1個(gè)隊(duì)在每1輪比賽中都和不同的對(duì)手進(jìn)行比賽.

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

證明 由（1）式有

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

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

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

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

又因?yàn)閤，y∈A，所以x=y.

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

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

于是，接下來(lái)的任務(wù)就是要對(duì)這個(gè)特殊的第N隊(duì)進(jìn)行像（一），（二），（三）的證明，即如下結(jié)論.

（四）第N個(gè)隊(duì)在每1輪比賽中，對(duì)手x是唯一的.

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

（一）每1個(gè)隊(duì)在每1輪比賽中，對(duì)手是唯一的.

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

由（1）式有

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

因?yàn)樽対M足（6）式這個(gè)例外的x隊(duì)與第N隊(duì)進(jìn)行比賽，所以N隊(duì)確定的對(duì)手是x隊(duì)，則為x隊(duì)確定的對(duì)手也是N隊(duì).

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

證明 假設(shè)在第s輪和第r輪中（s≠r）有

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

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

即第N隊(duì)在每1輪比賽中都和不同的對(duì)手進(jìn)行比賽.

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

2 比賽程序表編排

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

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

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

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

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

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

（責(zé)任編輯 鈕效鹍）

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ù)學(xué)教學(xué)研究.