『一道很難的智力題』解法

題目鏈接：一道很難的智力題 - ⑥的完美算數教室 - 知乎專欄

首先很抱歉把這道智力題寫成了專欄而不是問題（本意只是想分享有趣的智力題），導致大家回答起來比較吃力，沒想到有這麼多人感興趣

其次，除了我這個解法外，還有來自Vichare Wang的解法。我感覺他的答案是對的，而且操作起來比我的做法簡單許多。另外，還有來自wheeler的解法，我還沒來得及仔細看。

最後，本解法來自StackExchange上Gil Goldshlager的解法。我試圖把原解法寫得盡量降低讀者的思維深度需要（因此答案會顯得非常冗長，但我希望易懂）。但無論如何，credit都歸原作者。

=======================

前言

在開始之前，請大家先注意一個很重要的結論：所有人排成了一個圓，那麼在任何時候，當天發出1的那部分人和收到1的那部分人都不可能完全相同。否則，這些人自己就形成了一個閉環。唯一的例外是：發出者已經是全集（或者空集）。換句話說，對於某個非空真子集來說，他們一定有辦法對外『滲透』，同時也一定可以『吸收』來自外部的新信息，獄長無法阻止。

這個結論在本解法中經常用到。下文中我會用來提醒大家回想這個結論。

=======================

序章：打造一個工具

我們先來定義一個子過程，其中是一個人員集合，是某個正整數。並且假定所有人都明白自己是否在里，且所有人都知道的值是多少。

的目標是試圖讓1『感染』所有人，它包含兩步：

第一步耗時天。在這天里，所有在里的人，以及在這一步內收到過1的人，都持續發1直到這一步結束。其他人發0。

這有什麼用呢？顯然是從這個『傳染源』開始，試圖讓1感染盡量多的人。多少人呢？如果每次收到1的人都是『新』的（還沒被感染的），那麼『患者』每輪都加倍，最多感染個人。但如果收到1的人有很多『舊』的怎麼辦？根據，每次收到1的人至少會有1個是『新』的。這也就意味著第一步至少感染了個人，除非總人數沒有那麼多——那就已經感染了所有人。

所以我們可以這麼說：第一步結束後，要麼所有人都被感染了（成功），要麼只有一部分人被感染（失敗），這部分人不超過個。

現在問題就來了：第一步結束後，如果某人仍未被感染，那他清楚地知道本次『失敗』了。但是反過來，如果他被感染，他還沒法肯定這次實驗就是『成功』的——因為他不知道是否有其他人沒被感染。換句話說，此時還未達成一個關於『這次是成功了還是失敗了』的全局『共識』，這怎麼辦？再次利用，我們可以反過來去嘗試『清除』這些人的感染，一天至少清除一個（除非前面已經『成功』）。既然上面說了第一步最多感染個，那麼：

第二步耗時天。在這些日子裡，所有尚未被感染（即第一步最後一天收到的還是0），以及在這一步內收到過0的人，都持續發0直到這一步結束。其它的人發1。

經過這兩步之後，要麼所有人都是1（成功），要麼所有人都是0（失敗）。這意味著達成了共識——每個人都知道本次是成功了還是失敗了！

要注意的是，為了保證每個人都知道第二步一共要執行多少天，要麼每個人都必須知道的值，要麼某個『總人數的上界』已經成為共識——這時，這個『清除感染』的過程只要執行天就足夠了。

以上，子過程定義完畢。

=========================

第一章：找出人數上界

出山的第一戰，就是用來找出這個『總人數的上界』：

我們以給大家群發郵件的『你』作為傳染源，從開始調用你。若失敗，則把增加再重試，如此反覆。由於每輪感染的人數下限不斷增加，所以一定有成功的那一天。而一旦在成功，我們就知道總人數不超過個人，人數上界找到並成為共識。

然而為什麼要找上界呢？在的最後曾提到過，使用的前提需要知道或二者之一。現在我們找到了，從此就解鎖了一項技能——可以對任何大小未知的集合進行操作。這讓我們發現了的另一種用途：

對於任意（可以是空集的）集合，調用。只要不是空集，由於第一步至少感染了個人，必然成功。這樣大家就可以根據成功與否，來判斷是不是空集。換句話說，除了幫我們找到上界之外，我們同時有了一個新工具：，並且它仍然保持著『全局共識』這樣一個優良傳統。

