Chang.pdf

Size: px

Start display at page:

Download "Chang.pdf"

凌会狄
7 years ago
Views:

1 環以顏色從黑白棋到多色棋的循環探討新竹市國立高級中學張維哲指導老師 : 吳智傑 Abstract Assume there are N black/whte chess peces placed around a crcle. We perform the followng process to change the placement of the N peces. If two adjacent peces are of the same color, we nsert one black pece n between; otherwse, we nsert a whte pece. After that, we remove all the orgnal peces. In ths way, we can create a new placement of N black/whte peces. We observe that after repeatng the process, at some teraton, the new placement of the peces wll be the same as a placement n a earler teraton. Ths s called a cycle. We use Pascal trangle and Euler theorem to derve formula for the cycle length. In addton to the model of black/ whte peces, we further nvestgate the multple color cases and ts correspondng cycle. We dvde the multple color case nto two sub-cases. One has the number of colors to be a prme, whle the other has the number of colors to be a composte number. We found that the prme color case can be solved smlarly to the two color case. When the number of peces s gven, we are able to fnd the correspondng cycle of the prme color problem. For the composte number color case, we provde a new defnton.((is ths necessary?)) By usng the cycle calculaton of the prme color problem, we expect the soluton can be found by usng matrces to represent the relatonshp between color changes. 中文摘要假設有 N 顆棋子 ( 黑色或白色 ) 置於一圓周上, 我們進行以下的動作改變此 N 顆棋子的排列 : 如果相鄰兩棋子為同色, 則在兩棋所在圓弧中點上放一顆黑棋, 異色則放上白棋, 然後移除原先的 N 顆棋子如此在圓周上可產生一組新的 N 顆棋子發現如果重複執行數次以上的動作, 新圓周上的 N 顆棋子排列方式, 必定與過往某次相同, 因而會有週期的現象發生我們可運用巴斯卡三角型與尤拉定理推導公式, 計算所有不同棋子數的週期除了雙色 ( 黑白 ) 棋, 我們進一步研究了多色棋的循環, 分成質數色棋與合數色棋進行討論, 質數色用類似的操作產生的循環規則, 以及不同與對應的週期藉由質數色棋的週期數計算和數色棋的週期之後我們期望以矩陣來表示棋子的顏色變化關係簡介. 研究動機在學校的數學專科教室中, 偶然間翻到數林外傳系列 - 磨光變換, 當中的某一節介紹到有道很優美的競賽試題 :2 n 顆棋子均勻的分佈在一個圓周上, 黑白兩色, 如果相鄰兩棋子為同色, 則在兩棋所在圓弧中點上放一顆黑棋, 異色則放上白棋, 然後把原先的那顆棋子拿走求證 : 不論此 2 n 顆棋子顏色分布為何, 經過若干次操作後必可使圓周上放的全是同色為了讓黑白棋能以代數形式做運算, 我們將黑白棋分別表示為 0 和, 因此每兩相鄰棋子間變換的關係就可以表示成 0( 黑 )+( 白 )= ( mod 2 ), 即為一黑棋一白棋時, 於下一步動作將在兩棋間放一顆白棋並移走原來兩棋 ; 同理模二下同餘 0 時即表同色中間放置黑棋那麼, 除了 2 n 顆棋子以外的棋子數會產生類似的結果嗎? 如果不會全部變成同色, 各棋子的變化情況為有限的結果, 應當會產生循環的變化因此我們試圖尋找棋子的運算規則, 並期望能找出一般化的結果

2 .2 研究目的. 找出黑白棋的棋子數 m 與週期 T m 的關係 2. 研究巴斯卡三角形與黑白棋運算方法的聯結 3. 推廣到質數 p 種顏色棋的棋子數 m 與週期 T p m 的關係 4. 推廣到合數 n 種顏色棋的棋子數 m 與週期 T n m 的關係.3 研究設備及器材 EXCEL C++.4 名詞定義. 模 n 表示任何整數被 n 除後的餘數值 2. 在 {0,, 2,...,n } 可重複任取 m(m > ) 個數均勻放置在一圓周上, 以數列 {a,a 2,...,a m } 表示, 相鄰兩數之和模 n 後得新的數放置在兩數中點, 並將原 m 個數拿掉, 產生新的數列, 稱為一操作, 即 b a + a + (mod n) 3. 圓周上任意放置 m(m > ) 顆多色棋, 在經過 T + z 次操作後的棋子排列位置為第 z 次操作後的排列相同, 稱 m 顆多色棋的循環次數為 T 次此時最小循環次數 T 稱為該排列下的週期當排列成順時針方向旋轉 r 個位置時, 則稱順向提升 r 格 2 研究內容 2. 兩色棋我們首先尋找兩色棋一般顆棋時, 週期與顏色的變化有沒有週期性的關係現在我們針對一般初始值 {a,a 2,,a m } 以順時針方向紀錄位置, 經過第一次操作後的 {b,b 2,,b m }, 將滿足 b a + a + (mod 2) 以下圖為例, 可表示成 {0,, 0, 0}, 並與 {0, 0,, 0} {0, 0, 0, } {, 0, 0, 0} 視為相同的排列, 但 {0, 0,, 0} 為 {0,, 0, 0} 順向提升一格 2

