偶然中有必然──怎樣才公平?
本研究發現n個人的約瑟夫問題,反覆淘汰留下來的第m個人,m=1〜lcm(n,n-1,……,k) 時,倒數第k個淘汰的編號f(n,m,k) 會循環,其循環節長度是lcm(n,n-1,……,k);又找出 f(n,m,k) 的遞迴公式,再以該公式使用 Excel 推算 n=1〜16,m=1〜lcm(n,n-1,……,2) 時,發現人數不變時,每個編號倒數第 k (k=n〜1) 個淘汰的機會都相同;據此提出並證明「約瑟夫定理」:人數n人,反覆淘汰留下來的第m個人,取 m=1〜lcm(n,n-1,……,2) 時,每個編號倒數第k個淘汰的機會都相同。
從平分問題到動態穩定
本文探究由一人獨自進行的遊戲,探討最後是否能將兩堆石頭移動形成數量相等的狀態,稱之為「穩定狀態」。探索過程中,我們利用數對(x, y)來表示兩堆石頭分別有x, y顆的情況,利用輾轉相除法的形式來記錄移動過程,而因為遊戲進行中,兩堆石頭的總數不變,因而以此總數進行分類觀察,我們發現並非任意數對(x, y)皆能形成穩定狀態。 藉由列表觀察後,我們猜測當x+y=2k時,任意數對(x, y)皆能形成穩定狀態,我們用二進位制驗證,並進一步得到定理1: 定理1:數對(2k-p×2m, p×2m))形成穩定狀態所需的次數為k-1-m次。 另外,因為數對(qa, qb)和(a, b)的移動方式類似,得知定理3及4如下: 定理3:數對(q2k-pq×2m, pq×2m)形成穩定狀態所需的次數為k-1-m次。 定理4:若x+y=q×2k , q≠1, 且x, y的最大公因數為r×2m,q≠r時(x,y)無法形成穩定狀態。 由以上定理1、3、4,可歸納為定理5如下: 定理5:若x+y=q2k(q為奇數), 且x, y的最大公因數為r×2m,則 1.q=r時,數對(x, y)形成穩定狀態的次數為k-1-m次。 2.q≠r時,數對(x, y)無法形成穩定狀態。