約瑟夫問題之數值探究摘要本研究旨在探討約瑟夫問題之起始相對位置問題及 N K 值之間的變化研究者利用遞迴關係式加上 matlab 撰寫程式檢驗結果, 探討總數為 N 之約瑟夫問題, 以 K 個一數, 第 I 個刪去之起始相對位置關係式 ; 並以 K=1 到 100 為例, 探討總數 N 其數值

Size: px

Start display at page:

Download "約瑟夫問題之數值探究摘要本研究旨在探討約瑟夫問題之起始相對位置問題及 N K 值之間的變化研究者利用遞迴關係式加上 matlab 撰寫程式檢驗結果, 探討總數為 N 之約瑟夫問題, 以 K 個一數, 第 I 個刪去之起始相對位置關係式 ; 並以 K=1 到 100 為例, 探討總數 N 其數值"

壁溥
5 years ago
Views:

1 國立臺中教育大學數學教育學系在職進修教學碩士學位班碩士論文指導教授 : 胡豐榮博士約瑟夫問題之數值探究研究生 : 蔡明憲撰中華民國九十七年六月 I

2 約瑟夫問題之數值探究摘要本研究旨在探討約瑟夫問題之起始相對位置問題及 N K 值之間的變化研究者利用遞迴關係式加上 matlab 撰寫程式檢驗結果, 探討總數為 N 之約瑟夫問題, 以 K 個一數, 第 I 個刪去之起始相對位置關係式 ; 並以 K=1 到 100 為例, 探討總數 N 其數值限制之差異, 及總數 N=100,K 100, 滿足約瑟夫問題之 K 值研究結果說明如下 : 壹本研究發現約瑟夫問題中, 對應 N K I 三個數值所得最後棋子相對位置之遞迴關係式為 J(N+1,K,I+1) (K+J(N,K,I)) (mod(n+1)) 貳本研究發現約瑟夫問題中, 當 K=1 時, 總數 N 值的大小不受限制 ;K=2 5 8 時只有 N=2 時成立 ; 本研究亦得到 K 時所對應的總數 N 之上限值參本研究發現當總數 N=50,K 100 時, 存在 K= 可以滿足約瑟夫問題 ; 當 N=100,K 100 時, 只剩下 K= 成立 ; 當 N=200 時, 只餘 K=1 成立, 故 N 值愈大, 存在滿足約瑟夫問題的 K 值愈少關鍵字 : 約瑟夫問題同餘遞迴 II

3 The study of computation of Josephus Problem Abstract This study was to explore the relative position of the outset according to the rule of Josephus Problem and the change between N s value and K s value. The researcher used Recurrence relations & the Programming language of matlab to check result of Josephus Problem. The totality (N) of Josephus Problem, count by a number (K), and to chase down outset position relationship of Ith deletion. And take K=1 to 100 as the example, to research difference of the upper limit of N, and the value of K by the rule of Josephus Problem when N=100, K 100. The result of research as follows: 1. The relative position of the outset according to the rule of Josephus Problem is J(N+1, K, I+1) (K+J(N, K, I)) (mod(n+1)). 2. This research in the Josephus Problem:(1)the total N value's size is not limited when K=1.(2)Only N=2 conform to the rule of Josephus Problem when K=2, 5, 8. the total N value's size has the corresponding value respectively when K As the total N=50, K 100, has K=1, 9, 16, 18, 49, 57, 64 to conform to the rule of Josephus Problem; As N=100, K 100, K=1, 16, 49, 57o conform to the rule of Josephus Problem; As N=200, K=1 to conform to the rule of Josephus Problem, therefore the N value is bigger, the K value to be less. Key word:josephus Problem, Modular arithmetic, Recursive. III

4 目錄第一章緒論 01 第一節研究動機 01 第二節研究目的 02 第三節名詞釋義 03 第二章文獻探討 06 第一節約瑟夫問題 06 第二節約瑟夫相關問題研究 08 第三章主要結果 13 第一節遞迴關係式 13 第二節總數 N 上限值差異 14 第三節滿足條件之 K 值 19 第四章結論與未來發展方向 21 第一節結論 21 第二節未來發展方向 21 參考文獻 23 附錄 25 附錄一題型圖解 25 附錄二電腦程式 41 IV

5 圖目錄圖 1-1 約瑟夫問題黑白棋相對位置 04 圖 2-1 典型約瑟夫問題 06 圖 2-2 著色問題位置 11 表目錄表 2-1 八仙定坐問題骰子與上位人員位置關係 09 表 2-1 沈康身解八仙定坐之上位人員位置關係 09 表 3-1 以 K=9 為例各 N 值其末兩位相對位置 14 表 3-2 K 值對應總數 N 上限值 18 表 3-3 N=100 及 K 100 時 K 值對應末兩個棋子之相對位置 20 表 3-4 N=600 及 K 600 時 K 值對應末兩個棋子之相對位置 20 V