3 於是我們先用 Excel 整理出符合題意的表示方式, 透過 Excel 的表格對於我們找尋循環的規律有很大的幫助以初始排列 {, 0, 0,...,0} 為例, 利用 Excel 進行模擬在 22 顆棋中, 先將第一行的數字列到 23, 輸入初始值, 而 23 的位置等於的位置, 模擬成一個圓上 22 顆棋的排列下一行的值等於相鄰兩數之和模 2( A 3 A 2 + B 2 (mod 2) ), 把表格往下拉, 找出與它有相同排列的下一行, 便能計算週期為 62 及排列位置順向提升 2 格, 如下表所示統計不同棋子數與週期關係做成下表, 進行觀察棋子數週期順向提升棋子數週期順向提升

4 又當我們改變初始條件時, 週期將會改變例如, 當六顆棋的初始排列為 0000 的週期為, 會是 2 的因數其原因解釋如下 : 如果初始排列為 {, 0, 0,...,0} 所對應的週期為 T, 我們將任意初始排列拆成 {, 0, 0,...,0} {0,, 0,...,0} {0, 0,,...,0} {0, 0, 0,...,0, } 的和, 各個排列經由 T 次操作後, 均會產生循環因此, 任何排列所對應的週期均為 T 的因數接著我們的討論將以初始排列為 {, 0, 0,...,0} 所對應週期與棋子數的關係 : 初始 : 經二次操作後 : 經三次操作後 : 4

5 因此, 可利用數學歸納法得知, 圓周上 m 顆棋子經過若干次操作後, 新的各個位置上 {a,a 2,...,a m } 的係數恰為巴斯卡三角形各列的值觀察上圖, 若係數為奇數, 模二後同餘 ; 當係數為偶數時, 模二後同餘 0, 即原係數會視為 0, 因為無論或 0 乘上偶數倍都會變成偶數, 所以棋子於運算中不會被運算例如 :( a + 2a 2 + a 3 a + a 3 (mod 2) ) 因此, 我們決定將巴斯卡三角形模二, 得引理 2... 模 2 後的巴斯卡三角形中, 第 2 n 列的數字全為當 n = 0 時, 第 2 n = 列的數字為, 引理成立假設當 n = k 時, 第 2 k 列的數字全為得知, 第 2 k + 列數字為 {, 0, 0,...,0, 0, }, 取左邊的 2 k 個數 {, 0, 0,...,0, 0}, 經過 2 k 操作後會得到 2 k 個數 {,,...,, } ; 同理, 取右邊的 2 k 個數 {0, 0,...,0, 0, }, 也會得到 2 k 個數 {,,...,, } 此 2 k+ 個數會成為第 2 k+ 列的數字也就是, 當 n = k + 時, 第 2 k+ 列的數字全為, 引理成立根據數學歸納法, 對於任意 n 為非負整數, 模 2 後的巴斯卡三角形中, 第 2 n 列的數字全為恆成立 5