=========================

第二章：拆！

接下來，我先給出解決問題的方向，以及具體執行方案。在下一章里再給出分析，來解釋這個執行方案為什麼能夠解決問題。

方向：我們試圖把所有人拆分成若干個不相交的集合，並在這個過程中找到關於這些集合之間的一系列關係。更具體地說，如果把每個集合的大小看做未知數，我們試圖建立若干個關於這些之間的方程，並且證明這個方程組有唯一解的。

執行方案：

起始時，我們把所有人劃分成個集合：你，其他人。

現在假設場上存在個集合，那麼我們定義如下操作為『一輪』：

1. （外循環）按照某種事先約定好的順序來遍歷的所有非空真子集，也就是說每個子集都包含著若干個。在這個循環里，記『當前子集』包含的所有的下標為下標集合：

1.1. 花一天時間，讓所代表的那些集合里的每個人都發1，其他人發0。這樣會有一些人收到了1，記這些人構成集合。

1.2. （內循環）對於每個，再按的順序遍歷每個集合：

1.2.2. 執行，也就是判斷里有沒有人在1.1步中收到了1。

1.2.3. 執行，也就是判斷里有沒有人1.1步中收到了0。

1.2.4. 若以上兩個集合都不為空，說明里既有人收到1也有人收到0。那麼把原來的分裂為兩個新的集合。不妨把『收到1』的那部分人繼續沿用，而『收到0』的那撥人則新開設一個集合，同時把集合總數加一。反之，若以上兩個集合里有一個為空，那麼就保持原樣。

1.2.5. 若1.2.4步中成功分裂了一個集合，那麼這『一輪』就立即結束，並且重新開始一個新的『一輪』。反之，若這輪中的所有循環都未能成功分裂某個集合，就不再重複進行新的『一輪』了。

不難想像，每一輪都會分裂一個集合，但集合總數不可能超過全場人數，所以總有停止的一天。

現在我要證明的是，根據最後一輪（即沒有任何集合分裂）里發生的一切，場上的每個人都有能力計算出所有現存集合的大小，從而得到總人數！

=========================

最終章：為什麼會這樣呢

讓我們來看看『最後一輪』里都發生了什麼：

每一個外循環對應著一個。所代表的那些集合里的每個人都發了1，這些1被收到了。由於本輪沒有集合被分裂，這意味著可以視為若干個的並集——因為任何一個集合，要麼里的所有人都收到了1，要麼都沒收到1，（否則就該分裂）。不妨記這些『收到1』的集合的編號構成了編號集合。我們可以簡單地概括成『發出信號，被收了』。

注意，由於遍歷的所有非空真子集的順序是事先約好的，所以每個人都知道代表哪些集合。同時，由於所有人都知道的結果，也就是說大家都知道里有哪些集合（的下標）。

現在我們知道和的內容都是共識。另外，我們還知道每天發出1的人數總是等於收到1的人數。這意味著我們得到一個這樣的方程：

用人話說，就是『A代表的集合的人數總和與Z代表的集合的人數總和相同』。另外，由於來自於的所有非空真子集，所以不會是全集，根據，總是成立的。

類似這樣的方程有多少個呢？它等於的所有非空真子集的個數，也就是個。有了這個元線性方程組，我們就能用高斯消元法來解出每一個。但在這之前，還需要證明這個方程組有唯一解。為此，我們需要用數學歸納法證明一個更泛的結論：

當係數已知時，由類似上述方程的方程構成的方程組總是有唯一解的。

證明如下：

當時，方程組退化為。由於已知你，也知道，顯然可以解出唯一解；

假設時結論成立，此時方程組的左邊包含了的所有組合。那麼當時，考慮某個不含的未知數集合，我們能在方程組裡找到這樣兩個方程：

如果我們能用以上兩個方程構造出一個類似的方程，使得不含，那我們就能用所有的方程來構建出所有所需的方程，問題就搞定了。能么？顯然可以。

如果不含，直接用即可。

如果含且，用即可。

唯一剩下的情況是含同時無法完全抵消左邊的。此時，顯然可以用代入消元法消去形成一個左邊為的方程。

至此，整個問題解答完畢。