6 第一章序論在數學教育課程當中, 需要引導學生培養數學眼光, 指導學學生如何去領會數學本身的美, 將日常生活中中的問題數學化, 運用學習來的數學能能力去解決日常生活中的問題在數學相關的的課程當中, 常常會以一些益智遊戲呈呈現在學生眼前, 引發學生學習的動機, 這些些遊戲大多數都有一定的規則可循, 有一些口訣幫助記憶或解題若是以學生的立立場來看這些遊戲, 可以引發學習動機, 懂得怎麼去解題或許就足夠了 ; 但身為一一個數學教師, 該把這些遊戲利用數學學眼光好好的檢視一番當自己或是他人在操操弄這個遊戲的同時, 應該尋求一個以以數學思考的解題途徑, 這才不失一個學習引引導者該伴演的角色第一節研究動機日常生活中, 許許多多多的遊戲或是趣味題目, 與數學都有密密不可分的關係從古代流傳下來的益智遊戲, 至今人們都仍在玩, 例如 : 九連環環華容道七巧板等曾被問及一個益智遊遊戲, 其內容是 : 有 12 個石子排列成一一個圈, 其中 10 個石子是黑色, 剩餘 2 個是是白色, 而且這 2 個白色的石子是相鄰鄰的, 從其中一個開始計數, 由 , 數到 9 的這個石子就拿掉, 依此此規則點數, 直到最後只剩下兩個, 請問由那那一個石子開始數, 才能讓兩個白色的的石子被留下來為了解決這個問題, 查閱了許多相關資料, 在西方國家也也出現相類似的題目, 稱為約瑟夫問題 (Josephus Problem), 另一種類似的題型稱稱為航海問題 ; 在東方則有日本的繼子立問問題我國八仙定座問題及貓食十三鼠鼠問題然而西方的約瑟夫問題航海問題題及貓食十三鼠問題, 其研究的結果只只找出最後或倒數幾名的位置 ; 日本繼子立立問題當中所討論的是進行一半的約瑟瑟夫問題後再轉向 1

7 處理, 最後還是只找出最後一個的位置 ; 我國八仙定座問題則是討論兩個骰子點數合, 其數值對剩餘末位的位置影響, 這些資料都只有簡要的說明或是留下正確解答, 並無相關的解題方法及過程借由這些先備知識, 如何加以運用並解決約瑟夫問題末兩位相鄰的問題, 成為本研究很重要的一個環節, 因此研究者有了一個想法, 若對於總數為 N 之約瑟夫問題, 以 K 個一數, 找到第 I 個刪去之起始相對位置之關係式, 是不是可以幫助解決本研究之約瑟夫問題? 在郭世榮 (2002) 研究中提到, 方通中在數度衍中大膽假設, 九個一數對所有 N 值皆存在末兩位相鄰之結果, 郭世榮 (2002) 利用 Basic 語言算出 K=9 對應總數 N 之上限值為 91, 但對其它 K 值上限卻無討論, 故研究者想對 1 K 100 作總數 N 的上限值比較 ; 至於當 K 100 時, 在益智遊戲中, 由一點數到一百或一百以上對於此類問題並無多大的區隔, 點數愈多反而會失去玩弄益智遊戲之趣味, 故研究者將研究範圍設在 K 小於一百以內在八仙定座的題型當中, 固定總數 N 在變動的 K 值影響下, 改變了最後誰坐上位的結果, 使得研究者想運用於約瑟夫問題中, 探討固定總數 N, 會有多少個 K 值可以滿足本研究的約瑟夫問題? 綜上所述, 本研究主要是找出約瑟夫問題中, 總數 N 點數到 K 拿掉, 第 I 個相對起始位置之關係式, 並探討 N 及 K 值之間的影響, 希望借此找出一個以數學方法解決益智遊戲之途徑第二節研究目的基於上述研究動機, 本研究之目的如下 : 一找出約瑟夫問題中 N K I 相對於起始位置之關係式二探討約瑟夫問題中,1 K 100 時, 對應總數 N 上限值之差異 2