6 定理圓周上放置 2 n 顆黑白棋在第 2 n 次操作後會成同色經過次操作後, 由引理 2.., 每個位置均為 a + a 2 + a 3 + +a n 模的值, 故會同色特別注意, 棋子數為 2 n 以外的其他數, 並不會在 2 n 次操作後回到同色以五顆棋為例, 經 3 次操作後如下圖所示, 不會回到同色然而, 經 4 次操作後, 棋子排列如下圖所示, 與經一次操作後有相同的排列由於經 2 n + 次操作後, 對應巴斯卡三角形的係數為 {, 0, 0,...,0, }, 考慮的棋子數為 2 n ± 顆時, 我們可以發現下列的循環關係定理圓周上放置 2 n + 顆黑白棋經 2 n 次操作後, 棋子排列與經第次操作後有相同的排列且順向提升格 ; 圓周上放置 2 n 顆黑白棋經 2 n 次操作後, 棋子排列與經第次操作後有相同的排列且順向提升 0 格同理可得以下定理 2..4 定理圓周上放置出 2 n n n n + 2 k (k N 且 k < n) 顆黑白棋, 循環分別為 2 n 2 2 n 4 2 n n 2 k 次且分別回到第 k+ 次操作結果, 故分別經過 2 n 2 k 次操作後, 棋子的排列會與第一次操作後有相同的排列 6

7 由定理觀察比較 6 顆棋與 3 顆棋的循環分別為 2 與, 另外,0 顆棋與 5 顆棋的循環分別為 6 與 3, 有著兩倍的關係, 因此可得出以下定理 : 定理當 m 2 n, 假設圓周上放置 m 顆黑白棋的週期為 T, 且順向提升 r 格, 則當圓周上放置 2m 顆黑白棋時經過 2T + z 次操作後會和第 z 次操作後有相同的排列, 且順向提升 2r 格若 2m 顆棋的初始排列 {a,a 2,...,a 2m } 並依序定義為 {A,B,A 2,B 2,...,A m,b m }, 其中 A 為初始的第 2 顆棋的顏色所代表的數字, B 為初始的第 2 顆棋的顏色所代表的數字初始情況為 A 經一次操作後為經二次操作後為經三次操作後為經四次操作後為 A + B A + 2B + A + (A + A + ) A + 3B + 3A + + B + (A + B + A + + B + ) A + 4B + 6A + + 4B + + A +2 (A + A +2 ) 由上可知, 兩次操作後可視為奇數位置 (A,A +,A +2,...,A m ) 代表的 m 顆棋子的一次操作與偶數位置 (B,B +,B +2,...,B m ) 的 m 顆棋的第一次操作 ; 四次操作可視為奇偶位置 (A,A +,A +2,...,A m ) 與 (B,B +,B +2,...,B m ) 的第二次操作因 2m 顆棋每 2 次操作可視為奇數位置與偶數位置上 m 的次操作當 m 2 n, 當圓周上放置 2m 顆黑白棋時經過 2T + z 次會和第 z 次操作後有相同的排列相對地, 順向提升格子數也成 2 倍關係由於巴斯卡三角形上每列的數會代表經該次操作後的係數, 因此 m 顆棋子可套用到其任一列所代表的係數所代表操作次數會產生, 我們著手於找出哪一列的係數能符合相對應的循環與回歸次數的關係, 為此我們利用尤拉定理 m 為奇數時, 2 φ(m) (mod m) () 其中 φ(m) 表不大於 m 且與 m 互質的正整數個數定理當 m 是奇數時, 圓周上放置 m 顆黑白棋經第 2 φ(m) 次操作後, 棋子的排列必然會與第一次操作後有相同的排列由公式與引理 2.., 經 2 φ(m) 次操作的排列為 {a n +a,a +a 2,a 2 +a 3,,a n +a n }, 與第一次操作後有相同排列, 即可得此結果 7

8 引理設 m 是正奇數, n 是 2 n (mod m) 的最小正整數 n, n 2 是 2 n (mod m) 的最小正整數 n, 令 mn{n,n 2 }=n 0, 當 2 p (mod m), 則 n 0 p 若 n n 2, 設 p = n q + r, 0 r < n, 則 2 p = 2 nq+r =(2 n ) q 2 r (mod m) where 2 r (mod m) 若 r 0, 2 r (mod m) 又 n > r, 則與 n 是最小正整數使得 2 n (mod m) 矛盾, 因此 r = 0 若 n > n 2, 設 p = n 2 q + r, 0 r < n 2, 則 2 p = 2 n2q+r =(2 n2 ) q 2 r (mod m) where ( ) q 2 r (mod m). 若 q 為偶數, 2 r (mod m), 則與 n 是最小正整數使得 2 n (mod m) 矛盾 ; 2. 若 q 為奇數, 2 r (mod m), 則與 n 2 是最小正整數使得 2 n (mod m) 矛盾由定理 2..6 及引理 2..7 可得下列推論推論圓周上放置 m 顆黑白棋, m 2 n, 則當 m 為奇數時, 令 Tm 2 = 2 n 0, 則經過 Tm 2 次操作後, 棋子的排列必然會與第一次操作後有相同的排列當 m 為偶數時,m = 2 p q, q 為奇數, 令 Tm 2 = 2 p Tq 2, 則 m 顆棋經過 Tm 2 + z 次操作後會和第 z 次操作有相同的排列舉例說明 ( 26 顆棋 ): 26 = 3 2, φ(3)=2 從 2 的因數中可以得到 n 0 = 6, T 2 3 = 2 6 = 63, T 2 26 = 2 (2 6 )=26 8

