天生贏家的奧秘─『傳遞問題』之研究與探討

國中組　第三名

縣　市：台北市

校　名：介壽國中

作　　者：簡民惠

指導教師：李艷卿

我住在台北都會區裡，現在就讀於介壽國中三年級，我的家庭很單純，有兩個哥哥，父母親都上班，經營資訊事業，由於父母親都是理工的背景，所以特別注意我們的邏輯分析和推理的能力，鼓勵支持我參加各種活動，包括五次科展，我發現學習「如何學習的方法」才是最重要的，而不是解題目的技巧。

關鍵詞：搜尋、遞迴、數學歸納法

壹、研究動機

去年參加建中「中學生數學通訊解題」時，發現第二期88205斟酒問題,內容充滿了思考和推理的趣味性，引發我研究的動機。(原題摘錄如下)：(如附件一)

n個客人圍坐一圓桌,按逆時針方向依次編號1,2,3,…n。服務員先給1號座位斟酒，然後再按逆時針的方向斟，但每次都要跳過兩個未被斟酒的客人（已斟過酒的客人自然也跳過），才給下一位客人斟酒，但最後一位客人不受此限制。試問：最後一位斟到酒的客人的座位編號是多少?

　

在思索問題的過程中，處處充滿了難題與挑戰，因此我到圖書館尋找解題相關線索，想從相關文獻資料中，探討其研究方式。我找到--民國８４年我國參加紐西蘭第十九屆科學展覽的科展作品名稱：劫後餘生(其研究題目如下)：(如附件二)

「有一個古代的故事」，歷史學家約瑟夫與他的四十位猶太同伴為逃避羅馬人的追殺而躲在一個山洞裡。這些人寧死也不願被俘虜，最後眾人決定輪流自殺，先指定首領為１號，然後大家接著首領圍成一圈，從１號算起，每次算到第三個存活的人就必須自殺，直到全部死光為止。約瑟夫並不贊成，但為了求生存，他只好預先算好一個位置，使得站上這個位置的約瑟夫在輪流次序中是最後一個人。結果，約瑟夫終於避開了自殺的命運。 我們好奇的是，在危急之時，約瑟夫如何冷靜地算出最後存活的位置，難道他有速算的公式?」

　

及民國85年第二十九屆台北市高中組科展優勝作品「天算不如人算」:（如附件三）

並在網上瀏覽台師大數學系網站時，發現科學教育月刊通訊解題第2035題，傳錢幣問題有類似作法（其題目如下）：（如附件四）

　

ｎ個人圍成一圈玩遊戲，ｎ大於等於４，首先他們依反時針方向依序編號為１號、2號、．．．ｎ號。且讓每個人手上都有一枚銅板，遊戲規則如下：遊戲開始，１號拿一枚銅板給２號，然後２號拿二枚銅板給３號，接著３號拿一枚銅板給４號，４號拿二枚銅板給下一位，規定遊戲過程中，手上沒有銅板的人，他就自動出局，離開此遊戲，而遊戲繼續下去，如此依次拿一枚，拿二枚給下一位手上仍有銅板者。試證有無限多個ｎ使這個遊戲最後僅剩一人，而其餘的人均出局。

我覺得此題目在傳遞過程中，隱藏了數學規律在其中，更使我有進一步深入研究的興趣。

貳、研究目的

1.首先研究斟酒問題(每次斟酒只跳過一人之情況)。

n個客人圍坐一圓桌，按逆時針方向依次編號1,2,3,...，n。服務員先給1號座斟酒，然後按逆時針方向斟，但每次都要跳過一個未被斟酒的客人(已斟過酒的客人自然也跳過),才給下一位客人斟酒，但最後一位客人不受此限制，試問：最後一位斟到酒的客人的座位編號是多少?

2.其次研究斟酒問題(每次斟酒只跳過二人之情況)並加推廣一般性的情形。

3.探討傳錢幣問題：

(1)傳遞方式為傳一枚、二枚的循環方式，當總人數ｎ為多少時，最後會只剩下   一人?

(2)找出最後一人的原始編號ｍ?

(3)討論一般狀況，總人數ｎ及未出局人之編號ｍ之對應號碼表。

(4)如果改變了遊戲的規則後（諸如傳錢幣的方式，由原先傳一枚、二枚的循環  方式，改成一枚、二枚、三枚的循環方式）是否能得到相同之結果，遊戲結  果是否會剩下一人？能知道那些人會出局？

(5)將此研究之方法，推廣應用在解答一般性問題上，即總人數ｎ，傳遞方式為一枚、二枚、．．．至ｍ枚循環方式，探究最後一般性之結果。

　

參、研究方法

1.首先蒐集相關文獻並探討其研究方式。