8 三找出 N=100,K 100 時, 滿足約瑟夫問題之 K 值第三節名詞釋義壹九連環九連環是一種傳說源於中國的傳統智力遊戲, 這種古老玩具以往在民間極為普及它包含著九個相同的圓環及一把劍, 目的是把九個圓環全套上或卸下不少人還認為能解此環可訓練腦筋, 甚至代表聰明的象徵其實九連環不一定是要九連環, 也可以是七連環或是十一連環等, 但其中卻是九連環最廣為人知中國人心目中以九為尊, 且九代表一種多數有這種說法 : 巧環難解, 九連環更難解, 九個連環表示著一種不能輕易得解的等級, 難度達到了顛峰其中次出名的為六連環, 取其六六無窮之意 ( 維基百科,2007) 貳華容道華容道, 英文稱 Klotski, 是一種滑塊遊戲, 由放在方形盤中的 10 塊方片拼成, 目標是在只滑動方塊而不從棋盤中拿走的情況下, 將最大的一塊移到底部出口最大的一塊代表曹操, 其餘九塊分別代表關羽張飛趙雲馬超和黃忠及 4 個小兵各方塊的起始位置可以根據開局不同有變化, 但傳統的擺法是將曹操置於方盤上方的中間, 周圍圍繞著五虎將和小兵遊戲的玩法是移動這 10 塊方塊, 將代表曹操的一塊移動到最下方中間的空位一般玩法分兩種 : 移動最少次數, 或者用最少的時間來完成遊戲 ( 維基百科,2007) 參七巧板七巧板除七巧板的名稱外, 還有不少名稱 : 益智圖智慧板唐圖等都是七 3

9 巧板的別稱七巧板的英文名稱則為 Tangram 這英文名稱的由來在坊間有不少說法, 其中流傳最廣的有三種 : 一它來自被廢棄的英文單詞 Tangram, 意思是奇形怪狀的小玩意二 Tang 是來自中國唐朝的帶後綴 ; 而 gram 是來自希臘文 γραµµή, 詞意為直線 ; 整個詞語的意思就是唐朝的直線三來自俚語 Tanka, 話說從前居住於中國東南沿海岸被稱為蛋家的水上居民, 他們供應食物給一些在運輪擺渡中的商家, 除了供應食物以外, 他們還提供一些娛樂招待, 其中一樣即是由七片薄片組成的中國謎題 Tangram 一詞大約就是 Game of the Tanka, 船上人家的游戲演化出來的三種說法皆有一定的根據, 但大部份西方人皆覺第二種說法最可靠 ( 維基百科,2007) 肆約瑟夫問題本研究所指之約瑟夫問題 : 將總數 N 個的黑白棋排成環狀, 其中有兩個白棋, 剩餘 N-2 的皆為黑棋, 兩個白棋必須相鄰, 黑白棋相對位置如圖 1-1 所示圖 1-1 從 N 個當中的某一棋子開始, 由 1 到 K 以順時針方向點數, 數到 K 的棋子拿 4

10 掉, 再由下一個棋子開始點數, 重覆操作, 直到最後只剩餘兩個白色的情況, 應該由那一個棋子開始點數之問題伍同餘在本研究當中, 所用到的同餘的值 a b, 當 a b (mod n) 所採用的數值是 a=b 且,0 a,b N-1, 其餘之同餘之數值在本研究的等式中並不成立 5

11 第二章文獻探討本研究主要是運用遞迴迴關係及同餘, 探討約瑟夫問題中起始始相對位置之問題, 相關之約瑟夫問題及研究, 茲分別敘述如下 : 第一節約瑟夫問題在 Harry J. Smith (2006) 中指出, 據說在羅馬人佔領喬塔帕特特之後,39 個猶太人與 Josephus 及他的朋朋友躲到一個山洞中,39 個猶太人決定寧寧願死也不要被敵人抓到, 於是決定了一個自自殺的方式,41 個人排成一個圓圈, 由第 1 個人開始報數, 每報數到第 3 人該人就就必須自殺, 然後再由下一個重新報數, 直到所有人都自殺身亡為止然而 Josephus 和他的朋友並不想遵從,Josephus 要他的朋友先假裝遵從, 他將朋友與自己安安排在第 16 個與第 31 個位置, 於是逃逃過了這場死亡遊戲此問題的解法只要畫兩兩個圓圈就可以讓自己與朋友免於死亡亡遊戲, 這兩個圓圈內圈是排列順序, 而外圈圈是自殺順序, 如圖 2-1 所示 : 圖 2-1 由上可知, 最後一個自自殺的是在第 31 個位置, 而倒數第二個個自殺的要排在 6