9 2.2 質數色棋經過二色棋的研究後, 我們決定討論多種顏色棋的情況, 首先我們先考慮三色棋的情況, 操作定義為 : 用 {0,, 2} 代表三種顏色, 重複任取 m 個數均勻放置在一圓周上, 相鄰兩數模 3 後得新的數放置在兩數中點, 並將原 m 個數拿掉, 產生新的數列, 稱為一次操作觀察模三後的巴斯卡三角形如下 : 可得第 3 n + 列的數字為 {, 0, 0,...,0, 0, } 因此, 當 m 不是 3 的倍數時, 圓周上放置 m 顆三色棋經第 3 φ(m) 次操作後, 棋子的排列必然會與第一次操作後有相同的排列並將其推廣到任意 n 種顏色棋, 用 {0,, 2,,n } 等 n 個數來表示 n 種顏色, 相鄰兩數相加後被 n 除後的餘數來表示新的顏色棋模 n 後的巴斯卡三角形是否具有的性質, 方能進行週期的計算引理若 n 是質數, 將巴斯卡三角形模 n 後形成了新的巴斯卡三角形, 且在第 n + 行的排列為依巴斯卡定理, 在第 n 行的係數依次為 C0 n,c n,c2 n,c3 n,...,cn n, 其中, C n n (n ) (n + ) =, n, N 2 因為 n 為質數, 所以 C n 為 n 的倍數, 可得 C n 0 (mod n) 另外, 若 n 是合數, 令 n = ak(k 為質數 )a N, 則 Ck n ak (ak ) (ak k + ) = 不可能是 n 的倍數, 故巴斯卡三角形模 n 後形 2 k 成了新的巴斯卡三角形, 且在第 n 行的排列不會是因此, 我們將顏色數分成質數色與合數色兩類進行討論 9

10 將巴斯卡三角形分別模 5 與模 7, 如下所列 : 模 5 巴斯卡三角形模 7 巴斯卡三角形當 p 是質數, 用 {0,, 2,...,p } 代表 p 種顏色, 重複任取 m 個數均勻放置在一圓周上, 相鄰兩數模 p 後得新的數放置在兩數中點, 並將原 m 個數拿掉, 產生新的數列, 稱為一次操作, 即 b a + a + + (mod p) 我們利用 Excel, 以初始排列 {, 0, 0,...,0} 模擬並將質數色棋的棋子數的週期以表格列出如下 : 棋子數色棋色旗色棋

