5 XOR-三元組問題

最近看到一個滿有趣的被包裝成演算法題目的數學謎題。記錄在這邊：

XOR-三元組問題 有 \(n\) 個人 (\(n\le 25\))，每個人頭上都有一個固定的非負整數 \(a_i\)。他們看不到自己頭上的數字。 這天他們聽到了來自天上的謎之音：『我保證你們之中存在三個人，頭上的數字 XOR 起來剛好是零！如果你知道你是某三元組的其中之一，就舉手吧。』 這個聲音說完以後就消失了。然後這群人很緊張，因此他們決定開個會因應對策。 開會的時候，他們看得到除了自己以外其他人的所有數字。如果一次會議過後，並沒有人舉手，那麼所有人都會各自回家，思考了一整晚，隔天繼續開會。 他們就這樣重複開會的流程，直到至少有一個人舉手為止。 請問在假設他們無比聰明的情況下，至少要重複幾次會議才會有人舉手？

解題想法

筆者第一次看到這題的時候腦袋是一片空白，所以只能從簡單的情形進行思考：

  • 如果只有 \(n=3\) 個人，那麼顯然為了保證謎之音的正確性，這三個人必須要同時屬於某個三元組。所以第一天的會議大家保證通通舉手。
  • 現在假設 \(n>3\)。如果第一天有人舉手了，那麼為什麼這個人會舉手？
    • 這個人會舉手，蘊含了他知道自己是其中一個三元組。這代表著他眼中看出去的所有人們，都湊不出這樣的三元組！因此，如果場上只有唯一滿足條件的三元組的話，第一天的會議中他們通通都會舉手。
  • 如果第一天沒有人舉手，那大家知道了些什麼？
    • 如果我沒舉手，代表我看到除了我以外至少有一個滿足條件的三元組。而且我知道其他人也沒舉手，尤其是我看到的滿足條件的那些人，他們也沒舉手。這代表扣掉任何一個三元組中的某個人以後，仍然存在某個三元組（可能或不可能包括我）。

然後腦袋就燒掉了。過了一陣子浮現出的歸納假設是這樣的——

引理

若第 \(k\) 天會議後仍然沒有人舉手，代表移除任意 \(k\) 個人以後，剩下的 \(n-k\) 個人之中仍然存在著滿足條件的三元組。

引理的證明

當 \(k=1\) 的時候，從上述想法中可以證明其正確性。 現在假設 \(k > 1\) 並已知在 \(k-1\) 的情形下引理是對的：即移除任意 \(k-1\) 個人之後，剩下的 \(n-k+1\) 個人之中仍然存在滿足條件的三元組。 我們將使用矛盾證法來證明該敘述： 假設第 \(k\) 天會議後仍然沒有人舉手，且存在 \(k\) 個人可以覆蓋所有滿足條件的三元組 (覆蓋指的是任意三元組至少有個人在這 \(k\) 個人之中)。令此 \(k\) 個人所成的集合為 \(S\)。 現在利用歸納假設：由於第 \(k-1\) 天會議後沒有人舉手 (所以才有第 \(k\) 天的會議)，所以移除任意 \(k-1\) 個人之後仍然存在滿足條件的三元組。考慮集合 \(S\) 中的任一人，不妨稱之為 A。

由於 A 經歷了第 \(k-1\) 天的會議，A 知道移除任何 \(k-1\) 人都會留下滿足條件的三元組。換句話說，移除了集合 \(S\) 中除了 A 以外的所有人後，剩下包含 A 在內的 \(n-k+2\) 個人之中必定有三元組。

此時，A 能夠觀察到一件事情：扣除集合 \(S\) 以後剩下的 \(n-k+1\) 個人之中，並不包含任何的三元組。因此，A 本人自知其必定身處某個三元組之中，A 應當舉手。此舉與第 \(k\) 天會議後無人舉手的假設矛盾，所以引理得證。

一個轉化

上面的引理告訴我們，若存在某個最小的集合 \(S\) 覆蓋了所有的三元組，那麼在第 \(|S\vert \) 天的會議上，至少集合 \(S\) 中的所有人都會一起舉手（可能有其他人跟著一起舉手，因為這樣的集合可能不只一個）。因此，問題便轉化到了超圖 (hypergraph) 上的最小點覆蓋問題 (minimum vertex cover)。 若超圖上每條邊都是三元組的話，這樣的問題又被稱為 3-Hitting Set 問題、或是 Minimum Transversal in Hypergraph of Rank 3。

演算法

於是，我們就可以得到一個 \(O(n2^n + n^3)\) 時間複雜度的演算法啦！首先暴力地將所有的三元組找出來。接著，我們做個動態規劃將所有能夠覆蓋所有三元組的集合找出來。最後只要算出最小的集合大小就行啦！

備註

這題轉化以後與 XOR 或三元組毫無關係呀！不曉得能不能利用 XOR 的特性得到多項式的演算法？

備註 2：關於 3-Hitting Set 問題

3-Hitting Set 問題本身是 NP-完備的。如果想要找到精確的最小集合，存在著以下幾種演算法：

  • [Wahlström 2004] 時間複雜度 \(O(1.6538^n)\)、使用多項式空間。
  • [Wahlström 2004] 時間複雜度 \(O(1.6316^n)\)、使用指數空間。
  • [Fernau 2010] 時間複雜度 \(O^*(2.0755^k)\)，這在最小集合大小 \(k\) 很小的時候很好用。

此外在計數或枚舉方面：

參考資料