600個人站一排，每次隨機殺掉一個奇數位的人，幾號最安全？

12-03

最安全參考兩種定義方式:
殺死需要的次數的期望值最大。
成為最後一個被殺死的概率最大。

修正之後的結論：存活回合數期望最大的應該是2，但最可能成為最後一個存活的人的是600。

我們來研究M個人殺N次的情況下，每個位置被殺的概率 $P(k;M,N)$ 。
可以用遞推法計算。首先2個人殺一次的情況下，2一定是最好的， $P(1;2,1) = 1$ ， $P(2;2,1) = 0$ 。M個人殺一次的情況下，偶數被殺概率為0，奇數被殺概率相等： $P(2k; M, 1) = 0$ ， $P(2k+1; M, 1) = frac{1}{lceilfrac{M}{2} ceil}$
考慮M+1個人殺N+1次的情況，則很容易得到：
$P(2k; M+1, N+1) = frac{k}{lceil frac{M + 1}{2} ceil} P(2k-1; M, N) + (1-frac{k}{lceil frac{M + 1}{2} ceil}) P(2k; M, N)$
$P(2k + 1; M+1, N+1) = frac{1}{lceilfrac{M + 1}{2} ceil} + frac{k}{lceil frac{M + 1}{2} ceil} P(2k; M, N) + (1-frac{k + 1}{lceil frac{M + 1}{2} ceil}) P(2k+1; M, N)$
我們定性分析一下這個式子，無論奇數還是偶數，都從(M,N)的情況中，繼承自己和前一項的「陣亡」概率，同時補上自己是奇數（有被殺概率）或者是偶數（無被殺概率）的修正值。k越小，前一項加權越小，後一項加權越大。奇數項有額外的加成。這樣，k比較小的情況下，奇數項和偶數項的差異越來越大；而k越大，由於前後兩項平均、甚至前項比例超過後項的效果，奇數項和偶數項的差距變得越來越小。
迭代下去的結果大致是一個上下波動然後衰減的樣式：1的被殺概率最大，2最小，3又變大但小於1，4又變小但大於2，依次類推。M和N都比較大的時候，靠後位置的奇數位置、偶數位置差異變得很小，因為它們經常相互轉換。而1永遠是奇數；2隻有很小的概率會轉換成1。N越大，存活概率的絕對值都變小，但存活概率與前後位置的關係變得更大，2的相對安全優勢也越明顯。如果考慮最後一個存活的人的比例的話，N很大的情況下，2的優勢會很明顯。
====================================================================
事實證明全憑臆想是不好的……這裡忽略了一件事，一開始在2，和最後幾輪在2，意義是完全不同的。一開始奇數多，每個奇數被殺概率比較小，而最後幾輪被殺概率嚴重提高，而一開始在2的，很容易就滑到1去了。還是老老實實算一下遞推式……
存活概率：

殺至最後一人的存活概率。這也太直了吧！
但其實並不是完美直線，而是奇數偶數一組跳變的，1的存活概率是0，（2,3）的存活概率幾乎一樣，（4,5）的存活概率幾乎一樣，依次類推，所以最後存活概率最大的是600，它存活的概率幾乎就是1/300。
實際上似乎有 $P(2k; M, M-1) = P(2k+1; M, M-1) = 1 - frac{k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil}$
我們代回去檢驗一下：
$P(2k; M+1, M) = frac{k}{lceil frac{M + 1}{2} ceil} P(2k-1; M, M - 1) + (1-frac{k}{lceil frac{M + 1}{2} ceil}) P(2k; M, M - 1)$
$= frac{k}{lceil frac{M + 1}{2} ceil} (1 - frac{k - 1}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil}) + (1-frac{k}{lceil frac{M + 1}{2} ceil})(1 - frac{k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil})$
$= 1 - frac{k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil} + frac{k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceillceil frac{M + 1}{2} ceil}$
$= 1 - frac{(lceil frac{M + 1}{2} ceil - 1)k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceillceil frac{M + 1}{2} ceil}$
$= 1 - frac{lceil frac{M - 1}{2} ceil k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceillceil frac{M + 1}{2} ceil}$
$= 1 - frac{k}{lceil frac{M}{2} ceillceil frac{M + 1}{2} ceil}$
$P(2k + 1; M+1; M) = frac{1}{lceilfrac{M + 1}{2} ceil} + frac{k}{lceil frac{M + 1}{2} ceil} P(2k; M, N-1) + (1-frac{k + 1}{lceil frac{M + 1}{2} ceil}) P(2k+1; M, N-1)$
$= frac{1}{lceilfrac{M + 1}{2} ceil} + (1-frac{1}{lceil frac{M + 1}{2} ceil}) (1 - frac{k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil})$
$= frac{1}{lceilfrac{M + 1}{2} ceil} + frac{lceil frac{M - 1}{2} ceil}{lceil frac{M + 1}{2} ceil}(frac{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil - k}{lceil frac{M}{2} ceillceil frac{M-1}{2} ceil})$
$= 1 - frac{k}{lceil frac{M}{2} ceillceil frac{M + 1}{2} ceil}$

