約瑟夫數列(Josephus Series)

科展類別
臺灣國際科展
屆次
2006年
科別
數學科
學校名稱
臺北縣立江翠國民中學
指導老師
顏榮皇
作者
葉佩雯
關鍵字
約瑟夫數列 環狀

摘要或動機

所謂約瑟夫數列,就是有n 個數排成一環狀,從頭開始,殺1(個數)留1(個數),求倒數第k 個留下的數會是多少?約瑟夫數列在台灣的全國中小學科學展覽出現多次(如下表)。全國科學展覽與本題類似的作品

全國科學展覽與本題類似的作品

資訊界演算法大師Donlad E. Knuth 在其著作The Art of Programing,CONCRETE MATHEMATICS,也針對該數列作詳細的說明。唯,不論是歷屆科學展覽或是大師的著作,對於該數列,都只是談及殺1
留β或是殺α留1。

筆者則在2005 年暑假,曾經提交於全國國小組比賽作品「老師無法解決的難題」討論到n 個人排成一圈經過殺α留β,最後留下來的情形。

本研究是將α、β、k 和n 作為變數,求:當有n 個數排成一環狀,從頭開始,殺α(個數) 留β(個數),則倒數第k 個留下的數會是多少?

需符合α、β、k、n 皆∈N,且n≧k


1.直觀觀察:發現在每一個循環中,當n 等差α時,Aα,β,n,k 則等差α+β、n- Aα,β,n,k 則等差β。

2.分類:將其分類為cα,n,使當中有規律可求。

3.循環觀察:發現每個循環的尾數n- Aα,β,n,k 都小於β。


4.循環尾數:設計公式求出每個循環節的尾數n、留下數Aα,β,n,k 及n-Aα,β,n,k

5.倒推:由與循環節中有等差的性質,則可以由循環節的尾數,推論出循環節中的任意一數。

Joseph Sequence is the problem that discussed the situation of eliminating1 and
retaining1 in the circle formed by n people. Joseph Sequence has appeared a number
of times in National Elementary School and Middle School Science Fair in Taiwan
(as shown in the table below). Past national science fairs and researches on Joseph
Sequence

Past national science fairs and researches on Joseph Sequence 


The publications,The Art of Programing,CONCRETE MATHEMATICS ,by the expert of mathematical
calculation in the IT industry,Donlad E. Knuth,has provided detailed explanation
on it. However, all of those only discussed eliminating 1 and retaining β or eliminating
α and retaining 1.

The researcher proposed “Problems unsolved by teachers” in the national competition,
and discussed the situation of eliminating α and retaining β in the circle formed
by n people. This study continued the summer project of 2005, and conducted research
on the question of when is the last kth person eliminated in a circle formed by
n people. In the paper, α, β, n and k were independent variables and the research
process was as follows:


1. Direct observation: the series shows equal difference in each cycle.

2. Classification: to search the pattern of the series based on cα,n classification.



3. Use the end number of each cycle to obtain the pattern.

4. Reverse induction: use the equal difference of each cycle to induce when the
kth person would be eliminated.



「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
約瑟夫數列(Josephus Series) 735 KB Adobe Reader(Pdf)檔案