關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您將幫助確保關於塑造我們當今世界的發現和想法的具有影響力的故事的未來。
大衛·肖重返早期職業生涯。作為哥倫比亞大學的副教授，他設計了一些創新的平行計算機，然後去創辦了一家非常成功的對沖基金，現在他決定使用大規模並行來模擬分子動力學計算。
這種計算中的一個關鍵問題被稱為N體問題，它需要計算N個物體（在我們的例子中是原子）的未來行為，其中物體以速度和位置開始，並且每個物體對所有其他物體施加一定的力。必須計算每個原子的軌跡，作為所有附近原子和一些遠處原子特徵的函式。我的紐約大學同事萊斯利·格林加德開發了一種針對遠處原子的基本方法（稱為“快速多極”）。肖和他的同事一直在研究如何在平行計算機上佈局近原子問題。我在文末提供了一個參考。然而，下面的謎題將把問題抽象化為它的本質核心。
一群辦公室員工被安置在一條非常長、狹窄且光線昏暗的走廊上的單人隔間裡。這條走廊非常狹窄，一次只能兩個人透過。隔間門上的數字從 0 開始，因此：0、1、2、3、...（這種編號系統在建築上不尋常，但在數學上會很方便。）我們設計解決方案的協議，就像我們從側面看走廊一樣，所以我們將討論人向右和向左移動。
每個人都想與他/她兩側的三個鄰居（即右邊的三個和左邊的三個）握手。假設每次握手需要 10 秒，並且從一個隔間移動到相鄰隔間不需要時間。
熱身
如果只有一個工人 p 想與所有六個鄰居握手，需要多長時間？
解答
只需 60 秒。所有鄰居都會來到 p。
當然，當 p 與他的六個鄰居會面時，p+7 也可以與他的六個鄰居會面，所以並行是可能的。但是我們的問題是讓每個人都與他/她左邊的三個鄰居和他/她右邊的三個鄰居握手。
這裡有一種方法。假設我們處理位置為 p、p+4、p+8 等的人，關於他們右邊的三個鄰居。這可以在 30 秒內完成。例如，p+1、p+2 和 p+3 與 p 握手的同時，p+4+1、p+4+2 和 p+4+3 與 p+4 握手。在接下來的 30 秒內，p+1、p+1+4、p+1+8 與他們的右鄰居握手。總共需要 4 * 30 = 120 秒。
1. 然而，120 秒比必要的時間長。我們能做得更好多少？
現在，假設我們不是一維，而是二維。我們有一個很大的辦公室，裡面有獨立的隔間，每個隔間四周都有走廊。隔間按它們的 x 和 y 座標編號，從左下角的 (0,0) 開始。每個人都想與所有“曼哈頓距離”在兩個或更少空間的人握手（即，所有水平和垂直距離為 2 的鄰居以及直接的對角鄰居）。
2. 我們如何做到這一點，需要多長時間？
讓我們回到單走廊的情況，但現在假設從一個隔間走到另一個隔間需要一些時間——比如，每個隔間一秒鐘——但辦公室工作人員不是握手，而只是互相看一眼，不花時間。由於走廊光線不好，人們只有在隔間內才能看清對方。一個隔間最多隻能容納七個人。
3. 在單條走廊上，所有人與所有六個最近的鄰居見面需要多長時間？
仍然開放的是當參與者不知道他們的隔間號，因此不知道他們的位置時，如何解決問題，但他們仍然必須與他們最近的三個鄰居見面。