关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您将帮助确保关于塑造我们当今世界的发现和想法的具有影响力的故事的未来。
大卫·肖重返早期职业生涯。作为哥伦比亚大学的副教授，他设计了一些创新的并行计算机，然后去创办了一家非常成功的对冲基金，现在他决定使用大规模并行来模拟分子动力学计算。
这种计算中的一个关键问题被称为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. 在单条走廊上，所有人与所有六个最近的邻居见面需要多长时间？
仍然开放的是当参与者不知道他们的隔间号，因此不知道他们的位置时，如何解决问题，但他们仍然必须与他们最近的三个邻居见面。