上一道數學謎題
下一道數學謎題

死裡逃生數學謎題

答對率:90%
一位數學家在蠻荒探險,在部落做客,卻遇到外族強力來犯,酋長帶著族人和數學家共31人一同被圍困在一個山洞中,正面臨著無可避免的失敗,他們下定決心,不成功便成仁,寧死不降。於是他們決定安排自己在一個圓圈上,其中酋長被指為1號,然後開始進行他們的決定方式是順時針由1號算起,每2人按順序自殺,直到所有人死光為止。很明顯第一圈之2、4、6、8......28、30相繼自殺,接下來因為沒有32號,所以應該輪到1號。因為2、4已自殺,所以下個號碼3號跳過,該自殺的輪到5號,以此類推。數學家不想白死,但又怕族人笑他懦弱,因此他必須站在最後一個自殺的號碼上,如此沒有人會知道他有沒有按照規矩自殺,便可保留生命走向投降之路。當下情況緊急,這位數學家很快便決定了他的號碼......試問這位數學家選幾號?又是如何快速選出的?
看答案
31

解析

我要編輯
假設有N人圍成一圈,用L(N)表示最後存活的人,會有以下遞迴關係:
  • L(1)=1
  • L(2N)=2L(N)-1,N大於等於1
  • L(2N+1)=2L(N)+1,N大於等於1
說明:
  • 全部只有1人時,顯然他會存活。
  • 全部有2N人時,繞完一圈時(回到1身上)只剩1,3,5,...,2N-1,
    這些人被看成是重新編號成1,2,3,...,N並且進行相同的遊戲,
    如果已知這N人中第L(N)個可以存活,
    ​對應回原來的2N人中就是第2L(N)-1個能存活。
  • 全部有2N+1人時,繞完一圈(回到1身上)時只剩3,5,...,2N+1,
    這些人被看成是重新編號成1,2,3,...,N並且進行相同的遊戲,
    如果已知這N人中第L(N)個可以存活,
    ​對應回原來的2N人中就是第2L(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(2x15+1)=2L(15)+1=2x15+1=31

一個有趣的結論:
如果N用2進位表示為
L(N)用2進位表示就是
有興趣了解更多請搜尋約瑟夫斯問題
4,424
上一道數學謎題
下一道數學謎題