11 定理模 p 後的巴斯卡三角形中, 第 p n + 列的數字為 {, 0, 0,...,0, 0, } C n = 仿引理 2.2., 在第 p n + 列的係數依次為 C pn 0,Cpn,Cpn 2,Cpn 3,...,Cpn n (n ) (n + ) N, p n, N 2 令 < s <, s= p k l, < k < n, (l, p)= pn s 因為 p 為質數, 所以 C pn = pn p k l p k l s 為 p 的倍數, 可得 C pn 0(mod p) p n, 其中, = pn k l l 定理假設圓周上放置 m 顆棋子的週期為 T, 且順向提升 r 格, 則圓周上放置 pm 顆質數色棋經過 pt + z 次操作後會和第 z 次操作有相同的排列, 且順向提升 pr 格令 pm 顆棋的初始排列 {a,a 2,...,a 2m,a 2m+,...,a pm } 重新定義為 {A,,A,2,...,A,p,A 2,,A 2,2,...,A 2,p,...,A m,,a m,2,...,a m,p } 第 p 次操作後為 {A, + A 2,,A,2 + A 2,2,...,A,p + A 2,p,A 2, + A 3,,...,A m,p + A,p } 可得, 第 p 次操作後第 p + k 位置可視為 (A,k,A 2,k,A 3,k,...,A m,k ) 代表的 m 顆棋子的第一次操作, 圓周上放置 pm 顆質數色棋經過 pt + z 次操作後會和第 z 次操作有相同的排列相對地, 順向提升格子數也成 p 倍關係定理當 m 不是 p 的倍數時, 圓周上放置 m 顆 p 色棋經第 p φ(m) 次操作後, 棋子的排列必然會與第一次操作後有相同的排列仿定理 2..6 之證明, 利用定理及尤拉公式可得引理當 m 不是 p 的倍數, 設 n 是 p n (mod m) 的最小正整數 n, n 2 是 p n (mod m) 的最小正整數 n, 令 mn{n,n 2 }=n 0, 當 p q (mod m), 則 n 0 p 證明手法與引理 2..7 相同推論圓周上放置 m 顆質數色棋, m p n, 則. 當 m 不為 p 的倍數時, 令 Tm p = p n0, 則經過 Tm p 次操作後, 棋子的排列必然會與第一次操作後有相同的排列 2. 當 m 為 p 的倍數時, m = p k q, q 不為 p 的倍數, 令 Tm p = p k Tq p, 則圓周上放置 m 顆質數色棋經過 Tm p + z 次操作後會和第 z 次操作有相同的排列舉例說明 ( 5 顆 5 色棋 ): 5 = 3 5, φ(3)=2 從 2 的因數中可以得到 n 0 = 2, T3 5 = 5 2 = 24, T5 5 = 5 (5 2 )=20

12 2.3 合數色棋 Case n = p p 2 p k 時 : 我們用初始排列情況 {, 0, 0,...,0} 用 Excel 模擬後將六色棋與兩色棋三色棋的週期比較列成表格如下 : 棋子數色棋色旗色棋發現六色棋的週期和兩色棋和三色棋的週期最小公倍數呈倍數關係, 並發現模 6 的餘數有一一對應 : mod mod mod 數對 (, ) (0, 2) (, 0) (0, ) (, 2) (, 0) 將六種顏色分別對應 0 (0, 0), (, ), 2 (0, 2), 3 (, 0), 4 (0, ), 5 (, 2) 可以將每次操作視為任意相鄰兩數對 (x,y ), (x +,y + ) 中間放置新的數對 (x,y ) 滿足 x x + x + (mod 2),y y + y + (mod 3) 舉例 (0 顆 6 色棋 ) 將棋子顏色代表數對 (x, y) 分開來討論,T 2 0 = 6, 順向提升為 2, T 3 0 = 8, 順向提升為, 但六色棋的的週期不一定是 6 和 8 的最小公倍數, 週期會受順向提升次數的影響 0 顆棋子的 x 部分經 24 次操作後的順向提升為 8, 但 y 部分的順向提升僅為 3 (x, y) 相對位置相差了 5, 所代表的數對排列與 24 次操作前的排列不相同我們以圖為例觀察 0 顆 6 色棋的情況 : 2

13 雖然內圈和外圈各自有循環, 但因為順向提升的關, 他們所組合出的數對並沒有循環再經過 24 次操作後 : 觀察上圖, 經過 48 次操作後, 發現他們的順向提升剛好相差 0, 因此他們所組成的數會回到原始排列因此, 他們的順向提升要相差 0 的倍數, 他們所組合出的數才會有循環關係 24t t 8 (mod 0) 求出最小 t 值 2, 則 24 2 為 0 顆六色棋的循環次數推論設 (x) 代表 2 色棋週期為 a, 順向提升 r 2 m 格 ; (y) 代表 3 色棋週期為 b, 順向提升 r 3 m 格若 a, b 的最小公倍數 l =[a, b] =a h = b k, (h, k) =, 滿足 t(hr 2 m) t(kr 3 m)(mod m) 的最小 t 值為 t 0, 令 T 6 m = l t 0, 則 T 6 m 為 m 顆 6 色棋時的週期 (x,y ) 表示次操作後的排列, 則 (x +T 6 m,y +T 6 m ) 的排列與 (x,y ) 相同, 可知 Tm 6 為 Tm,T 2 m 3 的倍數令 Tm 6 = l t, Tm 6 = Tm 2 ht = Tm 3 kt, 則經 Tm 6 次操作後, 數對 (x,y ) 與 (x +T 6 m,y +T 6 m ) 的 (x) 部分順向提升 htrm 2, (y) 部分順向提升 ktrm 2 故 htrm 2 ktrm(mod 3 m) 而 t 最小值 t 0 可得 Tm 6 = l t 0 我們將此手法推廣到部分合數色棋, 利用各質數 p 的循環關係來計算合數色棋的 T n m 定理圓周上均勻放置 m 顆合數 n 種顏色棋, n p p 2 p k, p 為相異正質數, k, 設 p 色棋的週期是 Tm p, 順向提升 rm p 格, 假設 e = lcm(tm p,tm p2,,t p k m ), 且 e = Tm p h, k 滿足 t(h rm) p t(hrm pj )(mod m), < j k 的最小 t 值為 t 0, 令 Tm n = e t 0, 則 Tm 6 為 m 顆 6 色棋時的週期數對 (x p,x p2,,x pk ) 表示 n 種顏色, 其中 x p {0,,,p } 滿足 r {0,, 2,,n } 且 r x p (mod p ) 經過一次操作後, 相鄰兩顆棋所代表的兩數 r, r 分別對應到數對 (a p,a p2,,a pk ), (a p,a p 2,,a p k ), 中間放置新的數對 (b p,b p2,,b pk ) 滿足 b p a p + a p (mod p ) 此時 r a p (mod p ) 且 r a p (mod p ) 3

