關於紅眼睛藍眼睛自殺問題，陶哲軒教授又問：旅者如何挽回自己說的話？

12-29

一個關於數學歸納法的悖論問題：到底是第N天有N個紅眼睛自殺，還是什麼都不會發生？，查找了此帖的根源，陶哲軒教授的問題邏輯設定顯然非常嚴密，在回答中出現的疑問其實都有說明。不過我更有興趣的是教授的展開問題。

首先是教授原題的翻譯：網上查找資料最早出現於2008年教授的博客（多年前的問題最近引起大討論~~lol）原題其實是棕色眼睛和藍色眼睛，在此遵照前問題改為紅藍眼睛。

從前有一個島，島上有1000民居民，100位是紅色眼睛，900位是藍色眼睛。
他們的宗教禁止他們從別處得出他們眼睛顏色的信息，或者討論這個話題。因此，每一位島民都知道其他島民的眼睛顏色，確沒辦法得知自己的（島上無鏡面反光物體）。
萬一島民通過自己的思索，確認了自己眼睛的顏色，他（她）就會在第二天正午，當著全村人的面自殺。
島民都擁有非常的邏輯思維能力，非常的虔誠於他們的宗教，並且他們互相知道大家都是這樣（高度邏輯，高度虔誠），也都知道大家都知道大家都是這樣（高度邏輯，高度虔誠）。

有一天，一位擁有紅色眼睛的旅行者來到了小島，並且贏得了島民們的完全信任。一個晚上，他邀請全島民感謝他們的款待，在不知道島民的信仰傳統下，他無意的感嘆道：「能在世界的這個小角落碰上和我一樣擁有紅色眼睛的人，是多麼的不尋常呀！」

額外說明：島民並不知道島上居民的眼睛顏色確切數據（因為他們都只能看見999位島民）;高度邏輯的意思是：在一名島民已知的信息和觀察結果下，任何可以邏輯性推導出的結論，這民島民都會自動得知。

陶哲軒教授直接給出了兩種回答：

旅者的話沒有任何效果，因為他的話並沒有給島民帶來任何新的信息（島上居民都知道他們之間有紅色眼睛的人）。

在旅者說完這句話100天後，所有的紅色眼睛島民都自殺了，即可以推論歸納為：島上有n位紅色眼睛者，他們會在旅者發表那句話後第n天全部自殺。並且在第101天，剩下的900民島民也知道自己的眼睛顏色，並在第101天正午全部自殺了。。。（旅者把這個島變成了無人島...）

證明過程：假設命題成立，
若n=1，唯一的紅眼睛島民會發現旅者指的就是他，因此在第二天就自殺了。
若n&>1，每位紅色眼睛的島民都會想「如果我不是紅色眼睛者，那麼在第n-1天，就會有（我觀察到的）這n-1位紅色眼睛的島民自殺」。但到了第n-1天，這些紅色眼睛的島民並沒有自殺（因為此時他們都沒有足夠的證據證明自己是紅色眼睛）。於是第n天，這些紅色眼睛的島民意識到了自己是紅色眼睛者，他們都在這天正午自殺了。

陶哲軒問：哪個結論成立呢？博客上並沒有給出他的解答，但是他給出了提示，他說：「解決這個看起來完全矛盾的兩種結論的關鍵在於理解"公共知識(common knowledge"的意思」。看來陶教授是贊成張石敧的回答的~

好了，展開問題來了：
1. 旅者在講話的第二天，意識到了他犯了一個大錯（引發大規模自殺），那麼他是否有方法減少人員傷亡。
2. 如果旅者在他講話的若干天后才意識到他的錯誤呢？

原博文似乎也有陶自己的解答，容我慢慢爬文翻譯...知友可以先嘗試解答啊~~~
博客地址：http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/

謝邀。

應該有個前提是旅行者不能說出前後矛盾的話，不然的話，旅者只要說他撒了謊就好了。

只是為了減少人員傷亡的話，簡單的辦法是，如果在第二天正午前意識到錯誤，殺掉一個紅眼睛的人，如果是正午後，殺掉兩個。如果是若干天后才意識到，就要想辦法殺掉若干個人了。。。

