同餘與球賽的賽程
單循環賽程是運動比賽中常見的比賽模式,這模式可使每一隊均有機會與別的隊伍比賽,從而選出一隊最強的作冠軍。然而若比賽隊伍眾多,編訂賽程則變得繁複了。原來同餘 (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