14 則 r + r a p + a p (mod p ) 又 n = p p 2 p k, p 為相異正質數, 則 r + r (mod n) 與 (a p + a p (mod p ),a p2 + a p 2 (mod p 2 ),...,a pk + a p k (mod p k )) 有著一一對應的關係 m 顆合數色棋的週期為 Tm p, 可知 Tm p 為 Tm p 的倍數令 Tm p = e t, Tm p = e t = Tm p h t, < j k, 則經 Tm p 次操作後, (x) 部分順向提升 rm p h t, 故 t(h rm) t(h p j rm pj )(mod m) 而 t 最小值 t 0 可得 Tm p = e t 0 Case 2 n = p α 時 : 四色棋在四色棋時就沒有像六色棋剛好有餘數的一一對應, 因此嘗試用不同方法來解釋四色棋的循環關係我們先將四色棋和兩色棋的週期做成表格來比較 : 棋子數四色棋兩色棋可觀察出四色棋和兩色棋的循環呈兩倍關係但因為四色棋沒有漂亮的餘數一一對應, 我們試著以二進位的方式來處理 s,t {0, }, a s + t 2(mod 4) (mod 4) (mod 4) (mod 4) (mod 4) 模 4 後巴斯卡三角形可以視為以下兩巴斯卡三角形相加 = 模 4 巴斯卡三角形模 2 巴斯卡三角形 Q2 巴斯卡三角形 4