告訴島上的人，你們這裡有紅眼睛，藍眼睛，綠眼睛，黑眼睛這四種顏色其中的三種，島上的人沒有理由判斷他說的是假話，那麼每人看到都是倆種顏色，而自己也不能判斷出自己是什麼顏色，就ok了。

~~~~~~~~~~~

我覺得島上的人早已知曉了一切。

他們都知道在這個島上有紅眼人，但為什麼，有個人說出來一個事實，他們就會死光光呢？
他們之所以不談論眼睛顏色，就是因為，一談論就死。
因為談論的那一個瞬間，給了他們一個開始數數起點。

比如有10個紅眼，有個這個起點之後，他們十個都知道知道第9天沒人死，那麼第10天就是他們的死期，因為他們眼中只有9個紅眼。

但中假如中間有人被殺，只要被殺的人數和度過的天數，不相等，就會打亂了他們數數的起點，因為他們不能確保，其他紅眼是以最開始的起點數，還是以有人被殺後的起點數，這時邏輯開始分流，不能導致唯一的結果。

但這個過程中必須有人死。。。

但這個邏輯的進行，必須在一個條件下進行，那就是這個島上只有紅和藍倆種，如果有第三種不確定的顏色出現，就會打破這種條件，從而邏輯沒辦法進行。

按照我最上面的答案，
島上的人會說:喂，哪有四種，你特么是在逗我們。
我會心裡默默的說，我特么是在救你們。

雖然答案有些缺陷，但並不影響他的可信度。

最重要的是，這樣就沒人死了。。。

我讓他們活在了謊言下，可是在生活中的我們又何嘗不是呢。

--------------update:2013.9.5----------
不用死人的方案。
提供方案前，先反對說自己色盲而紅藍對調的那個答案。
如果把太陽說成藍色，則之前第一個信息提供的有紅眼睛對於島上居民來說就是有藍眼睛。自殺推斷只是從藍色眼睛開始發生罷了，並不能阻止殺戮。

不死人方案：
假設島上有N個紅眼睛。
在第K（因為題目從第二天開始，所以K&>=1且K+1&

問題的思考：
時隔半個月，剛好靈機一動想到了一個方案，可以令島上紅藍眼睛都不用死。同樣和原始方案一樣，希望得到知友的指錯。

原來的方案（死K+1個人）的出發點是：

由於自殺推斷是基於「公共知識」，那麼其中一個減少殺害的方式是把知識給破滅。

但原來把知識破滅的出發點是真正意義上把知識破滅（企圖把信息清空）。但其實可以提供一個額外信息使人無法再確定所有人都知道自己知道的信息——知識一樣破滅了。

以達到的效果是：原來的推理過程，它本來是一個公共知識，只要讓其不再是，則推理阻斷。

以下基於新思路提供方案的分析過程。
分析：
由於經過第K天（K&>=1）後，所有人都會知道當前紅眼睛的人數R&>=K+1個。（如K=0時，由於旅客提供的公共常識，全部人都知道有紅眼睛（R&>=0+1=1）。而第1天（K=1）後，即第二天，由於看到沒人自殺則可以推斷紅眼睛數R&>=1+1=2個。）
那麼，假如這個時候旅客說：「你們這裡只有K+1個紅眼睛的說，又會如何？」
有兩種情況：
1.每個人都能證明旅客這次說的是假話。
2.旅客說的這信息本身就是公共知識。

第一種情況的條件是：紅眼睛數量&>=K+3個，即所有人都能確定島上至少有K+2個紅眼睛了，而且如果紅眼睛數量&>=K+4，甚至所有都能確定所有人都知道島上至少有K+2個紅眼睛，即都知道旅客說的是假話。即知道旅客說的是假話這是一個「共有知識」（Mutual knowledge）。但是否是一個「公共知識」（Common knowledge）呢？

簡化例子：假如島上只有5個紅眼睛，在第二天（K=1）時，旅客說島上只有2個紅眼睛。假設四個紅眼睛A、B、C、D、E。以下以A的視角分析（牢記這點）。

