100個囚犯與100個抽屜的問題？

12-24

有100個囚犯，編號1~100。在一個封閉的房間里放著一排抽屜，總共100個。另外有100張卡片，上面分別寫著1~100。卡片被隨機放入抽屜中，每個抽屜里放一張。
囚犯依次進入房間，每人最多打開50個抽屜。如果打開的抽屜中的卡片號碼與自己的編號一致，那麼這個囚犯就成功了。當且僅當所有的囚犯成功，大家才能被釋放。求策略？

注意：
1.囚犯依次進房間，進房間時以及進房間前後，都不能互相交流。
2.不能做任何記號，不允許把卡片拿出來，哪怕是自己的號碼。

3.打開下一個抽屜前，必須把之前的抽屜關上，即不能用抽屜的開關傳遞信息，也就是說，每個囚犯進房間的時候，房間的布置是一模一樣的。

先上結論：犯人們被釋放的概率可以超過30%。

如果你沒有意識到這個結論有多麼驚人的話，我們先來做一個計算：

如果每個人隨機選擇，那麼他找到自己號碼的概率是50%；所以，所有人都找到自己號碼的概率將是1/2的100次方。這個值約等於：

0.0000000000000000000000000000008

而採取一定的策略，我們可以使釋放的概率超過0.3！【停頓兩秒，此處應有掌聲】

首先我們把這一行抽屜按順序從1到100依次編上號。

策略如下：

1.每個人首先打開與自己的編號一樣的抽屜。例如：1號犯人進房間之後首先打開1號抽屜。

2.如果抽屜里就是他的編號，那麼瀟洒離場。例如：1號犯人發現1號抽屜里就是1號卡片，瀟洒離場。

3.否則，他接下來打開與該抽屜里的號碼一樣的抽屜。例如：1號犯人發現1號抽屜里放著72號卡片，那麼他接下來打開72號抽屜。

4.重複第二、第三步，直到找到自己的號碼後瀟洒離場，或者打開50個抽屜也沒找到後黯然神傷。

就是這麼簡單。

方便起見，我們用「總共8個抽屜、每人4次嘗試」作為例子：

假設排列如下：

於是：

1號犯人首先打開1號抽屜，發現裡邊放著7號卡片；接著打開7號抽屜，發現裡邊放著5號卡片；接著打開5號抽屜，發現裡邊放著1號卡片，瀟洒離場。

2號犯人首先打開2號抽屜，接著依次打開4號、8號抽屜，然後瀟洒離場。

3號犯人依次打開3號、6號抽屜，然後瀟洒離場。

4號犯人依次打開4號、8號、2號抽屜，然後瀟洒離場。

5~8號犯人同理。

所有犯人都被釋放啦！

但並非每次都這麼走運，假設排列如下：

1號犯人依次打開1號、3號、7號、4號……心灰意冷，黯然神傷。

2號犯人依次打開2號、1號、3號、7號……心灰意冷，黯然神傷。

最後，除了6號犯人瀟洒離場以外，所有犯人都黯然神傷。

時而成功，時而失敗，到底什麼是影響成敗的因素呢？不急不急，讓我慢慢說。

事實上，我們可以用「置換群」來表示卡片的擺放。

讓我們先來看那個成功的例子：

1號抽屜放著7號卡片，7號抽屜放著5號卡片，5號抽屜放著1號卡片；

2號抽屜放著4號卡片，4號抽屜放著8號卡片，8號抽屜放著2號卡片；

3號抽屜放著6號卡片，6號抽屜放著3號卡片。

發現了嗎？這個排列形成了3個「環」。

這個擺放可以用循環置換記法記為(1 7 5)(2 4 8)(3 6)。如下圖：

同理，那個失敗例子的擺放可以記為(1 3 7 4 5 8 2)(6)。如下圖：

不管卡片怎麼擺放，我們都可以表示成「環」的形式，因為每個抽屜只能從一個卡片指來，而這個抽屜里的卡片又只能指向一個抽屜，且抽屜的個數是有限的。

其中最小的「環」的長度就是1，最大的「環」的長度則等於抽屜總數。

當每個人首先選擇了自己編號的抽屜之後，沿著「環」的路徑打開抽屜，最後一個未打開過抽屜里的卡片號碼將會是一開始選擇的抽屜的編號，也就是自己的編號——因為這是個「環」嘛。

所以，回到原題，只要卡片的擺放沒有形成長度超過50的「環」，那麼所有人都可以找到自己的號碼。

那麼概率怎麼算呢？

首先，最多只可能有一個長度超過50的「環」，將其長度記為L。於是，總共有C(100, L)種構成該「環」的組合，每一種組合有(L-1)!種排列（注意不是L!，因為這是「環」）。這個「環」之外的卡片有(100-L)!種排列，所以對於每一個L來說，都有C(100, L)·(L-1)!·(100-L)!=100!/L種情況。而100張卡片的總排列數是100!，所以最終所有人都猜對的可能性就是：

≈ 0.31183

我們把這個值與0.0000000000000000000000000000008比較一下，是不是天壤之別？

最後，以TBBT里的一句話來結束這個回答：

參考資料/想了解更多可點擊：100 prisoners problem

匡世珉的答案已經非常詳盡了，這裡給一個簡單易懂的 version: https://www.youtube.com/watch?v=C5-I0bAuEUE

額...今天hackerrank做題遇到了...

概率是0.31182782069

首先囚徒被釋放的概率是（1/2）^100；

其次，我們可以用適當策略來提高這個概率。由於100個盒子里的卡片是隨機放置的，我們可以採用熱力學熵原理分析:
【用來表示任何一種能量在空間中分布的混亂程度，能量分布得越混亂，熵就越大。】卡片的隨機放置，100張卡片所處體系的混亂度是很大的（如果卡片按照1～100順序放置，可認為混亂度為0，由於隨機放置，混亂度為0概率為1/100！≈0）

按照這個規律，我們是不是可以讓囚徒抽卡片的順序變混亂，然後囚徒抽那張卡片也變隨機呢？

和高票回答的方法一樣，最大滿足囚徒抽卡片的組合不同，其中囚徒抽取卡片不同組合有C50/100種遠大於囚徒人數100，即:隨機選擇囚徒，每個囚徒隨機抽取50張卡片。
（這是我自己思考的一種策略，還有很多錯誤和不足，歡迎大家討論）

我呆在監獄裡還不行嗎！

怎麼知道大家都出來了呢和以前那種有個人判斷誰都出來過不太一樣