15 以五顆棋為例, 在模 2 的巴斯卡三角形從第列回到第 2 列, T 2 5 = 3, 順向提升為觀察四色棋分成的這兩個巴斯卡三角形, 可發現巴斯卡三角形可從第 5 列回到第 2 列, 但右邊則是從第 9 列回到第 3 列, 兩邊的巴斯卡三角形可同時從第列回到第 3 列, 週期為 6, 順向提升為 2 觀察模 4 的巴斯卡三角形, 即從第 9 列的回到第 3 列的 2 我們將探討 Q2 巴斯卡三角形的循環情況 : 引理模 4 巴斯卡三角形可拆成模 2 巴斯卡三角形和 Q2 巴斯卡三角形, 且 Q2 巴斯卡三角形是一個相加模二底下的操作假設模 4 巴斯卡三角形的第 n 列為 a,a 2,a 3,,a n, 第 n + 列為 a,a 2,a 3,,a n, 則 a + a + a + (mod 4) 令 a = s + t 2, a = s + t 2, 則 a + a + =(s + s + )+(t + t + ) 2, 此時, s + s + s + (mod 2), t + (t + t + +[ s + s + 2 ]) (t + t + )(mod 2)+[ s + s + ](mod 2) (2) 2 可得, Q2 巴斯卡三角形的每一列將受前一列的模 2 巴斯卡三角形與 Q2 巴斯卡三角形的影響定理若圓周上有 m 顆四色棋, Q2 巴斯卡三角形的第 2T 2 m + z 列和第 z 列所對應 m 顆棋的排列相同由方程式 2 之 [ s + s + ](mod 2) 表示模 2 巴斯卡三角形的各列均會提出一數列 2 {l } 至 Q2 巴斯卡三角形內部進行運算, 因此 Q2 巴斯卡三角形的第 n 列可拆成模 2 巴斯卡三角形的各 n 列所提出 {l } 分別經過到 n 次巴斯卡運算後的總和模 2 結果然而, l =[ s + s + ](mod 2), 因此 {l } 由模 2 巴斯卡三角形的各列所決定, 在 m 2 顆棋時, 模 2 巴斯卡三角形的 Tm 2 + z 列和第 z 列所對應 m 顆棋的排列相同因此, 模 2 巴斯卡三角形的 Tm 2 + z 列和第 z 列所提出的 {l } 之對應 m 顆棋排列相同又第 z 列所提出的 {l } 經 Tm 2 次巴斯卡運算後之對應 m 顆棋會產生循環此時, 模 2 巴斯卡三角形的 Tm 2 + z 列和第 z 列所提出的 {l } 在模 2 底下可以消掉故 Q2 巴斯卡三角形的第 2Tm 2 + z 列和第 z 列所對應 m 顆棋的排列相同利用此方法, 推廣到 2 n 種顏色棋定理當 m 2 n, 假設圓周上放置 m 顆兩色棋週期為 T 2 m 順向提升 r 格, 則 2 n T 為 m 顆 2 n 色棋子的週期, 且順向提升 2 n r 格當 n = 2 時, 由定理之結果可證設 n = k 時, Tm 2k = 2 k Tm 2 成立令 a s + t 2(mod 4), s {0,,, 2 k }, t {0, } 則模 2 k 巴斯卡三角形可拆成模 2 k 巴斯卡三角形加上 Q(2 k ) 巴斯卡三角形 2 仿引理及定理之證明過程, Q(2 k ) 巴斯卡三角形符合模 2 巴斯卡運算, 此時 Q(2 k ) 巴斯卡三角形的第 2Tm 2k + z 列和第 z 列所對應顆棋的排列相同可得 Tm 2k+ = 2Tm 2k = 2 k Tm 2 5

16 推論 p 是質數, 假設圓周上放置 m 顆 p 色棋週期為 T p m, 順向提升 r 格, 則 p n T 為 m 顆 p n 色棋子的週期, 且順向提升 p n r 格將模 p n 巴斯卡三角形可拆成模 p n 巴斯卡三角形加上 Q(p n ) 巴斯卡三角形 p 假設模 p n 巴斯卡三角形的第 h 列為 a,a 2,a 3,,a n 第 h + 列為 a,a 2,a 3,,a n 則 a + a + a + (mod p n ) 令 a = s + t p, a = s + t p, s {0,,,p n }, t {0,,,p} 則 a + a + =(s + s + )+(t + t + ) p, 此時, s + s + s + (mod p n ) t + (t + t + +[ s + s + p n ]) (mod p) (t + t + )(mod p)+[ s + s + p n ](mod p) 得 [ s + s + ](mod p) 表示模 p n 巴斯卡三角形的各列均會提出一數列 {l p n } 至 Q(p n ) 巴斯卡三角形內部進行運算, 此時, 模 p n 巴斯卡三角形的第 ktm pn + z, k =, 2,,p 列經巴斯卡運算後和第 z 列所提出的 {l } 在模 p 底下可以消掉故 Q(p n ) 巴斯卡三角形的第 ptm pn + z 列和第 z 列所對應顆棋的排列相同仿定理之證明過程, 可得 Q(p n ) 巴斯卡三角形的第 p n Tm p + z 列和第 z 列所對應顆棋的排列相同故 Tm pn = p n Tm p 依照定理的手法與推論結果, 得出任意多個質因數的合數色棋的結果如下 : 推論圓周上均勻放置 m 顆合數 n 種顏色棋, n = p α pα2 2 pα k k 數, k, 令 p α 且 e = p α Tm p h 滿足色棋的週期是 p α Tm p e = lcm (p α T p m,p α2 2 T p2 t(h p α r p m) t(h j p αj j, 順向提升 p α m,,p α k k T p k m ) r pj m )(mod m), p 為相異正質 m 格, 假設 < j k 的最小 t 值為 t 0, 令 T n m = e t 0, 則 T n m 為 m 顆 n 色棋時的週期 r p 6

