死裡逃生

死裡逃生
有一位數學家正在蠻荒探險，就在一部落做客時，遇到外族強力來犯，酋長帶著族人和數學家總共３1 人，一同被圍困在一個山洞內，正面臨著無可避免的失敗 ，他們下定決心， 不成功便成仁 ，寧死不降 。

於是他們決定安排自己在一圓圈上，其中酋長被指為 1 號， 然後開始進行他們的決定 ，方法是順時針方向由 1 號算起， 每二人按順序自殺， 直到所有人都死光為止。 很明顯的第一圈之 2，4，...， 28, 30 相繼自殺 ， 接下來的是誰 ? 應該是 32 號嗎 ? 但他們才只有 31 人， 所以 32 除以 31 餘數是 1 , 接下來應該是輪到 1 號 ,再接下來的並不是 3 號， 因為 2號和 4號剛才己經自殺身亡了， 我們這次不算他們， 所以下一個是跳過 3 號的 5 號 ，依此類推。數學家不想平白死掉，但是又怕族人笑他懦弱，因此，他立即算出自己應該站在那一位置才是最後輪到的，如此他就不必犧牲了。我們不來評斷數學家的勇氣 , 僅就其數學層面來看，以一般的討論來看 , 我們假設有 N人排成一圈 , 每二人退出圈 , 用L（N）表示最後留下來的人，為了探究L(N)的答案 , 更多的實驗可以得到更多數據， 引進適當的公式 , 可以節省時間， 一組可能的遞迴公式是如下：

L(1)=1
L(2N)=2L(N)－1，N≧1
L(2N＋1)=2L(N)＋1，N≧1。
利用這公式 , 我們快速的得到下面的資料 :
N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
L(N)
1
1
3
1
3
5
7
1
3
5
7
9
11
13
15
1

現在你該知道數學家站在哪一位置了嗎？

L(31)＝L(2×15＋1)＝2×L(15)＋1=2×15＋1＝31。