同餘與球賽的賽程

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

 

Hosted by www.Geocities.ws

1