A、B、C、D、E，一眼就知道島上除了自己有4個紅眼。並且A都知道其他人知道。因為除了A和其他
兩外一個人，都至少能看到3個紅眼。但是，A卻不能保證B知道C知道。更進一步，A不能保證B知道C知道D知道旅客這次說的是假話。具體分析可看我這裡的回答一個關於數學歸納法的悖論問題：到底是第N天有N個紅眼睛自殺，還是什麼都不會發生？

也就是說，所有人都不能保證所有人知道所有人和自己的有一樣的想法。——公告知識破滅。

上面的簡化例子中，在第三天（K=2）時候，A知道旅客說的是假話，本可以推斷保證島上至少有3個紅眼是公告知識。但卻難保A知道B知道C知道旅客的謊言。即，這一推斷，本來的公告知識，也順理破滅了。 推理阻斷！

而第二種情況則更為簡單。如第5天（K=4），島上的紅眼數推斷：&>=5個。旅客告訴島上有5個紅眼，5個紅眼一看，除了自己還有4個，那自己就是那個紅眼了——集體自殺。

也就是說要挽救這次殺戮，就不能讓第二種情況出現，所以說這個信息的時機應該是在島上集體自殺前一天之前。

最終分析結論應該是：在第K天（題目自帶K&>=1）之後（即第K+1天），告訴全島居民，「你們島上只有K+1個紅眼睛」。其中 K+1&

若邏輯有錯請指出。歡迎一同探討。

==================================================================
原來的方案不刪除，以便標記自己思考的過程。
----------------以下為原始方案-------------
暫時想到最好的是死2人的方案，不知邏輯是否有誤。

由於自殺推斷是基於「公共知識」，那麼其中一個減少殺害的方式是把知識給破滅。
由於經過第K天（K&>=1）後，所有人都會知道當前紅眼睛的人數&>=K+1個（第一天，由於旅客提供的公共常識，全部人都知道紅眼睛數&>=1個（有紅眼睛）。而第K=1天後（第二天），由於看到沒人自殺則可以推斷紅眼睛數&>=1+1=2個。），要破常識，可把這個數量的人數讓其死亡。
可以的方案是，當眾（如果私下的話，暫時沒考慮清楚會不會影響邏輯）在第K+1天，對其中K+1個紅眼睛說：「你們是紅眼睛的」，那麼第二天那K+1個紅眼睛會集體自殺（假設本題中的旅客說的話具有可信性，不然的話就當眾直接殺掉也行）。那之後，則公告知識便消失了——那時候公共知識剩下中紅眼睛數應該是&>=k+1-(k+1)=0個。即對於剩下的群體來說，回到了旅客沒有提供信息的地方。

因為不能保證循環的過程中每個人都都確信每個人知道還存在紅眼睛（有可能那個旅客第一次說的紅眼睛就是剛剛死的那個）。紅眼睛們不能因此推斷而集體自殺了。
按照這個推理，最少的死亡人數是K=1的時候，即死亡人數為2。

PS:個人覺得應該擁有方式提供更多的信息以迷惑推理過程。如提供紅眼睛的數量範圍或者藍眼睛相關情報以阻斷N=1或某個初始值情況下的證明？

PPS:個人認為本題回答中提供的很多「謊言」並不能解除殘局。假設居民能夠依靠自身觀察和推理知道旅客第二句話是不真實的話，居民有理由推理出旅客的用意。所以如果要提供「謊言」也是應該不能通過觀察或推理而證偽的謊言。

思考了一下，想了兩個方案，很不嚴謹，僅為拋磚引玉

方案一，旅者推翻自己的話

首先假設旅者可以推翻自己，例如在第二天向全體島民宣布：經過觀察，島上所有人的眼睛都是紅色。對島民來說這與事實不符，那麼要麼旅者說謊，要麼旅者沒有紅藍辨別能力。旅者第一天的話也就失去了可信度。

採用這一方案，確實可以阻止所有自殺的島民，但是，有很強的限制條件：旅者必須在第一次集會前（即第二天正午前）推翻自己的話，否則，此方案沒有任何作用