17 3 結論 3. 研究結果一黑白棋. 圓周上放置 2 n 顆黑白棋在第 2 n` 次操作後會成同色 2. 當 m 2 n, 假設圓周上放置 m 顆黑白棋的週期為 T, 且順向提升 r 格, 則圓周上放置 2 m 顆黑白棋經 2T + z 操作後會和第 z 次操作有相同的排列, 順向提升 2r 格 3. 圓周上放置 m 顆黑白棋, m 2 n, 則 () 當 m 為奇數時, 令 Tm 2 = 2 n0, 則經過 Tm 2 次操作後, 棋子的排列必然會與第一次操作後有相同的排列 (2) 當 m 為偶數時,m = 2 p q, q 為奇數, 令 Tm 2 = 2 p Tq 2, 則 m 顆棋經過 Tm 2 + z 次操作後會和第 z 次操作有相同的排列二質數色棋當 p 是質數, 在 {0,, 2,,p } 可重複任取 m 個數均勻放置在一圓周上, 可得. 假設圓周上放置 m 顆棋子的週期為 T, 且順向提升 r 格, 圓周上放置 pm 顆質數色棋經過 pt + z 次操作後會和第 z 次操作有相同的排列, 順向提升 pr 格 2. 圓周上放置 m 顆黑白棋, m p n, 則 () 當 m 不為 p 的倍數時, 令 Tm p = p n0, 則經過 Tm p 次操作後, 棋子的排列必然會與第一次操作後有相同的排列 (2) 當 m 為 p 的倍數時 $ m = p k q, q 不為 p 的倍數, 令 Tm p = p k Tq p, 則質數色棋經過 Tm p + z 次操作後會和第 z 次操作有相同的排列三合數色棋. p 是質數, 假設圓周上放置 m 顆 p 色棋週期為 Tm p, 順向提升 r 格, 則 p n T 為 m 顆 p n 色棋子的週期, 且順向提升 p n r 格 2. n = p α pα2 2 pα k k, p 為相異正質數 k, 令 p α 色棋的週期是 p α Tm p, 順向提升 p α rm p 格, 假設 e = lcm(p α Tm p,p α2 2 Tm p2,,p α k k T p k m ), 且 e = p α Tm p h k 滿足 t(h p α rm) p t(h j p αj j Tm pj )(mod m), < j k 的最小 t 值為 t 0, 令 Tm n = e t 0, 則 Tm n 為 m 顆 n 色棋時的週期四棋子數與對應的循環關係不同色棋與週期的表格如下 : 棋子數色棋色棋色棋色棋色棋色棋

18 3.2 討論 3.2. 在棋子的定義中, 我們雖然將新的棋子放在兩棋中點, 但為了計算時方便討論, 將第一顆和第二顆棋操作後的新棋子定義它的位置為第一個, 第 2 3 顆操作後的新棋子定義它的位置為第二個, 即 b a + a + (mod p) 之後我們試著研究不同定義下的三色棋操作方式 ( b (a + a + )(mod 3) ), 與質數色棋不同 ( b a + a + (mod p) ), 考慮到原本命題以顏色作為操作基礎 ( 相鄰兩棋為異色, 則在中間放黑棋, 相鄰兩棋為同色, 則在中間放白棋 ), 因此我們以顏色的角度來定義三色棋的操作 ( 鄰兩棋若是同色則在中點上放一顆此色棋, 異色則放上第三色棋 ), 此種顏色的變化規則比較常見, 且發現與原本的三色棋有類似的規則在質數 p 色棋中, 我們用來計算週期的方式都排除了 p 色, 而我們統整出了當有 p 顆 p 色棋時的對應週期, 而 p n 顆棋則可以用週期的 p 倍關係求出此時的週期為 p(p ) 或其因數, 仍在尋求證明手法棋子數 3 顆 5 顆 7 顆顆 3 顆 7 顆與顏色三色棋五色棋七色棋十一色棋十三色棋十七色棋週期參考文獻 [] 單墫民國 89 年, 趣味數論九章出版社 [2] 常庚哲 ( 民國 02), 磨光變換中國科學技術大學出版社 8

Microsoft Word - ACL chapter02-5ed.docx

Microsoft Word - ACL chapter02-5ed.docx 第 2 章神奇的質數 2.1.1 什麼是質數 1 1 1 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 1 1 0 10 2 3 5 7 4 6 8 9 10 4 10000 1229 1000 168 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131