12 第 16 個位置, 之前的人都死光了, 所以他們也就不知道約瑟夫與他的朋友並沒有遵守遊戲規則了 ( Harry J. Smith,2006) 此題之解決方法廣泛的被運用於電腦程式撰寫,A. Bogomolny. (n. d.) 的 Josephus Flavius game 中, 以 java 的形式輸出,3 N 50,1 K 49, 選定起始位置即可檢驗是否能躲過死亡遊戲 ; 同樣的問題也在 Peter B. Henderson. (n. d.) The Josephus Flavius Problem 中一樣也有不同程式語言的解決方法, 其預設解決的問題仍是在最後幾位的相對位置約瑟夫問題除了環形之外, 尚有直線方式的問題, 例題如下 : 設有 N 個人站成一排, 從第一名開始 1 至 3 報數, 凡報到 3 的人就退出隊伍, 其餘的向前靠形成新的一排, 再按此規則繼續進行, 直到第 X 次報數後, 只剩下三個人為止, 當 N=1000 時, 求這三個人的最初位置解題的方法要由最後的結果追溯到初始情形, 而每次報數後減少的人數也不一定相同, 這就是困難所在, 但注意到每次報數後, 退出隊伍的人所在的位置都是 3 的倍數, 故最後剩下的三個人中的前二人, 就是原來隊伍中的前二人, 因此, 主要問題是要求出第三個人原來的位置根據問題的淘汰方法, 可知此人每次報數時, 所在的位置都不是 3 的倍數, 並且它每次位置的變化與它所在位置前的各數中所有的 3 的倍數有關, 這就是解題的關鍵解法 : 第 p 次報數後, 剩下的三個人中的前二人最初的位置, 顯然是原來隊伍中的第一和第二個位置, 設第三個人的最初位置是第 a 個, 第一次報數後它站到第 a 個位置,, 第 p 次報數後, 它站到第 a 個位置, 顯然 a =3 由於都沒有被淘汰, 可知這些數都不是 3 的倍數, 經過一次報數, 由 a 到 a 的位置變動的數目 a -a 就是被淘汰的人數, 這恰是由 1 到 a 這些數中所有的 3 的倍數的個數, 即 (a r)( 其中 r=1 或 2), 則 a -a = (a r) (r=1, 或 2), 所以 a = (3a r)(r=1, 或 2), 由於 a,a 都是正整數, 所以當 a 為奇數時, 7

13 r=1;a 為偶數時,r=2 由此可知, 當總人數為 N 時, 最後剩下的三個人中的第三個人的最初位置是 a = (3a r) N (A) 其中 a 為奇數時,r=1;a 為偶數時, r=2 當 N=1000 時, 由 a =3 及遞迴關係式 (A), 得 a = =4,a = =5, a = =7,a =712,a = =1068>1000, 此時, 共報數 15 次, 最後剩下的第三個人最初在隊伍的第 712 個位置 ( 張本源, 無日期 ) 第二節約瑟夫問題之相關研究一繼子立問題日本繼子立問題大意是說, 老人前妻生了 15 個兒子, 後妻也生了 15 個兒子, 老人病危時要後妻選定一個兒子繼承家業, 後妻設計好讓 30 個兒子站立, 排列圍繞成一個圓, 其中穿白衣的表示是前妻所生之子, 穿黑衣的是後妻所生之子, 依順時針方向, 從某子開始計數, 每數到十的人就退出圈圈, 即宣告失去繼承家業的機會, 輪番循環進行, 直到中途前妻所生之子只餘一人, 後妻所生之子仍為十五人, 老人發現其中有詐急忙喊停, 改由前妻所生之子開始計數, 順時針方向改為逆時針方向點數, 最後前妻前之子由一比十五的劣勢險勝, 獲得繼承權 ( 郭世榮,2002) 前妻的十五個兒子分別排列在第 , 其餘的位置由後妻的孩子填補, 在前妻之子剩下位置 14 時, 老人發現有異時, 改由僅剩的前妻之子開始點數, 方向由原來的順時針改為逆時針, 最後剩下的變成了原來位置 14 的前妻之子在上述題目裡, 老人最後改變方向重新計數, 只是把剩下的十六人, 重新以十個一數再做約瑟夫問題的處理, 其實若只分前妻之子或是後妻之子, 有無改變方向, 最後剩下的都會是前妻之子 8

14 與繼子立相同類型的問題是以兩組不同人員分 A 組 B 組, 全部有 30 人,A B 各 15 人, 也是十個一數, 若要將 A 組人員全部留下, 則 A 組人員要位於等位置上即可 (Weisstein, Eric W.,n. d.) 二八仙定座問題我國流傳於大江南北的民間故事之一, 內容大意是八仙同赴王母宴, 宴會主持官員為不使呂洞賓坐首席, 出主意讓八仙排成圓圈, 並暗示小吏, 從呂洞賓前一人起, 按此前後次序, 以隨機擲兩顆骰子之合計數, 由一數到該數值, 數到誰就退出圈外, 依此規則繼續點數, 直至最後一人就坐首席這種方法表面上看不出主持官員做的手腳, 其實, 不論骰子擲出多少點, 呂洞賓總是坐不上首席 ( 沈康身,2003) 八仙定座問題, 兩顆骰子所可能擲出的點數為等 11 個數值, 假設八仙排列成一個圓, 呂洞賓的前一人所在位置為 1, 只要最後剩下的位置不在 2, 那麼呂洞賓就永遠坐不到上位, 每個骰子所擲出的數值所對應的最後一個人的位置如表 2-1: 表 2-1 骰子點數合對應最後一人位置由表 2-1 得知, 兩個骰子點數合從 , 所剩下的最後一個位置皆不會為 2, 所以呂洞濱都坐不到上位, 但其最後一人的位置與沈康身 (2003) 於東方約瑟夫問題研究選析中所發表的結果有出入, 沈康身 (2003) 得到之結果如表 2-2, 表 2-2 骰子點數合對應最後一人位置