為了簡化分析，假設島上只有3個紅眼睛，A，B，C。旅者在第一次集會後立即推翻了自己的話。但是已經來不及了，因為在A看來，如果島上僅有BC兩個紅眼。由於第一次集會無人自殺，這兩人必然已經知道自己是紅眼。那麼他們應該在第二次集會上自殺。如果他們沒有這麼做，只能是因為島上還有第三個人，就是A自己。BC兩人推理過程完全相同，於是三人在第三次集會上自殺

請注意，以上推理過程，與旅者未推翻自己的話時完全相同。這是由於後面的所有推理皆是建立在第一次集會的結果上，只要旅者的話在此之前未被推翻，那麼第一次集會的結果就足以提供足夠的信息，後面的推理無可避免

方案二，旅者殺掉紅眼睛

這一點比較好理解，旅者只要在第n次集會前，殺掉n個紅眼睛，就可以中斷剩餘紅眼睛的推理過程。最人道的方法是，在第二次集會前殺掉2人（第一次集會前可以只殺1人，但是此時可以使用方案一，不殺人，所以非優選）

在這個方案中，旅者完全可以不用親自殺人，只需在第n次集會前，親口告訴n個紅眼睛：「你們是紅眼睛」，由於題設中旅者受到高度信任，所以這些人會在第二天的集會上自己了結。當然，這還是變相殺人了，只不過好操作一點。

想了很久，也沒有想到在第一次集會後不死人的拯救方案，還求大神出來救人啊

設有s&>1個紅眼睛。取非負整數a小於b小於s.
在第a天（a為零即當天）告訴他們，你們中至少有b個紅眼睛。

這樣，旅客沒說謊，也不用死人。

如果晚了，到了s-1天，不撒謊等等破壞規則的方法似乎不好找了。

兩種辦法
1 證明自己的話沒有可信性即讓島上的人認為我說的都是假的，那麼旅客的話就不會成為知識。
2指明部分人(大於1小於紅眼人數)說他們是紅眼，當天他們會自殺，其他人恢復至初始的穩定狀態。
當然為了較少的傷亡，指一個人就夠了。

我給你講一個更恐怖的故事

從前，有一座美麗的小島。

小島上面住著100個藍眼睛的人。

有一天，島上來了一個黑眼睛的外鄉人。

他/她說：「島上有紅眼睛。」

咦，你們這裡怎麼把太陽叫成紅色的？明明是藍的啊！

哦不好意思我色盲......

第一天：「咦，發現有人的眼睛顏色會變。」

或者：「我發現有應該自殺的人沒有自殺。」

反駁Jaskey Lam的回答

這裡舉兩個例子好了：

{例子一}4個紅眼者ABCD，旅行者在2天後，也就是第3天時向大家宣告只有3個紅眼者。此時的所有藍眼者會覺得那個旅行者是傻逼，因為他們都看見了那4個紅眼者ABCD。但是A會因此推理出自己一定是藍眼者（因為他對旅行者「完全信任」），所以第二天就會去自殺，同理BCD也會去自殺。ABCD自殺之後的第二天所有人也都自殺去了，因為ABCD自殺了是因為相信了旅行者第二次所說的話，而這是基於ABCD每個人只看見3個紅眼者的基礎上，因此所有的藍眼者就可以推理出自己的眼色。

{例子二}4個紅眼者ABCD，但是這次是一天後，也就是第二天旅行者向大家宣告只有2個紅眼者。這一次不光是所有的藍眼者，還包括那4個紅眼者ABCD都會認為那個旅行者是傻逼，因為他們都看見4個或3個紅眼者。但是，A不知道B，C，D是不是知道那個旅行者是傻逼，以下用A的視角來分析：
如果老子是紅眼，那麼BCD都會覺得那個旅行者是大傻逼，所以他們明天就不會自殺；如果老子是藍眼，那麼BCD都會推理出自己一定是藍眼者（因為他們都會對那個傻逼「完全信任」），然後他們明天就會自殺。
結果ABCD都這麼想，結果明天誰都沒自殺，然後ABCD都因此推理出自己的眼色，後天就會去自殺。

