100囚犯問題加強(qiáng)版與選擇公理

《100囚犯問題加強(qiáng)版與選擇公理》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、100囚犯問題加強(qiáng)版與選擇公理????在講問題的加強(qiáng)版之前，讓我們先來回憶一下經(jīng)典的100囚犯問題（不是燈泡）。????100個(gè)囚犯從前往后坐成一列。坐在最后面的那個(gè)囚犯能夠看到其余99個(gè)囚犯，坐在最前面的那個(gè)囚犯啥也看不見。看守給每個(gè)囚犯戴上一頂黑色的或者白色的帽子。然后，看守會(huì)從后往前依次叫這些囚犯猜測自己頭頂上的帽子的顏色。如果哪個(gè)囚犯猜對(duì)了，他就自由了。坐在前面的每一個(gè)囚犯都可以聽到后面的囚犯的猜測。如果這100個(gè)囚犯事先可以商量好一種策略，那么最理想的策略是什么？????囚犯們可以亂猜一通，最壞情況下所有人都猜錯(cuò)，平均下來則會(huì)有50個(gè)人猜對(duì)。這個(gè)題有趣的地方就在于，100

2、個(gè)囚犯事先可以商量一種策略，也就是說坐在后面的囚犯可以用他的猜測給坐在前面的囚犯透露一些信息。很顯然，坐在最后面的囚犯是不可能保證自己猜對(duì)的，他猜黑猜白都只有一半的幾率猜對(duì)，似乎沒什么區(qū)別；但囚犯可以事先約定好一種暗號(hào)，即最后一個(gè)囚犯猜黑表示什么意思，猜白表示什么意思。比如，最后一個(gè)囚犯可以猜測和他前面的囚犯的帽子一樣的顏色，這就相當(dāng)于用他的猜測告訴了他前面那個(gè)囚犯該猜什么，于是坐倒數(shù)第二的囚犯可以保證被釋放；此時(shí)，坐在倒數(shù)第三個(gè)位置上的囚犯面對(duì)與剛才坐最后的囚犯相同的處境，他同樣可以用他的猜測提示出他前面那個(gè)人的帽子顏色。這樣下去，可以保證至少50個(gè)人猜對(duì)，平均情況則有75個(gè)人猜

3、對(duì)。這不是最佳的策略。????不可思議的是，最佳策略可以保證，除了坐在最后面的囚犯以外，其余99個(gè)囚犯都能猜對(duì)。你能想出這樣的策略是什么嗎？繼續(xù)看下去前不妨先想一下。????前面那種策略的問題在于，坐在最后面的那個(gè)人透露出的信息不多。他完全可以透露出與全局相關(guān)的一些信息，因此以后所有的人都可以用這條信息。比如，他可以數(shù)一數(shù)他前面99個(gè)人一共有多少頂白帽子，并約定他猜“黑”表示他前面共有偶數(shù)頂白帽，他猜“白”表示他前面共有奇數(shù)頂白帽。坐倒數(shù)第二的那個(gè)人也數(shù)一數(shù)他前面98個(gè)人的白帽子個(gè)數(shù)：如果他數(shù)出來的個(gè)數(shù)與先前透露出的個(gè)數(shù)一奇一偶，則他自己肯定戴的是白帽子；如果他數(shù)出來的和先前透露的

4、結(jié)果奇偶性相同，則他自己戴的肯定是黑帽子。這樣，坐倒數(shù)第二的保證可以猜對(duì)了。那接下來咋辦呢？不要忘了，其他囚犯能聽到剛才那人猜的是什么，并且知道他的猜測保證是對(duì)的。這相當(dāng)于每個(gè)人不僅能看到坐他前面的所有人的帽子顏色，還知道他背后那些人的帽子顏色，結(jié)合最初的那個(gè)奇偶性信息，接下來的每一個(gè)人都可以猜出自己腦袋上的帽子顏色。這樣下去，至少99個(gè)囚犯可以保證被釋放。這種策略顯然是最佳的，不可能再有什么策略能保證所有人都被釋放，因?yàn)橹辽僮詈蟮哪莻€(gè)人不可能保證自己猜對(duì)。????真正有趣的東西來了。下面提出這個(gè)問題的加強(qiáng)版，囚犯的數(shù)目加強(qiáng)到無窮個(gè)！你將看到“無窮”這個(gè)神秘的東西再一次開始作怪。

5、無窮個(gè)囚犯面向數(shù)軸的正方向依次就座，第i個(gè)囚犯坐在數(shù)軸上坐標(biāo)為i的地方，他可以看見所有坐標(biāo)大于i的囚犯頭頂上的帽子?？词亟o每個(gè)囚犯戴上黑色或白色的帽子，然后依次叫每個(gè)囚犯猜測自己頭上的帽子顏色，猜對(duì)了的予以釋放。另外一點(diǎn)和原來不同的是，囚犯們不能聽到其他人的猜測。另外注意到，由于每個(gè)人前面都有無窮多個(gè)人，因此囚犯們無法通過數(shù)他前面的人數(shù)來判斷出自己的位置，于是我們不得不加上一句：每個(gè)人都知道他后面有多少人（即他是第幾個(gè)被問的）。同樣地，事先所有囚犯可以商量出一個(gè)策略。你認(rèn)為這下囚犯們還有什么好辦法沒？????這下囚犯已經(jīng)不能通過自己的猜測來通風(fēng)報(bào)信了，似乎每個(gè)人都只能瞎猜，任何人都

6、無法保證自己能猜對(duì)。你相信嗎，居然有這樣的策略，它可以保證除了有限個(gè)囚犯之外，其他囚犯全部釋放！????考慮所有可能的顏色序列（你可以簡單地想像成01串）。我們說兩個(gè)顏色序列“無窮遠(yuǎn)相等”，如果經(jīng)過了有限多項(xiàng)之后，余下的無窮多項(xiàng)完全相同（即存在某個(gè)數(shù)x，使得兩個(gè)串在各自的第x位后面完全重合）。這種關(guān)系顯然滿足自反性、對(duì)稱性和傳遞性，是一種等價(jià)關(guān)系。因此，按照這種有限位后對(duì)應(yīng)相等的關(guān)系，我們可以把所有可能的顏色序列劃分為一個(gè)個(gè)等價(jià)類。它們的交集為空（兩個(gè)等價(jià)類如果有交集，由傳遞性它們立即并成了一個(gè)更大的等價(jià)類），并集為全集（若某序列不屬于任何等價(jià)類，則它自己就是一個(gè)新的等價(jià)類），是全

7、集的一個(gè)劃分。你能想象出一個(gè)等價(jià)類大致是什么樣子的嗎？假如把同一個(gè)等價(jià)類里的所有序列對(duì)齊并排放在一起，你從前往后走過去的時(shí)候會(huì)發(fā)現(xiàn)這些序列“越來越相像”。你走得越遠(yuǎn)，你會(huì)發(fā)現(xiàn)越來越多的序列開始變得互相重合；當(dāng)你走到無窮遠(yuǎn)時(shí)，所有的序列都變成一個(gè)樣了。????囚犯們事先在每一個(gè)等價(jià)類中選一個(gè)代表元，然后把所有等價(jià)類的代表元背下來。到時(shí)候，每個(gè)人都能夠看到他前面無窮多個(gè)人的帽子顏色，并且知道他自己在整個(gè)序列的位置，于是能立即判斷出他們現(xiàn)在所處的顏色序列在哪個(gè)等價(jià)類里。接下