題目描述：

現(xiàn)有100名囚犯，編號(hào)1～100；100個(gè)位于密閉房間中的不透明容器，編號(hào)1~100；以及一百?gòu)埛謩e寫(xiě)有數(shù)字1~100的紙條

現(xiàn)將100張紙條隨機(jī)放入100個(gè)容器中

然后，讓100名囚犯分別進(jìn)入房間中，每名囚犯可以打開(kāi)50個(gè)容器，尋找與自己編號(hào)相同的紙條，開(kāi)完50個(gè)容器后，必須將所有東西放回原位，且不得與其他囚犯有交談。但在這之前，囚犯?jìng)兛梢陨塘繉?duì)策。若所有囚犯都找到了與自己編號(hào)相同的紙條，這這100名囚犯可以全部無(wú)罪釋放，但若有一人沒(méi)找到自己編號(hào)的紙條，則所有人必須繼續(xù)服刑

那么，囚犯?jìng)儜?yīng)該選擇怎么樣的策略，才能使得無(wú)罪釋放就幾率最大？

策略

首先，很容易想到全隨機(jī)選擇，那么對(duì)于單個(gè)囚犯來(lái)說(shuō)，找到自己的紙條的概念均為?，那么100名囚犯都找到自己紙條的概率自然是?

這是個(gè)什么概念呢？

據(jù)估計(jì)，地球上沙粒的數(shù)量在?左右，也就是說(shuō)，使用這個(gè)策略獲勝的可能性，是讓你從地球上隨機(jī)挑出一顆沙粒，挑到指定的那一粒沙粒的概率的不足億分之一，可見(jiàn)這必然不是最佳策略

那么我們應(yīng)該使用怎樣的策略呢？

我們知道：對(duì)任意一個(gè)容器?而言，其中有一張紙條?，不管紙條編號(hào)是否與容器相同，其紙條必定指向箱子，像這樣，容器中有紙條，紙條指向箱子，形成一個(gè)循環(huán)，直到容器中有紙條，此時(shí)循環(huán)結(jié)束

我們稱(chēng)這樣的循環(huán)為“環(huán)”，記作

那么對(duì)于囚犯，其只需要從容器開(kāi)始尋找，對(duì)所在的環(huán)進(jìn)行遍歷后，必定能在容器中找到紙條，考慮到囚犯只能打開(kāi)至多50的容器，則所在的環(huán)的長(zhǎng)度必須小于51，即

那么，這個(gè)策略成功的概念，就是100個(gè)紙條和100個(gè)容器隨機(jī)組合，形成的若干個(gè)環(huán)中，最長(zhǎng)環(huán)的長(zhǎng)度小于等于50的概率

求出概率

在下文中，我們記最長(zhǎng)環(huán)的長(zhǎng)度為

要得到的概率，直接算肯定不好算，因?yàn)殚L(zhǎng)度小于等于50的最長(zhǎng)環(huán)有時(shí)不止一個(gè)

但是，的情況肯定只有一個(gè)最長(zhǎng)環(huán)，我們可以計(jì)算，那么：

考慮

選出n個(gè)數(shù)，不妨令這個(gè)環(huán)的結(jié)構(gòu)如下：

容易知道：

第一個(gè)數(shù)字有n-1種選擇，第二個(gè)數(shù)字有n-2種選擇，以此類(lèi)推，第的數(shù)字有種可能，而第n個(gè)數(shù)字只有一種可能，才能保證成環(huán)

那么這個(gè)環(huán)就有種排法

考慮剩下的容器，用同樣的方法可以算出有有種可能

故長(zhǎng)度為n的環(huán)有

種

所以：

故長(zhǎng)度最長(zhǎng)的環(huán)長(zhǎng)度為n的概率為

這個(gè)式子的值約為0.688

則成功幾率為1-0.688=0.312

可見(jiàn)，使用這種策略可以使成功的幾率大大提高

優(yōu)勢(shì)

更有趣的是，這種策略所帶來(lái)的優(yōu)勢(shì)隨著人數(shù)的上升而增加

則獲勝幾率為：

故成功幾率穩(wěn)定在

而這比的值要大的多

注：

本專(zhuān)欄是基于視頻BV17W4y1S7WR的基礎(chǔ)上撰寫(xiě)，對(duì)部分原視頻講的不清楚的地方進(jìn)行了補(bǔ)充，主要是最長(zhǎng)環(huán)概率處，感興趣的也可以去看這個(gè)視頻

另外，沒(méi)意外這就是我暑假的最后一更了，過(guò)幾天就要去新學(xué)校報(bào)道了，上了高中不能常更新，可能只有長(zhǎng)假才會(huì)更新了，不好意思啦~