自己曾在這裡犯了個錯誤，被Flysong一針見血的指了出來：「K小於N-1取什麼值都沒用的，所有人都能或對或錯的推斷出來自己的顏色。如果有N等於K+2，類似你第一個例子，紅色都會錯誤的判斷自己是藍色，在第N-1等於K+1天集體自殺，藍色於是在第N天自殺。如果N等於K+3，類似你第二個例子的推理，紅色在第N-1天自殺不再是錯誤判斷，而是正確判斷自己是紅色。這是歸納法的初始，之後用歸納法就得到了，對任意N大於K+3成立。因此在K天后說有K+1個紅眼睛，加速死亡一天。」

所以我對這題的答案是：旅行者控制島民們以使得他們自殺的情況（是否自殺）對於其他島民來說是個未知數，因為題干有說島民們自殺時會當著全村人的面。
如果旅行者做不到這一點的話，就在說漏嘴了之後當著全體人員的面立即殺掉一個紅眼人。這樣可使傷亡人數最小化。

作死版本1：你們猜我之前說的是真的還是假的
作死版本2：我從來不說真話
總之毀掉邏輯推理的根基

你們當中有一個人，昨天晚上眼睛發生了變化。

有一種細思極恐的情況，假如只有一個人是紅眼睛，可是這個人他嗎的智商不夠，第一天他沒有自殺，結果第二天晚上除了他所有人都自殺了..第三天他就懵逼了……

補充的話不能推翻前面的話，且不能被證偽。破壞他們的推理模式即可。
「紅色眼睛的人視力有問題，會將部分紅色眼睛看成藍色眼睛。」

答案是第一種結論，沒有任何影響，但是這是個無人島。
反駁第2種結論的觀點如下：第2種觀點的證明是從第一天開始的，但是這個假設是不成立的，因為任何一個居民都知道至少有99個紅眼睛，這個居民還知道除他之外的其他居民也至少看到了98個紅眼睛，所以他知道島上一定有98個紅眼睛，並且每一個居民也知道。所以起點應該是98開始，而不是1，也就是說，第一天的時候只看到97個紅眼鏡的都會自殺。但是第一天沒有人會自殺，因為每一個人都看到了至少99個紅眼睛，到了第二天,只看到98個紅眼睛的都會自殺，依舊沒有人自殺，到了第3天，看到99個紅眼睛的都自殺了,每一個紅眼睛的人都自殺了，第4天藍眼睛的人也會自殺。
所以和外來者根本沒有關係，這個島嶼在出現的第4天就會成為無人島。

無法阻止，所有人最後都會死。

商人並沒有給島上居民帶來新的信息，他只是統一了所有人統計眼睛顏色的時間。也就是「死亡倒計時」！（借用一下概念）

每天所有紅眼睛都會去統計紅眼睛數量得到數字N（紅眼睛人數為N+1），然後在第N天，如果沒有N個紅眼睛一起自殺，第二天所有紅眼睛一起自殺，然後藍眼睛發現沒有紅眼睛了，然後一起自殺。

如果有人在這個過程中死亡，那麼問題重置。

問題的根本在於所有人都會在同一天開始計數，這就是公共知識的基礎。這個命題題不變，那麼循環一定會繼續，直到所有人死亡。

想要破壞這個命題，就需要破壞統一時間這個概念，不論怎麼做，怎麼分組，所有組內成員都會在同一時間開始計數。

旅行者進入一私密房間，島民排隊按次序進入和退出，以保證同一時間只有一個島民能聽到旅行者說話。對於每個紅眼睛島民，旅行者告訴他島上紅眼睛島民總數是（真實紅眼睛島民總數-1）；對於藍眼睛島民，則說今天天氣真好。

這是通過信息不對稱來平衡之前泄漏的公共信息的辦法，因為每個島民都不知道其他人從旅行者那裡獲得了什麼信息。

掏出槍，說:你們TM都給老子改信伊斯蘭教！

改口說你們這裡至少有50人是紅眼睛的。然後所有人下意識在心裡數了一下，超過了50個，然後低頭想想罵了句：媽的智障，盡說些廢話！

旅者殺掉一個藍眼睛呢？殺掉了丟失荒野不讓別人看到他的眼睛顏色。

然後紅眼睛看到只有899個藍眼睛99個紅眼睛就會想「我是藍還是紅？失蹤的那個是什麼眼睛？我不知道？所以我不會去自殺。」

然後不會有人去自殺？

這個答案不知道可行不？