這提示我們也許應該用存活概率來表示遞推式，改寫一下，用Q(k; M, N)來表示存活概率：
$Q(2k; M+1, N+1) = frac{k}{lceil frac{M + 1}{2} ceil} Q(2k-1; M, N) + (1-frac{k}{lceil frac{M + 1}{2} ceil}) Q(2k; M, N)$
$Q(2k + 1; M+1, N+1) = frac{k}{lceil frac{M + 1}{2} ceil} Q(2k; M, N) + (1-frac{k + 1}{lceil frac{M + 1}{2} ceil}) Q(2k+1; M, N)$
的確可以去掉那個常數項，改寫成齊次的遞推式。

在N不為M-1的時候，得到的結果跟之前的分析基本一致（Q(600,300)）：

（0實際上是1）
當N增大的時候，這個圖也有變化，下圖是Q(600,500)：

最安全的已經不是2了，而是向後移動，但並沒有移動到非常遠的地方。
進一步增大的時候（Q（600,550））：

中間大部分地方都變平了，但是注意看那個尾巴，會下降一些，原因不明，但應該不是計算誤差，因為隨著N增大，這個尾巴變得越來越明顯，以至於到599的時候，尾巴變成了整條直線。
更有趣的是這個尾巴的朝向跟N的奇偶性密切相關（Q（600,551））：

尾巴變成向上了。
N接近於599的時候：
Q（600,595）

波動越來越不明顯，而尾巴越來越明顯。
Q（600,596）

Q（600,597）

Q（600,598）

變成了一個這樣的奇怪曲線……
然後599就突變成了直線。只能說，數學真是太奇妙了。附Python代碼：

def fr(a,b = None): if b is None: return a else: return float(a) / float(b)


