死裡逃生

有一個探險家深入蠻荒地區，意外受到一個部落的盛情款待後，不幸遇到該部落的世仇來攻擊，部落族人和探險家總共３1 人，一起困在山洞，山洞外盡是世仇，部落族人知道已經無路可逃，決定寧死不降。他們圍坐在一圓圈上，由酋長開始循順時鐘報數1、2、1、2、....，報數2的人得先慷慨成仁，直到所有人都殺身成仁為止。

其實，探險家在一開始就不想平白枉死，早就盤算出應該坐在那一個位置才會最後輪到自己，就可以死裡逃生。

我們不評斷冒險家的作為 , 僅就數學面來討論 , 我們假設有 N人圍成一圈 , 順時鐘依序編號1~N，由1號開始循順時鐘報數1、2、1、2、....，報數2的人就退出圓圈 , 用L（N）表示最後留下的那一個人的最初編號。

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	2⁰	2¹		2²				2³
L(N)	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15

N	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
	2⁴
L(N)	1	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31

從上表可以得知下列的遞迴關係：

L(1)=1
L(2N)=2L(N)－1，N≧1
L(2N＋1)=2L(N)＋1，N≧1。

甚至可得知公式L(N)=1+2(N-2ⁿ)，其中 2ⁿ≦N<2ⁿ⁺¹ 。

現在，應該知道探險家在開始時選擇坐在哪一個位置了？ (總共３1 人圍成一圈)

L(31)＝L(2×15＋1)＝2×L(15)＋1=2×15＋1＝31 或者

L(31)=1+2(31-2⁴)=1+2×15=31　。

如果上述故事裡部落族人和探險家總共有42人，則探險家選擇哪個位置才會是最後留下的人？

L(42)=1+2(42-2⁵)=21，探險家一開始坐在從酋長算起，順時鐘方向的第21位，才會是最後留下的人。