同餘與球賽的賽程
單循環賽程是運動比賽中常見的比賽模式,這模式可使每一隊均有機會與別的隊伍比賽,從而選出一隊最強的作冠軍。然而若比賽隊伍眾多,編訂賽程則變得繁複了。原來同餘 (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-1 是奇數,必定有一隊找不到配合,那便與 N 隊比賽。
因為在模 (Modulo) N-1 下,只有一數可與特定的 i 相加而得結果 k ,故不會出現在同一輪中有兩隊同配一隊的情況;再者 k 是取由 1 至 N-1 ,即要使特定的 i 和一些數加起來的結果剛巧等如由 1 至 N-1 ,由於除 i 以外便只有 N-1 隊,即 i 得和其餘每一隊比賽,即不會出現有兩隊沒有比賽的情況了。由此可知,此法可行。
例:編一個九隊比賽隊伍的單循環比賽賽程。
答:把九隊依次編上 1 至 9號,第 10 號則為虛設隊伍,若該輪比賽被編與虛設隊伍比賽,即該輪輪空 (以 X 表示)。
隊伍 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
第一輪 |
9 |
8 |
7 |
6 |
X |
4 |
3 |
2 |
1 |
第二輪 |
X |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
第三輪 |
2 |
1 |
9 |
8 |
7 |
X |
5 |
4 |
3 |
第四輪 |
3 |
X |
1 |
9 |
8 |
7 |
6 |
5 |
4 |
第五輪 |
4 |
3 |
2 |
1 |
9 |
8 |
X |
6 |
5 |
第六輪 |
5 |
4 |
X |
2 |
1 |
9 |
8 |
7 |
6 |
第七輪 |
6 |
5 |
4 |
3 |
2 |
1 |
9 |
X |
7 |
第八輪 |
7 |
6 |
5 |
X |
3 |
2 |
1 |
9 |
8 |
第九輪 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
X |
如何,是否方便了?別說是廿隊足球隊伍的雙循環比賽,順帶一提,雙循環也好,三循環也好,不過是把同一比賽模式運作多一次或多兩次而已。別說是廿隊足球隊伍的雙循環比賽,三十隊也難不倒大家了。
參考文獻及網址:
裴定一, 祝躍飛, "剩餘類環" §2.2 取自 算法數論, 北京:科學出版社, 頁19-21, 2002