# Uncomment the following line to use fractions
# from fractions import Fraction as fr
def cal_p(m, n):

    P = [fr(0)] * (m - n + 1)

    for M in range(m - n + 1, m + 1):

        P2 = [0] * (M+1)

        half = (M + 1) // 2

        P.append(fr(0))

        for i in range(1, M + 1):

            if i % 2 == 0:

                P2[i] = fr(i // 2, half) * P[i-1] + fr(half - i//2, half) * P[i]

            else:

                P2[i] = fr(1, half) + fr(i // 2, half) * P[i-1] + fr(half - i//2 - 1, half) * P[i]

        P = P2

    return P
import matplotlib.pyplot as plt

def plot_q(M,N): P = cal_p(M,N) q = [1.0 - p for p in P[1:]] plt.figure() plt.plot(q) plt.show()

如果考慮存活回合數的期望值的話，由於N很大的時候存活概率本身就比較小，最後的確應該是2的平均存活回合數比較有優勢吧。

解釋一下當N比較大的時候，為什麼隨著N的奇偶性變化，最後一段的概率忽大忽小呢？
因為我們的M = 600是個偶數，當殺奇數人的時候，最後一輪排在最後一個位置的人不會被殺，而殺偶數人時，最後這一輪排在最後一個位置的人可能被殺，而就是這一點點差別導致了差異；殺奇數人時，最後一段很容易成為最後一個人，所以存活概率變大了，在殺599人的時候，甚至這是唯一的存活可能性；殺偶數人時，反而是成為倒數第二個人比較划算，所以最後一小段反而概率下降了。

猜一猜，598那個曲線的極值點在什麼位置？

在[0,600]的黃金分割點上。

謝邀?~?
按照題主的描述，這個問題分為兩問:
兩問的答案分別為600號和2號

一、簡單的數據打表以及初步分析答案給出

(1)活到最後一個的那個人，幾號概率最大

反對有好多人以如下原因說是2號:除非1號死了，否則2號不會死——但是1號必死無疑，之後2號就成了1號，於是2號能活下來，當且僅當1號能活到「決賽」，這個概率是很小的。

反對有好多人純「臆斷」512號，或是「中間某個號」，「偶數比奇數安全」之類的答案，其實只要前面某個人一死，後面的奇偶性就會全部改變，並且初期死亡概率其實很小（平均下來每個人會有99%+的最終死掉，而初期那幾輪那怕一直是奇數也只佔百分之幾的概率，並不足以產生什麼影響），所以初始狀態是奇數或是偶數並不會對這個問題產生本質性的影響。

對於「這就一道數學題，那些mark了去寫代碼的是傻逼么？」的回答，我想文明用語。對於一眼看不出答案的問題，編程猜出答案後數學驗證是最為嚴謹的做法。最主要的，這種方法省時間。此類題只要知道結果了，用數學歸納法分分鐘就證畢。

編程結果是:越往後存活概率越大
1＜2=3＜4=5＜6=7...以此類推，並且1,3,5,7...它們存活的概率是以0為首項的等差數列
下面是600個人時的概率打表（因為表太長了，所以只打了表頭和表尾
懷疑結論正確性的可以拿n比較小的時候手算驗證（比如n=2,3之類的

猜出了結論時候對n用數學歸納法不難從數學層面證明。

(2)活的輪數的數學期望，誰最大

如諸位所願，這次變成了2號，但是領先優勢並沒有臆想里那麼霸道。並且除了位置靠前的幾個倒霉蛋存活期望值不太穩定之外，號大的朋友幾乎都能期望活300輪左右（其實除了1號比較倒霉平均少活100輪意外，其他人都是「差不多」平均活300輪，只不過2號能稍微多活微不足道的幾輪罷了）

至於這一問的數學解釋應該蠻難給的，通項公式都未必能很簡單的寫出來。

二、深入分析以及評論區「答疑」

1.對於上述規律的數學證明

成為「唯一倖存者」的概率的 等差數列規律（並且很容易分奇偶給出通項公式
活的輪數的數學期望值：奇數位遞增，且趨近於總輪數的1/2；偶數位遞減，且趨近於總輪數的1/2；1號大約是總輪數的1/3,2號大約是總輪數的5/9...（這裡甚至可以給出任何一位的期望值是總輪數的百分之多少，用到一點高中組合知識即可證明）

上述結論的證明極其簡單，且毫無意義。故略
（有興趣的看官可以用數學歸納法自行證明，用到知識不超過高中課本範圍）

2.「怎麼模擬隨機過程？不是偽隨機嗎？」

知道計算機是「偽隨機」是好的，但是你還應該知道取time作為seed之後就無限趨近於真隨機了（如果你能精確到毫秒按滑鼠的話它依然是偽隨機，否則就是真的）
這裡並沒有模擬隨機過程，只是用到了一點高中數列知識來遞推（原理和排名第二的答案是一樣的，就不詳述了）

3.「請問具體的代碼可以分享一下嗎？」

實在抱歉。因為搞數學競賽遍地寫ijk的緣故，循環控制變數用的滿地ijk，美觀性不忍直視，所以就不分享了。關心演算法的朋友可以去學習其他的答案分享的代碼，大家的演算法都是幾乎一樣的

4.「沒給方差不幸福」

因為我並沒有模擬隨機，所以方差數據是給不出來的
但是理論推導，應該是越往前方差越小，越往後方差越大（只是大致趨勢，有沒有2號=3號，或是等差數列等規律暫未知）

5.「不理解為什麼活的輪數最多的人反而最後活下來的幾率倒數第二……難道最後活下來的人不是活的輪數最多的嗎？」

因為2號位的方差小啊
你可以理解成：活到最後一個是「變成千萬富翁」，活多少輪就是手裡有多少錢。2號位是辦理財，600號位是買彩票。那麼2號位平均能拿到的錢自然比600號位多，但是他卻幾乎沒有可能變成千萬富翁，相比之下600號位還是有一些機會的。

看了一圈，懂了

2號平均最長命，因為一號不死它就安全，但是一號一死，自己就成了一號，每輪都要抽籤，死的飛快。也就是兩條命，但閃避清零。

600號最可能活到最後，因為它是最後一個，只要前面死人了就會改變奇偶性，在奇數號的時候沒死下一輪就是安全的。也就是帶50%額外閃避

總結：如果這是場必敗的Boos戰，二號就是躲在主T背後的奶媽，600號就是混在人堆里的盜賊。

既然是必敗，那劇情十有八九是這樣的，一分鐘死個人，300分鐘，主T咯屁了，350分鐘，奶媽咯屁了，接著大家各憑本事，最後盜賊隱身瑟瑟發抖。

有理無理先@vczh @曾加 (〃"▽"〃)

先說結論:
一共有n個人時，i號活到最後的概率為:

n為偶數時，
P（i,n）=2i/n^2 （i為偶數）
或 2（i-1）/n^2 （i為奇數）

n為奇數時，
P（i,n）=2i/（n^2-1）（i為偶數）
或 2（i-1）/（n^2-1）（i為奇數）

下面是過程(ノ°ο°)ノ

————————————————————

假設只有2個人，那麼1號活到最後概率為0，2號活到最後概率為1。

假設有3個人，那麼1號概率0，2號概率1/2，3號概率1/2。

假設4個人，1號概率0，2號概率1/4，3號概率1/4，4號概率1/2。

假設5個人，1號概率0，2號概率1/6，3號概率1/6，4號概率1/3，5號概率1/3。

假設6個人，1號概率0，2號概率1/9，3號概率1/9，4號概率2/9，5號概率2/9，6號概率1/3……

根據上述規律，大膽假設:

一共有n個人時，i號活到最後的概率為:

n為偶數時，
P（i,n）=2i/n^2 （i為偶數）①
或 2（i-1）/n^2 （i為奇數）②

n為奇數時，
P（i,n）=2i/（n^2-1）（i為偶數）③
或 2（i-1）/（n^2-1）（i為奇數）④

且n=1，n=2時上述四式成立。

同時，考慮在隊尾增加1個人，人數變成n+1時，各人活到最後的概率為:

n為偶數時，
P（i,n+1）=i/（n+2）×P（i-1,n）+（n-i+2）/（n+2）×P（i,n）（i為偶數）⑤

即 P（第一次先打i號前面的奇數）×P（n個人時i-1號活到最後）+P（第一次先打i號後面的奇數）×P（n個人時i號活到最後），下同

或 P（i,n+1）=（i-1）/（n+2）×P（i-1,n）+（n-i+3）/（n+2）×P（i,n）（i為奇數）⑥

n為奇數時，
P（i,n+1）=i/（n+1）×P（i-1,n）+（n-i+1）/（n+1）×P（i,n）（i為偶數）⑦
或 P（i,n+1）=（i-1）/（n+1）×P（i-1,n）+（n-i+2）/（n+1）×P（i,n）（i為奇數）⑧

下面就是證明原假設了，將①②代入⑤得:
（此時n，i均為偶數）

P（i,n+1）=i/（n+2）×2（i-2）/n^2+（n-i+2）/（n+2）×2i/n^2
=（2i^2-4i+2ni-2i^2+4i）/（（n+2）×n^2）
=2ni/（（n+2）×n^2）
=2i/（n^2+2n）
=2i/（（n+1）^2-1）
與假設中式③相符（n+1為奇數，i為偶數）

……之後再代入⑥⑦⑧，遞推(ノ°ο°)ノ
懶得寫了(*/ω＼*)

由:
n=1，n=2時原假設成立；
當n=m，原假設成立時，n=m+1也能使原假設成立。
可知原假設在n屬於正整數時成立，
即一共有n個人時，i號活到最後的概率為:

n為偶數時，
P（i,n）=2i/n^2 （i為偶數）①
或 2（i-1）/n^2 （i為奇數）②

n為奇數時，
P（i,n）=2i/（n^2-1）（i為偶數）③
或 2（i-1）/（n^2-1）（i為奇數）④

n=600適用於①②
明顯i越大，活到最後的概率越大，且600號概率大於599號。（如果是n=599，那麼598號與599號活到最後的概率同為最大值）

大晚上看到這個題,突然想試一試.作為一個剛念完一學期的統計系大一新生,並不懂概率知識不知道如何用數學推導.最近正在學python,試著寫了個小程序跑了一下,發現和前面答案差不多誒
根據多次試驗,統計存活次數來看,應該是號越大活到最後的概率越高,這就意味著600號最可能活到最後么?
下面是代碼,不知道有沒有錯誤

import random import matplotlib.pyplot as plt


base = range(600)

for i in range(600):

    base[i] = 0

for i in range(100000):

    x = 1200

    c = range(1, 601)

    for i in range(599):

        a = random.randint(1,x/2)

        while a %2 ==0:

            a = random.randint(1,x/2)

        else:

            del(c[a-1])

            x = x-2
    base[c[0]-1] = base[c[0]-1] + 1

plt.figure() plt.plot(base) plt.show()

只跑了10萬次......太慢了

兩個問題答案不一樣，殺死需要次數的期望2最大，最後一個死600最有可能！代碼在後面。
原因也可以理解：2在1沒死之前一直安全，但當1死了2就變得非常危險，隨時可能死，所以殺死需要次數的期望較大，但是不容易活到最後。
任何一個人死，越靠後面越有可能改變奇偶性，從可能死到不可能死，而越靠前面越有可能卡在能死或者卡在不能死上，第一個永遠卡在能死上了，這個微小的影響最後造成越靠後越安全。

無腦寫了一點代碼跑跑看：
殺死需要次數的期望：

正如大家期待的，2號平均死亡時間最短，所以殺死需要次數的期望2最大。最後一個死：

大致線性上升，沒時間跑了，暫且認為600最有可能。

看大家討論的熱火朝天，申明一個自己的觀點吧：

因為這是只有一個人倖存的遊戲，所以我認為安全的定義只有一個，就是活到最後。這也是為什麼我只跑了這一個程序。
試想一個極端情況：即使一個人在一局遊戲里活的時間很長，但他仍然必死，那還叫安全嘛？
或者問下自己，讓你站2號或者600號，你選哪個？

=====更新前內容=====

簡單寫了個程序，執行了測試一百萬次，記錄每次最後存活的人的編號，一百萬次後計數最多的編號即為最安全編號。

class Execution { Random seed = new Random();


        public int[] record = new int[600];

        public int testTimes = 1000000;

public void test() { for (int i = 0; i &< 600; i++) { record[i] = 0; } for (int i = 0; i &< testTimes; i++) { record[processKilling()]++; } } int processKilling() { LinkedList& x = new LinkedList&(); for (int i = 0; i &< 600; i++) { x.AddLast(i); } for (int i = 600; i &> 1; i--) { int decedent = seed.Next((i + 1) / 2) * 2 + 1; LinkedListNode& node = x.First; for (int j = 1; j &< decedent; j++) { node = node.Next; } x.Remove(node); } return x.First.Value; } }

結果如圖：

首先聲明一下，答主剛剛上大一，大學之前沒有接觸過任何信息競賽或書籍，沒聽說過什麼高級演算法，答主只學了一個學期的C++ ，所以姿勢水平比所有其他答主不知道低到哪裡去了，只是覺得這題最近在這個話題下挺火併且很有意思，所以就斗膽今晚花了一點時間用C＋＋寫了一段模擬這個遊戲過程的代碼，並在Dev平台上編譯通過了QAQ。

下面簡單分享一下答主的對應題主對安全的兩個定義的兩個版本的源代碼，寫的十分啰嗦辣雞，但我覺得還是很好懂的吧，比較答主才入C++ 的坑幾個月而已，所以懇請知乎眾大神的批評指教，蟹蟹啦！

版本一：「安全」即為成為最後一個被殺死的概率最大。

這段代碼模擬這個遊戲100000次，結果依次輸出每個人存活下來的次數。

#include& #include& #include&


#define N 600

using namespace std;
int IsOneElement(int a[],int n);

int Find(int a[],int n,int m);
int main()

{

	int show[N+1]={0};

	srand(time(0));
	for(int q=1;q&<100000;q++)
	{
	   int test[N+1];
	   for(int i=1;i&<=N;i++)
	   test[i]=i;				//給每個人編上號 

 	int d=N;
	do
	{	
		int kill=0;
		while(kill%2==0)
		{
		kill=rand()%d+1;
	 	}			//隨機產生當前要殺的人的現有編號 

	int pos=Find(test,N,kill);	//找到所要殺的人在原數組中對應的下標 
	test[pos]=0;				//把那個人給殺了 
	for(int j=pos+1;j&<=N;j++)
	{
	 if(test[j]!=0)
	test[j]-=1;
    }			//把剛剛殺掉的那個人後面所有還倖存的人編號通通前移一位 

	}while(d--,IsOneElement(test,N));
//特別要注意每循環一次d要減一，並且判斷此時是否只剩一位倖存者 


    for(int k=1;k&<=N;k++)
    if(test[k]!=0) { 	
     show[k]++;
    break;
	 }		//統計在實驗了100000次後，每個人倖存下來的次數 

	}

 	for(int i=1;i&<=N;i++)
 	{
	  	cout&<&
只放上550-600的結果，因為我看1-600的結果滿足遞增的趨勢，哈哈哈QAQ。


版本二：「安全」即為殺死需要的次數的期望值最大。
下面這段代碼，從這個角度切入，模擬100000次，結果輸出殺死每個人所需要的平均次數。
#include&

#include&

#include&

#define N 600

using namespace std;
int Find(int a[],int n,int m);

int NobodyLeft(int a[],int n);

int main()

{

	int show[N+1]={0};

	srand(time(0));
	int a[N+1]={0};		//a數組負責存儲每次實驗時每人被殺掉時的次序之和
	for(int q=1;q&<=100000;q++)
	{
	   int test[N+1];
	   for(int i=1;i&<=N;i++)
	   test[i]=i;				//給每個人編上號

	int d=N;
	int counter=0; 
	do
	{	
		int kill=0;
		while(kill%2==0)
		{
		kill=rand()%d+1;
		}			//隨機產生當前要殺的人的現有編號

	int pos=Find(test,N,kill);	//找到所要殺的人在原數組中對應的下標
	test[pos]=0;				//把那個人給殺了

	counter++;
	a[pos]+=counter;	//把此時所殺的人當時被殺的次序計入對應數組中



	for(int j=pos+1;j&<=N;j++)
	{
	 if(test[j]!=0)
	test[j]-=1;
    }		//把剛剛殺掉的那個人後面所有還倖存的人編號通通前移一位

	}while(d--,NobodyLeft(test,N));
                //特別要注意每循環一次d要減一，並且判斷此時是否沒有倖存者


	}


	for(int i=1;i&<=N;i++)
	{
		cout&<&
結果答主忘截圖了，不過我很負責任地講確實此時想要把2號殺掉所需的次數的確最多。

 
為了讓更多人明白這個結果，答主將600人縮減為60人（顯然這個問題答案和究竟總共有多少人無關），然後把兩個程序模擬的次數均提高到一千萬！最後給大家形象地製作了兩張散點圖。直接上圖：
情況一：從存活概率角度分析：


從圖像上我們可以看出，0號必死（這是顯然的），整體上每相鄰的兩個人（2和3；4和5；6和7；ect...）的存活概率相近，且同組中偶數號比奇數號存活概率略低，而每相鄰兩組之間後面的總比前面的存活概率高，即從最終存活概率的角度看，0號顯然必死無疑，2&<≈3&<4&<≈5&<6&<≈7&<,,,&<58&<≈59&<60.所以60號最為安全。
情況二：從殺死某個人所需要次數的數學期望角度分析：


從這張圖像上我們可以看出，殺死奇數號的人所需要的平均次數遞增，而殺死偶數號的人所需要的平均次數遞減，並且都趨於某個相同的值（30到31之間，難道會是它們的黃金分割點？），所以從這角度看，顯然2號最為安全。
所以綜上，如果我們定義最安全是指殺死需要的次數的期望值最大，那麼答案是2號；如果我們定義最安全是指成為最後一個被殺死的概率最大，那麼答案是600號。
所以總的來說，這個題目貌似從編程的角度解決了，顯然答案與高票中大神從數學角度分析得到的答案一致QAQ，（反正答主數競已經退役了，現在又不是數學系的，哈哈哈）還是謝謝 評論區@好心好報的提醒，答主才把從數學期望角度的源代碼碼了出來，本題也確實可以推廣，比如把殺人次數也變成隨機，這個想法很好，答主有時間再把代碼擼出來吧。
答主第一次回答一個私以為比較符合知乎主流專業的學術問題，其實是最最簡單地學術吧QAQ，厚著臉皮求個贊，還有期待大神們的各種批評指教，蟹蟹QAQ！
謝 @成一一 邀...
編號i的傢伙倖存概率為:

也就是越到後面倖存幾率越高.
倒霉的1號必死無疑...
所以如果你是最後一個,那麼存活概率高達

約莫雙色球末等獎的概率,祝你好運...
2號很快就死好不好...1號死了不就2號嗎...3號接下來也死得快...
--------------------------------------------------------


這個數列顯然就是:
Table[Floor[i/2]/Floor[j/2]/Floor[(j+1)/2],{j,2,10},{i,1,j}]//TableForm


模擬驗證:
n=600;

list=Reverse@Rest@Flatten@Array[{#,#},n/2];

foo[x_]:=Block[{die},die=2(RandomInteger[{1,#}]/@list)-1;

Fold[Delete[#1,#2],Range[n],die]];

ans=Flatten[foo/@Range[10000]];

Histogram[ans]



這個題很有意思，數學上的上面都講了，我就寫個程序跑個模擬看看。
算了一下平均多少輪死，以及有多少次是最後一次死。
先上一張圖，10k次測試的結果：


結論與上面的都一樣：
1、越靠後，最後一個死的可能性越大。
2、存活輪數最多的，最可能是第2個人。python太慢，所以只測試了10k次，代碼如下：
#!/usr/bin/env python3

import sys

import random
from matplotlib import pyplot as plt
def kill_one(to_die, dead, n):

    xlen = len(to_die)

    r = random.randint(0, (xlen - 1)//2)

    r *= 2

    dead[to_die[r]] = n

    return [to_die[i] for i in range(xlen) if i != r]
def kill_all(num):

    to_die = [i for i in range(num)]

    dead = [0 for _ in range(num)]

    for i in range(num):

        to_die = kill_one(to_die, dead, i + 1)

    return dead
def main(script, *argv):

    num = int(argv[0])

    sta = [0 for _ in range(num)]

    last = [0 for _ in range(num)]

    K = 100000

    for i in range(K):

        print(i)

        dead = kill_all(num)

        x = dead.index(num)

        last[x] += 1

        sta = [sta[i] + dead[i] for i in range(num)]

    stat = [s / K for s in sta]

    plt.plot(stat)

    plt.plot(last)

    plt.show()
if __name__ == "__main__":

    main(*sys.argv)


另外給個C版的，快多了。
#include &

#include &

#include &

#include &

#define NUM 600

#define K 1000000
void kill_one(int *to_die, int left, int *dead, int n) {

    int r = rand() % ((left - 1 ) / 2 + 1);

    r *= 2;

    dead[to_die[r]] = n;

    for (int i = r; i &< left - 1; ++i) {
        to_die[i] = to_die[i + 1];
    }
}

int to_die[NUM];
int dead[NUM];

void kill_all() {
    for (int i = 0; i &< NUM; ++i) {
        to_die[i] = i;
        dead[i] = 0;
    }
    for (int i = 0; i &< NUM; ++i) {
        kill_one(to_die, NUM - i, dead, i + 1);
    }
}

int64_t count[NUM] = {0};
int last[NUM] = {0};

int main() {
    printf("start...
");
    srand(time(NULL));
    for (int i = 0; i &< K; ++i) {
        if (i % 10000 == 0) {
            printf("test %d...
", i);
        }
        kill_all();
        for (int j = 0; j &< NUM; ++ j) {
            count[j] += dead[j];
            if (dead[j] == NUM) {
                last[j] += 1;
            }
        }
    }
    printf("
result:
");
    for (int i = 0; i &< NUM; ++i) {
        double x = (double)(count[i]) / K;
        printf("%d: %d, %lf
", i, last[i], x);
    }
}

再補充一個一億次的結果圖（大尺度上趨勢看起來更明顯）：

其實上面的回答已經很完整了，但是還是兌現昨天的承諾，把過程寫一遍吧。
這個題其實就是個遞推的過程，第一問我們需要算的是，600個人玩這個遊戲，每個人獲勝的概率，我們分別來計算。
我們用dp[i][j]來表示i個人玩這個遊戲，編號為j的人獲勝的概率。
那麼，考慮單步的過程：要麼選了一個比j小的奇數，要麼選了一個比j大的奇數，要麼選了j(如果j也是奇數的話)。
共有多少種可能性呢？比j小的奇數有[j/2]個，比j大的奇數有[(i+1)/2]-[(j+1)/2]個，如果j是奇數那麼還有一個，一共加起來剛好是[(i+1)/2]種可能性。
現在分情況來討論：
1.選了一個比j小的奇數：那麼狀態會變化為dp[i-1][j-1](總人數-1，j的編號-1)，概率為[j/2]/[(i+1)/2]
2.選了一個比j大的奇數：那麼狀態會變化為dp[i-1][j](總人數-1，j的編號不變)，概率為[(i+1)/2]-[(j+1)/2]/[(i+1)/2]。
3.選了j(如果j是奇數)：顯然此時j已經死了，那麼不考慮。
所以dp[i][j]=dp[i-1][j-1]*[j/2]/[(i+1)/2]+dp[i-1][j]*[(i+1)/2]-[(j+1)/2]/[(i+1)/2]
邊界條件是dp[2][1]=0%，dp[2][2]=100%。(顯然，2個人的時候，編號為1的必死，2必活)。
OK，複雜度O(n^2)，我們花幾分鐘寫個代碼驗證一下，發現和1樓的答主答案完全一致。
期望的求法和概率基本一樣，就不寫了。

以下是原答案：
這不是個dp嗎？dp【i】【j】表示一共i個人，j號生存下來的概率，dp【500】【i】的最大值就是答案啊
先寫個DP式子，期待別人通過遞推公式推出一個直接的計算公式。
dp(m, n) 表示總共m個人，第n個人活到最後的概率：
dp(m, n) = (n|2) / (m|2) * dp(m - 1, n - 1) + (1- (n | 2) / (m | 2)) * dp(m-1, n)
即，共m個人第n個人活到最後的概率等於第一次殺死的是自己前邊的人的概率 * 共m-1個人第n-1活到最後的概率  加上  第一次殺死的是自己後邊的人的概率 * 共m-1個人第n個人活到最後的概率。
0號
對不起我學電子的，我們計數都從0開始
先說結論：最後一個活的可能性最大，另外1號必須死。
import random

N = 10

loop = 400000
def kill(array):

	for i in range(N - 1):

		kill_id = random.randint(0, len(array) - 1)

		while kill_id % 2 != 0:

			kill_id = random.randint(0, len(array) - 1)

		del array[kill_id]

	return array[0]
def main():

	last = {i:0 for i in range(1,N + 1)}

	for i in range(loop):

		number_list = [i for i in range(1,N + 1)]

		last[kill(number_list)] += 1

	for k,v in last.items():

		print(k,v)
if __name__ == "__main__":

	main()


代碼比較粗糙，N表示人數，loop表示循環做多少次實驗。
1號必須死，因為不管怎麼變，1號始終是奇數，1號一死，2號死也就不遠了。所以，2號存活的可能性不大。
當N=2~10，可以看出，從2號開始，(2n)號和(2n+1)號存活次數大致相當，且存活次數隨著n的增加而增加，故存活概率最高的是第600號
你們就是這樣對待奇佬的？
用R寫了代碼， 600個人跑起來較慢（100次需要1秒），改為100人跑30000次
library(data.table)

library(ggplot2)

my_kill &<-function(n,times){
  survive &<&<- 0
  for(j in 1:times){
    kill &<- c(1:n)
    for(i in (n:2)){
      kill&<-kill[-(sample(seq(1, (i+1) %/% 2), 1) * 2 - 1)]
    }
    survive[j] &<&<- kill[1]
  }
  survive &<&<- as.data.table(table(survive))
  survive[, survive:=as.numeric(survive)]
  ggplot(data = survive,aes(x = survive, y = N)) + geom_point()
}
my_kill(100,30000)



我先mark一下這個題目，對於總數足夠大情況，直覺上可以用martingale來做，然而我現在還沒有學到那裡，不好說。等我學完了我再來看一下。

600號最有希望撐到最後一輪，然而他還是會死，唉。
選取一個"存活率" 指標k, 即在N次實驗中ID為i的人的存活次數與所有人的平均存活次數之比. 當然如果N是固定的話平均存活次數就是固定的.
我發現哪怕在計算機上重複實驗50萬次, k都是波動的. 當然不清楚這是否與計算機的隨機數演算法有關係. 所以我設定N為80000, 重複實驗了600次, 把所得到的k整理成如下兩張圖表(數據相同,色譜不同)



這樣看的話,在一定的區間內存活的次數都是顯著變高的, 600和590可能區別並不大.程序的源代碼如下:
//

// Created by Alan on 2017/2/8.

//

#include &

#include &

#include &
#include &

#include &

#include &

#include &

#include &

#include &

#include &

#include &
using namespace std;
using uint = unsigned int;
//global variables

int test_cases = 80000;

short num_people = 600;

vector& *last_ones;

const int num_threads = 4;
int evens = -1;
class Mortuary {

public:

    vector& *people;

    vector&::iterator iter;
    Mortuary() {

        people = new vector&;

        init();

    }
    ~Mortuary() {

        delete people;

    }
    void init() {

        people-&>clear();

        for (short i = 0; i &< num_people; i++) {
            people-&>push_back(i);

        }

    }
    void remove(const int index) {

        if (index &<= people-&>size() / 2) {

            iter = people-&>begin();

            for (size_t i = 0; i &< index; i++) {
                ++iter;
            }
            people-&>erase(iter);

        } else {

            iter = people-&>end();

            --iter;

            for (size_t i = people-&>size() - 1; i &> index; i--) {

                --iter;

            }

            people-&>erase(iter);

        }
    }

};
inline short run_case(Mortuary *mortuary) {

    mortuary-&>init();

    bool subt = (num_people % 2);

    int temp;

    for (int i = evens; i &> 1;) {

        temp = rand() % i;

        mortuary-&>remove(2 * temp);

        if (subt) {

            subt = false;

            --i;

        } else {

            subt = true;

        }

    }

    return mortuary-&>people-&>back();

    //assert(mortuary.people-&>size() == 2);

}
void write_result(int *total, int t = 0) {

    double avg = 0.0;

    int temp = 0;

    for (int i = 0; i &< num_people; i++) {
        temp += total[i];
    }
    avg = (double) temp / (double) num_people;
    stringstream sstr;
    sstr &<&< num_people &<&< "_" &<&< t &<&< ".txt";
    ofstream out(sstr.str(), ios::out);
    for (int i = 0; i &< num_people; i++) {
        out &<&< i + 1 &<&< " " &<&< setiosflags(ios::fixed) &<&< setprecision(8) &<&< (double) total[i] / avg &<&< endl;
    }
    out &<&< "AVG "&<&at(i)]++;

    }

    return freq;

}
int main() {

    last_ones = new vector&;

    last_ones-&>reserve(test_cases);
    time_t *now = new time_t;

    time(now);

    srand(*now % UINT32_MAX);

    clock_t c1, c2;

    c1 = clock();
    if (test_cases % num_threads != 0) {

        cerr &<&< "Invalid thread number." &<&< endl;
        exit(-1);
    }

    Mortuary *objs[4];
    for (int i = 0; i &< 4; i++) {
        objs[i] = new Mortuary();
    }

    for (int t = 0; t &< 600; t++) {

        evens = (int) floor(float(num_people - 1) / 2.0f) + 1;

#pragma omp paralell for num_of_threads(4)
        for (int i = 0; i &< test_cases; i++) {
            short res = run_case(objs[omp_get_thread_num()]);
#pragma omp critical
            {
                last_ones-&>push_back(res);

            }

        }
        cout &<&< last_ones-&>size() &<&< " ";
        //analysis part
        int step = test_cases / num_threads;
        int *total = new int[num_people];
        for (int i = 0; i &< num_people; i++) {
            total[i] = 0;
        }

#pragma omp paralell for num_of_threads(4)
        for (int i = 0; i &< num_threads; i++) {
            int *temp;
            temp = analyse(i * step, (i + 1) * step);
#pragma omp critical
            {
                for (int j = 0; j &< num_people; j++) {
                    total[j] += temp[j];
                }
            }
            delete[] temp;
        }

        write_result(total,t);
        delete[] total;

        cout &<&< num_people &<&< endl;
        last_ones-&>clear();
    }

    c2 = clock();

    cout &<&< "finished in " &<&< float((c2 - c1)) / float(CLOCKS_PER_SEC) &<&< " seconds." &<&< endl;


    system("pause");

}

顯然600號最安全啊~
我沒文化，不太懂數學，當年高數都是補考才過的，那我講一下邏輯吧。
第一次，
不管抽到幾，600號都會從偶數變成奇數。
第二次，
不管抽到幾，600號都會從奇數變成偶數。
這說明，每隔一次，600就會有一次偶數，概率就最低。
越往後的數字，越容易因為抽了前面的而產生奇偶變化，概率就越低。
所以越往後，越安全。
反而數字1，
第一次只要不殺死他，他就還是奇數。
第二次只要不殺死他，他就還是奇數。
一直是奇數才容易被殺死。
所以越往前就越容易死。

最後，沒有真正的安全，反正最後都要死，

還是600個人一起上弄死殺人者吧。
  推薦閱讀：


※三個蛋撻，分別是紫薯的、提子的、黃桃的，有 80% 的把握第一個是紫薯的，有 80% 的把握最後一個是黃桃的，中間的那個是提子的概率是多大？
※怎樣降低被老師點名回答問題的幾率？
※蒙提霍爾問題（又稱三門問題、山羊汽車問題）的正解是什麼？
※一隻股票現價20，上漲或者下降的概率為0.5，每次上漲或者下跌步長為5，求漲到30塊的概率是多少？
※為了防止下雨時沒有帶傘而每天放一把傘在包里值不值得？
TAG:數學 | 趣味數學 | 概率 |