2.其次將所探討問題中之規則、設計成電腦程式，利用電腦快速計算的特點及正確性，觀察並了解數據間變化的情形，協助規律的尋求及驗證。

3.最後利用數學歸納法，證明所得之結果以了解天生贏家的奧祕。

　

肆、研究過程

1.斟酒問題 (每次斟酒只跳過一人之情形)：

 n個客人圍坐一圓桌,按逆時針方依次編號1,2,3,...n。服務員先給1號座位斟酒，  然後再按逆時針的方向斟，但每次都要跳過壹個未被斟酒的客人（已斟過酒的 客人自然也跳過），才給下一位客人斟酒，但最後一位客人不受此限制。試問：

最後一位斟到酒的客人的座位編號是多少?

(1)首先將問題設計成電腦程式，搜尋最後一位斟酒客人編號ｍ值。

例：

斟酒問題：每次跳過1人　客人總數：10
圓桌客人編號	1  2  3  4  5  6  7  8  9  10
第一輪斟到酒客人編號	1，3，5，7，9
第二輪斟到酒客人編號	2，6，10
第三輪斟到酒客人編號	8
最後一位斟到酒客人編號	4

(2)整理所得結果，如表（一）

　

表（一）

客人總數ｎ	1	2	3	4	5	6	7	8	9
最後編號 ｍ＝(an)	1	2	2	4	2	4	6	8	2

10	11	12	13	14	15	16	17	18	19	20
4	6	8	10	12	14	16	2	4	6	8

(3)歸納，尋求最後編號an

觀察an規則，發現an序列中斷斷續續有一群公差為2的等差數列，例如從 a9，a10，a11，a12，a13，a14，a15即為一組群，但是每遇到a2K＋１(K為正整數或０)   時；卻使等差規律又從2開始，如a9∼a16的這組群在a17時之對應值為2而非18，如a5∼a8， a3∼a4等。事實上當預期對應值超過原來ｎ之總數，等差規律便會消失，並從頭開始，所以我們歸納出2^K項顯然是兩組群等差數列的分界。 因為a1＝1，a2＝2，a4＝4，a8＝8，a16＝16，故可以猜測出a2^K=2^K（其中   K為正整數或0）。

