死裡逃生

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

L(1)=1
L(2N)=2L(N)1N1
L(2N1)=2L(N)1N1

利用這公式 , 我們快速的得到下面的資料 :

     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。 

 


Copyright ©1999~2002 昌爸工作坊 all rights reserved