同餘與球賽的賽程

單循環賽程是運動比賽中常見的比賽模式,這模式可使每一隊均有機會與別的隊伍比賽,從而選出一隊最強的作冠軍。然而若比賽隊伍眾多,編訂賽程則變得繁複了。原來同餘 (Congruent) 的小知識可在這編訂賽程中幫忙,便我們把繁複的問題化簡。

設有 N 隊比賽隊伍參加一單循環比賽,我們不如假定 N 是偶數,因為若 N 是一奇數,我們可多加一虛設隊伍,若該輪比賽被編與虛設隊伍比賽,即該輪輪空 (不用比賽) 。

那 N 隊我們依次編上 1、2、3、......、N 號,它們共需進行 N-1 輪比賽,每輪比賽 N/2 場。我們只要定第 k 輪 (k 介乎 1 與 N-1 之間) 比賽中,比賽的兩隊 i 和 j ( i 和 j 介乎 1 與 N-1 之間) 滿足條件

i + j = k (mod N-1)

這時若 N 是偶數的話,把第 N 隊抽起暫不作編排。而因為 N-1 是奇數,必定有這樣的一個情況:對於某一組出現 i = j,那 第 i 隊便與第 N 隊比賽了。若 N 為奇數的話,那第 i 隊便在該輪輪空了。

因為在模 (Modulo) N-1 下,只有一數可與特定的 i 相加而得結果 k ,故不會出現在同一輪中有兩隊同配一隊的情況;再者 k 是取由 1 至 N-1 ,即要使特定的 i 和一些數加起來的結果剛巧等如由 1 至 N-1 ,由於除 i 以外便只有 N-1 隊,即 i 得和其餘每一隊比賽,即不會出現有兩隊沒有比賽的情況了。由此可知,此法可行。

 

例:編一個九隊比賽隊伍的單循環比賽賽程。

答:把九隊依次編上 1 至 9號,第 10 號則為虛設隊伍,即取 N = 10。若該輪比賽被編與虛設隊伍比賽,即該輪輪空 (以 X 表示)。

 
第一隊
第二隊
第三隊
第四隊
第五隊
第六隊
第七隊
第八隊
第九隊
第一輪 (k=1)
9
8
7
6
X
4
3
2
1
第二輪 (k=2)
X
9
8
7
6
5
4
3
2
第三輪 (k=3)
2
1
9
8
7
X
5
4
3
第四輪 (k=4)
3
X
1
9
8
7
6
5
4
第五輪 (k=5)
4
3
2
1
9
8
X
6
5
第六輪 (k=6)
5
4
X
2
1
9
8
7
6
第七輪 (k=7)
6
5
4
3
2
1
9
X
7
第八輪 (k=8)
7
6
5
X

3

2
1
9
8
第九輪 (k=0)
8
7
6
5
4
3
2
1
X

如何,是否方便了?別說是廿隊足球隊伍的雙循環比賽,順帶一提,雙循環也好,三循環也好,不過是把同一比賽模式運作多一次或多兩次而已。別說是廿隊足球隊伍的雙循環比賽,三十隊也難不倒大家了。

 

參考文獻及網址

裴定一, 祝躍飛, "剩餘類環" §2.2 取自 算法數論, 北京:科學出版社, 頁19-21, 2002

 

Free Web Hosting