15 之位置其骰子點數合對應最後一人位置, 應為才是正確三貓食十三鼠問題我國近代創意數學遊戲之一, 其內容為 : 有十三隻老鼠被貓所捕獲, 十三鼠與貓商議, 表示十三鼠之中有肥美的白鼠一隻, 有一遊戲若貓有興趣可以共同參與, 可將他們十三鼠順便吃掉遊戲為 : 這十三鼠環形排列, 從那一隻開始, 十三個一數, 點數到十三的老鼠就被貓吃掉, 依序將全部十三隻老鼠通通吃完, 但白鼠要留到最後一隻, 結果貓思索很久而累到睡著, 十三鼠則重獲自由 ( 沈康身,2003) 貓食十三鼠問題, 只需考慮最後一個剩下的是肥美的白鼠, 只要從白色老鼠排在位置第 8, 則總數 13, 點數 13 而食之, 最後剩下的就是位置 8 的白鼠四航海問題航海問題的內容為 :15 個基督徒和 15 個異教徒同乘一船遠航, 途中遇大風浪, 船長指示 : 將全船乘客之半投入海中, 其餘人員才能確保平安, 船長要大家圍成圓圈, 從某人起點數, 至第 9 人, 把此人投下海, 照此繼續點數, 直到餘下 15 個乘客為止, 怎樣安排才能使 15 個基督徒全部不被投海? 此問題被稱為航海問題 ( 李啟印,2007) 航海問題中, 只需要考慮最後 15 個位置為何, 故解法與繼子立的相同, 將所有基督徒安排在等位置上, 則可以讓所有基督徒免於投海之危機, 於另一說法的航海問題只改變總人數, 解題的方法並沒有差異 10

16 五分桃問題五隻猴子分桃子, 老大先把桃子均分成五堆, 然後把剩餘的一個扔掉, 自己拿走了五堆中的一堆, 老二把剩下來的再均分成五堆, 又扔掉剩餘的一個, 自己拿走了這五堆中的一堆, 以後, 每隻猴子來了都是如此辦理, 問原來至少有多少個桃子? 最後至少有多少個桃子?( 張本源, 無日期 ) 解法 : 設原來有 N 個桃子, 第 n 隻猴子所得的桃子數為 X (n=1,2,3,4, 5), 則 N=5x +1, 且 5x =4x -1, 即 x = x - (n=2,3,4,5), 上述遞推式變形為 x +1= (x +1) (n=2,3,4,5), x = (x +1)-1, 其中 x 是整數, 且 N 要最小, 所以 x +1= 5, x = 4-1, 於是 N =5( 5-1)= 5-4=3121, 4x =4(4-1)= 4-4=1020, 原來至少有 3121 個桃, 最後至少有 1020 個桃六著色問題地圖上某一地區有 n 個國家相鄰, 但 n 個國家只有一個會共點, 現用紅黃綠三色給地圖染色, 但相鄰不同色, 問共有多少種染法?( 張本源, 無日期 ) 圖 2-2 解法 : 設共有 a 種染法, 對第一個國家 S 共有 3 種染法, 對第二個國家 S 共 11

17 有 2 種染法, 同理對 S S S S 每個國家均有 2 種染法, 共有 3 2 種, 而在對 S 之染色時, 是以 S 為參照的, 它有 2 種染法, 這兩種染法可能與 S 同色, 也可能與 S 不同色, 而 S 與 S 同色, 必須排除但 S 與 S 同色有多少種呢? 事實上, 只要把 S 與 S 之交界線拆除就成為同一塊, 這時就是 (n-1) 塊不同染法即 a 種, 故 a = 3 2 -a,a -2 =-(a -2 ) 因此, 數列{ a -2 }是首項為 a -2 =6-4=2, 公比為 -1 的等比數列, 即 a -2 =2 1 a = , 這就是所求的染色方法七登台階有一個 n 層的台階, 若每次可上一層或兩層, 那麼, 共有幾種上法?( 張本源, 無日期 ) 解法 : 設登 n 層台階的方法有 f(n) 種, 若第一回登一層時, 登其餘的 (n-1) 層的方法有 f(n-1) 種, 若第一回登兩層時, 登其餘的 (n-1) 層的方法有 f(n-2) 種 ; 所以, 登 n 層的方法應是 f(n)= f(n-1)+ f(n-2) 種, 又因為登一層台階的方法只有一種, 登兩層台階的方法有下面兩種, 一回登二層, 或者每回一層一層地登, 因此 f(1)=1 f(2)=2 即為 Fibonacci 數列, 可得 f(n)= - 登法, 則登 n 層台梯, 每次可上一層或兩層, 共有 - 種 12

