假設有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進位表示就是
。
有興趣了解更多請搜尋
約瑟夫斯問題。