(4)證明當客人總數n＝2^K時，最後一位被斟到酒的客人編號ｍ＝a2^K=2^K (其中 其中Ｋ為正整數０）。

以數學歸納法證明之

當ｎ＝2⁰＝1時，a1＝1＝2⁰原式成立

設當ｎ＝2^K時，a2^K=2^K原式亦成立

當ｎ＝2^K＋１時，第一輪從1號開始斟酒，3號，5號，一直到2^K＋1－1號，第二輪斟酒，可以把剩下偶數號客人加以重新編號，如下表（二）所示：

表（二）

客人原編號	2	4	6	8	...　m	m＋2	...	2K＋1
客人新編號	1	2	3	4			...	2K

 此時第二輪開始時，共有2^K人需要斟酒，由ｎ＝2^K時，最後一位被斟酒   的客人應該是新編號2^K，即對照原編號為2^K＋１，故得證ｎ＝2^K＋1時，最   後一位被斟酒客人編號ｍ＝a2^K＋1＝2^K＋1

 即得證ｎ＝2^K＋1時，原式亦成立。

 由數學歸納法可得證，對所有0或自然數K

 當人數為ｎ＝2^K時，最後一位斟酒客人的編號為2^K

(5)推廣

由等差方法可算得，客人總人數ｎ，對應到最後一位客人編號aｎ，即整理成1 2 兩關係式

1 當ｎ＝2K      K為自然數或０　則an＝2K 2 當ｎ≠2K　 K為自然數或０，即ｎ為介於2K及2K＋1間之正整數　則an＝2(ｎ－2K）

(6)用數學歸納法證明上式成立

當ｎ＝3時　a3＝2（3－2¹）＝2　原式成立

（∵3介於2¹和2²之間）

設當ｎ為介於2^K及2^K＋１間的正整數

an＝2（ｎ－2^K）　原式亦成立

(7)將上述結果表成遞迴一般式：

由(4)之證明過程中，可以推得

(ㄅ)若人數ｎ，ｎ－1介於2^K及2^K＋1之間，則由（5）2

得an－an－1＝2(ｎ－2^K)－2[(ｎ－１)－2^K]＝2

故an＝an－1＋2，即組群間為公差2之等差數列

(ㄆ)若n = 2^K+1時，則2^K < n - 1 < 2^K+1，由1 2 得

 an－an－1＝2^K＋1－2[(ｎ－１)－2^K]＝2•2^K＋1－2ｎ＋2＝2

觀察(2)及(6)之結果，若an－1≦ｎ－2則an＝an－1＋2

若ｎ－１＝2^K則2^K＜ｎ＜2^K＋１且an－1＝2K

故由(5)1 2 可得

an－an－1＝2(n－2^K)－2^K=2[n－(n－1)]－(n－1)=2－(n－1)

而此時an－1＝2^K＝ｎ－1＞ｎ－2

綜合整理得

3 當ｎ＝1時　a1＝1　而當ｎ≧2時     若an－1≦ｎ－2　則an＝an－1＋2     若an－1＞ｎ－2　則an＝an－1＋2－(ｎ－１)

    3 式的遞迴式有助於解決斟酒問題之最後一般性結果

伍、結論

(一)斟酒問題：

n個客人圍坐一圓桌,按逆時針方依次編號1,2,3,...n。服務員先給1號座位斟酒，然後再按逆時針的方向斟，但每次都要跳過Ｋ個未被斟酒的客人(Ｋ大於１之自然數)(已斟過酒的客人自然也跳過)，才給下一位客人斟酒，但最後一位客人不受此限制。試問：最後一位斟到酒的客人的座位編號an是多少?

1.當K＝1時：

ｎ＝１時　a1＝１

ｎ≧2時  若an－1≦ｎ－2　則an＝an－1＋2

　　　　 若an－1＞ｎ－2　則an＝an－1＋2－(ｎ－1)

2.當K＝2時：

ｎ＝1時　a1＝1；ｎ＝2時　a2＝2

ｎ≧3時  若an－1≦ｎ－3　則an＝an－1＋3

　　　　 若an－1＞ｎ－3　則an＝an－1＋3－(ｎ－1)

3.當K＝ｍ時　此時1≦ｍ＜ｎ　且ｍ為自然數

ｎ≧ｍ＋1時 

若an－1≦ｎ－(ｍ＋1)　則an＝an－1＋(ｍ＋1)

若an－1＞ｎ－(ｍ＋1)　則an＝an－1＋(ｍ＋1)－(ｎ－1)

(二)傳錢幣問題

ｎ個人圍成一圈玩遊戲，ｎ≧４，首先他們依反時針方向依序編號為１號、  2號、．．ｎ號。且讓每個人手上都有一枚銅板，遊戲規則如下：遊戲開 始，1號拿一枚銅板給2號，然後2號拿二枚銅板給3號，接著3號拿一枚銅板給4號，4號拿二枚銅板給下一位，規定遊戲過程中，手上沒有銅板的人，他就自動出局，離開此遊戲，而遊戲繼續下去，如此依次拿一枚，拿二枚給下一位手上仍有銅板者，則遊戲結果如下：

1.當總人數為2^ｔ＋1或2^ｔ＋2（ｔ為正整數或０），遊戲結束，最後會剩下１人。

2.當傳遞規則改為一枚、二枚、三枚之循環方式，則總人數為3^ｔ＋1, 3^ｔ＋2,或3^ｔ＋3（ｔ為正整數或０），遊戲結束後最後會剩下１人。

3.傳遞規則改為一枚、二枚、三枚,,....Ｋ枚之循環方式，則總人數為Ｋ^ｔ＋1, Ｋ^ｔ＋2,或Ｋ^ｔ＋3,.... Ｋ^ｔ+Ｋ（ｔ為正整數或０），遊戲結束後最後會只剩下1人。

陸、參考資料

1.高中數學第一冊課本（大同資訊88年版）李虎雄　陳昭地等編著P106∼P120頁

2.中學生通訊解題第二期題目，科學教育月刊第224期（88年11月號）P24∼P25頁

3.中華民國第三十五屆中小學科學展覽優勝作品專輯　(民84年)　高中組：劫後餘生　卓秋儀　P301∼P308（如附件二）

4.台北市第二十九屆中小學科學展覽優勝作品專輯　(民85年)　　高中組：天算不如人算　王昭仁等3人（如附件三）

5.數學歸納法縱橫談（1999）夏興國著　九章出版社出版

6.數學與猜想　波里亞著　李心燦等人譯　    九章出版社

7.網頁：(1)www.ck.tp.edu.tw 建中中學生通訊解題88205

　　　(2)www.math.ntnu.edu.tw (同附件一)

　　　台師大中學數學挑戰題2035題　(如附件四)

評語

本作品探討所謂斟酒問題，作者從已知的問題出發，加以推廣。數學的推導頗嚴謹，亦知使用適當的數學工具，如數學歸納法，最後並以電腦程式以展示數據間的變化，不論在題材，數學理論及程式方面，均達相當水準，作者表達能力也很好，穩健且具信心為一可造之材。