18 第三章主要結果第一節遞迴關係式於 Josephus 問題中, 設 N 個人圍成一圈, 標號為 N-1, 從第一個人開始依次從 1 到 K 循環報數, 當報到 K 的人出圈設 J(N,K,I) 表示第 I 個出圈的人的位置標號因為起始位置為 0, 故 J(N,K,1) K-1(mod N),(N 1, K 1) (1) 設 J(N,K,I)= X, 因此如果有 N 個人, 從 0 開始報號, 第 I 個出圈的位值標號為 X 現在考慮 J(N+1,K,I+1), 因為 J(N+1,K,1) K-1 (mod (N+1)), 即第一步的時候刪除數字 K-1, 第二步的時候從數字 K 開始數起因而問題變為了找到剩下的 N 個數字中從 K 開始數起被刪除的第 I 個數字, 而這恰好就是 (X+K) (mod (N+1)), 可得 J(N+1,K,I+1) (K+J(N,K,I)) (mod (N+1)), ( N 1, K 1, 1 I N ) 故滿足末兩位相鄰, 對應 N K I 三個數值所得最後石子相對位置之遞迴關係式為 J(N+1,K,I+1) (K+J(N,K,I) (mod(n+1)) 遞迴關係式起始值 J(1,K,1)=0, 若 K 值為奇數, 則 J(2,K,2)=1,J(2,K,1)=0, 若 K 值為偶數, 則 J(2,K,2)=0,J(2,K,1)=1 總數 N 2 之相對位置可利用遞式子 J(N+1,K,I+1) (K+J(N,K,I) (mod (N+1)) 一一解出 ; 然而在本研究當中, 研究者利用 Excel 表中基本函數運算, 將遞迴式子簡單的以表列形式呈現當總數 N 值確定後, 由遞迴關係式 J(N+1,K,I+1) (K+J(N,K,I) (mod (N+1)) 可得最後一個被拿走之相位置為 J(N+1,K,N), 點數之起始位置則是由最後一個之相對位置反推即可得知 13

19 第二節總數 N 上限值差異在本研究的遊戲當中, 最後剩下的兩個白色石子, 在關係式中, 因為其位值標號必需相鄰, 而且依順時針方向點數的話,K 值為奇數時, 最後一顆其位值標號會大於最後第二顆的標號,K 值為偶數時, 最後一顆其位值標號會小於最後第二顆的標號若可以找到 J(N,K,N)- J(N,K,N-1) 1, 但必要考慮最後一顆位值標號為 0, 最後第二顆為 N-1 之特例, 則表示未兩個相鄰之情形不存在, 則可找出對應 K 值之總數 N 的上限值為何本研究以 K=9 為例, 將其相對位置表示如表 3-1, 表 3-1 J(N+1,9,I+1) (9+J(N,9,I)) (mod(n+1)) 最後一顆石子最後第二顆石子 J(N,9,N) (9+J(N-1,9,N-1)) (mod N) J(N,9,N-1) (9+J(N-1,9,N-2)) (mod (N-1)) 位值差 J(N,9,N) N 值 = 相對位置 J(N,9,N-1) N 值 = 相對位置

23 由表 3-1 得於 N=91 時出現其位值差不等於 1 的情形出現, 但其最後兩個仍處於相鄰的位值標號, 故 N=92 時本研究的遊戲才出現無解的情形依上述方法可找出 K= 所對應之上限值, 如表 3-2 所示表 3-2 K 值 N 值上限 K 值 N 值上限 K 值 N 值上限 K 值 N 值上限 K 值 N 值上限

24 對應 1 K 100 之總數 N 簡單分為三大類, 第一類 :K=1 時, 總數 N 值的大小不受限制皆可以滿足約瑟夫問題 ; 第二類 :K=2 5 8 只有 N=2 時成立,N 3 就無法滿足約瑟夫問題 ; 其餘探討之 K 值對應總數 N 的上限值皆不同, 所以方通中在數度衍中大膽假設, 九個一數對所有 N 值皆滿足約瑟夫問題, 其結果只有 K=1 滿足末兩位相鄰之條件,K=9 時, 總數 N 之上限值只是比其它的值大一些, 並非沒有限制第三節滿足條件之 K 值在本研究當中, 以遞迴關係式 J(N+1,K,I+1) (K+J(N,K,I) (mod(n+1)), 研究者利用 Excel 內預設之函數, 撰寫可輸入 K 值之試算表, 再以 matlab 所撰寫的程式檢驗, 根據遞迴關係式得到, 總數 N=50,K 100 時, 存在 K= ; 在 N=100,K 100 時, 還存在等四個小於 100 的數, 可以滿足約瑟夫問題, 其最後剩下的兩個數的位置分別如表 3-3: 19

25 表 3-3 K 值對應剩下位置最後一個位置倒數第二個位置依 matlab 程式檢驗 N=600, 及 K 600 之情形, 得以下結果如表 3-4: 表 3-4 K 值最後一個位置對應剩下位置倒數第二個位置故在固定總數 N 之值, 可找到滿足末兩位相鄰之條件的 K 值並不唯一, 且當 N 之值愈大, 滿足條件的 K 值愈少 20

26 第四章結論與建議第一節結論本研究旨在探討約瑟夫問題之起始相對位置問題及 N K 值之間的影響其結論如下 : 壹約瑟夫問題中, 對應 N K I 三個數值所得最後石子相對位置之遞迴關係式為 J(N+1,K,I+1) (K+J(N,K,I)) (mod(n+1)) 遞迴關係式起始值 J(1,K,1) =0, 若 K 值為奇數, 則 J(2,K,2)=1,J(2,K,1)=0, 若 K 值為偶數, 則 J(2,K,2)=0, J(2,K,1)=1,N 2 者之相對位置借由關係式即可計算得知貳在末兩位相鄰條件下, 當 K=1 時, 總數 N 值的大小不受限制 ;K=2 K=5 K=8 只有 N=2 時能滿足約瑟夫問題 ; 其餘探討之 K 值對應總數 N 的上限值皆不同, 所以當 K 值改變後, 即可推算出總數 N 上限值, 只有在比上限值還小的 N 值才能滿足約瑟夫問題參當總數 N=50,K 100 時, 存在 K= 可以滿足約瑟夫問題 ; 總數 N=100,K 100 時, 存在 K=1 K=16 K=49 K=57 可以滿足約瑟夫問題中末兩位相鄰之條件, 總數 N=600 時, 原本滿足的 K=16 K=49 K=57 皆無法滿足約瑟夫問題, 得知若 N 值愈大, 滿足末兩位相鄰條件的 K 值愈少第二節未來發展方向本研究主要探討約瑟夫問題當中, 找出最後會剩下兩個相鄰的位置但研究結果當中的 K 值改變, 得找出相對應 K 值的幾個起始值, 才能利用遞迴關係式, 21

27 演算出後面的 N 值的結果, 未來研究者可以依以下的方向進行探討 : 一固定 N 值, 求出滿足最後剩下兩個相鄰的 K 值間之關係式二找出 K=1 之外, 對應總數 N 上限值最大的 K 值三找總數 N, 滿足最後三個剩餘的相鄰的 K 值及其起始位置 22

28 參考文獻壹中文部分沈康身 (2003) 東方約瑟夫問題研究選析自然科學史研究, 第 22 卷第一期李啟印 (2007) 著名經典趣題之約瑟夫斯問題繼子立問題八仙落座問題數學奧林匹克報 2007 年 12 月 08 日, 取自約瑟夫問題 ( 無日期 ) 非關語言. 常見程式演算 2007 年 11 月 22 日, 取自張本源 ( 無日期 ) 漫談遞迴數列 2007 年 07 月 13 日, 取自 edu.tw/teacher/allteachers/math/zhang_ben_yuan/ 郭世榮 (2002) 方中通數度衍中所見的約瑟夫斯問題自然科學史研究, 第 21 卷第一期維基百科 (2007) 九連環 2008 年 01 月 15 日, 取自 wiki/ %E4%B9%9D%E9%80%A3%E7%92%B0 維基百科 (2007) 七巧版 2008 年 01 月 13 日, 取自 %E4%B8%83%E5%B7%A7%E6%9D%BF 維基百科 (2007) 華容道 ( 遊戲 ) 2008 年 01 月 17 日, 取自 index.php?title=%e8%8f%af%e5%ae%b9%e9%81%93_%28%e9%81%8a %E6%88%B2%29&variant=zh-hk 23

29 貳英文部分 A. Bogomolny. (n. d.). Josephus Flavius game, Retrieved July 05, 2007, from Harry J. Smith. (2006). Josephus Permutation Problems, Retrieved November 24,2007, from Peter B. Henderson. (n. d.). Josephus Flavius Problem, Retrieved July 17, 2007, from Butler University Department of Computer Science & Software Engineering, Web site: Weisstein, Eric W. (n. d.). Josephus Problem, Retrieved August 17, 2007, from Wikipedia.(2007). Josephus problem. Retrieved November 20, 2007, from 24

30 附錄附錄一題型圖解壹 12 個石子圍成一圈, 兩個白色相臨, 由 1 依續數到 9, 數到 9 的做記號去掉, 重復上述動作, 直到最後剩兩個白色相臨, 圖解如下 : : 為白色石子 : 為黑色石子 : 為被點數中拿掉之石子 I: 為被點數拿掉之次序 00 I=0 I=1 I=2 I=3 0 25

31 00 I=4 I=5 00 I=6 I=7 00 I=8 I=9 26

32 I=10 27

33 貳日本繼子立圖解說明 : : 為前妻之子 : 為後妻之子 : 為退出財產繼承資格 I: 為被點數退出繼承資格之次序 00 I=0 I=1 00 I=2 I=3 28

34 00 I=4 I=5 00 I=6 I=7 00 I=8 I=9 29

35 00 I=10 I=11 00 I=12 I=13 0 I=14 30

36 去除已失去資格之前妻之子, 依老人的條件轉向做約瑟夫問題 : 為前妻之子 : 為後妻之子 : 為退出財產繼承資格 D= 轉向後失去繼承資格的次序 0 D=0 D=1 D=2 D=3 31

37 D=4 D=5 D=6 D=7 D=8 D=9 32

38 D=10 D=11 0 D=12 D=13 D=14 D=15 33

39 參總共 41 人, 每三個一數自殺,Josephus 及他的朋友為, 其餘為, 自殺後變成了 I= 自殺的次序 00 I=0 I=1 00 I=2 I=3 34

40 00 I=4 I=5 00 I=6 I=7 00 I=8 I=9 35

41 00 I=10 I=11 00 I=12 I=13 00 I=14 I=15 36

42 00 I=16 I=17 00 I=18 I=19 00 I=20 I=21 37

43 0 I=22 I=23 00 I=24 I=25 00 I=26 I=27 38

44 00 I=28 I=29 00 I=30 I=31 00 I=32 I=33 39

45 00 I=34 I=35 00 I=36 I=37 0 I=38 I=39 40

46 附錄二電腦程式指令說明如下 : clear all;% 清除之前資訊 close all% 關閉之前開始之視窗 %N=91; % 讀入 input 參數 N=input('inout the total = '); l=input('inout the leave l = '); k=input('inout the K = '); F=N; P=ones(0,N-1); % 起始直皆為 0 % 產生等加數列 for i=2:n P(i)=P(i-1)+1; end % 開始計數 for i=1:n-l P(1:F)= circshift(p(1:f)',-k)'; % 環形移位 P(F)=-P(F); F=F-1; end 41

47 % 後面無分號即可以顯示 % 顯示前 l 個 P(1:l) % 顯示 l 到 N 個 P(l:N) % 顯示 N 值 N 壹輸入 N 值, 固定 K=9, 找出最後剩下兩個相鄰的位置 clear all; close all N=input('inout the total = '); F=N; K=9; P=zeros(1,N); for i=2:n P(i)=P(i-1)+1; end for i=1:n-2 P(1:F)= circshift(p(1:f)',-k)'; P(F)=-P(F); 42

48 F=F-1; end R=0; if ((abs(p(2)-p(1))==1) (abs(p(2)-p(1))==n-1)) R=1; end R P(1:2) N 貳輸入 N K 值, 找出最後剩下兩個相鄰的位置 clear all; close all N=input('inout the total = '); F=N; K=input('inout the K = ');; P=zeros(1,N); for i=2:n P(i)=P(i-1)+1; end for i=1:n-2 43

49 P(1:F)= circshift(p(1:f)',-k)'; P(F)=-P(F); F=F-1; end Existance=0; if ((abs(p(2)-p(1))==1) (abs(p(2)-p(1))==n-1)) Existance=1; end Existance P(1:2) N 參輸入 N K 值,K 由 1 檢驗到 K, 找出最後剩下兩個相鄰的位置 clear all; close all N=input('inout the total = '); K=input('inout the K = '); W=N; Existance=zeros(1,K); for k=1:k N=W; 44

50 F=N; P=zeros(1,N); for i=2:n P(i)=P(i-1)+1; end for i=1:n-2 P(1:F)= circshift(p(1:f)',-k)'; P(F)=-P(F); F=F-1; end if ((abs(p(2)-p(1))==1) (abs(p(2)-p(1))==n-1)) Existance(k)=k; P(1:2) end end Existance(1:K) N 肆輸入 N K 值, 找出最後剩下 L 個的位置 clear all; close all N=input('inout the total = '); l=input('inout the leave l = '); k=input('inout the K = '); 45

51 F=N; P=zeros(1,N); for i=2:n P(i)=P(i-1)+1; end for i=1:n-l P(1:F)= circshift(p(1:f)',-k)'; P(F)=-P(F); F=F-1; end P(1:l) P(l:N) 46

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0