浴缸里的惊叹——11. 最少需要多少通电话

公司里有100个女生，每个女生都有一个独家八卦消息。两个女生可以通过电话联系，一通电话将使得双方都获知到对方目前已知的全部消息。一个有趣的问题是，要想所有100个女生都知道所有100条八卦消息，最少需要多少通电话呢？你的任务是，设计一种只用196通电话的方案。 大家可能首先会想到只需要198通电话的方案：从100个人中选一个消息汇总人，所有99个人都打电话给她，她再打电话给所有人，这样总共需要198通电话。其实，汇总阶段的最后一通电话和发布阶段的第一通电话可以合并为一通电话，这样的话该方案实际上只需要197通电话。但是，怎样把电话的数目继续减少到196通呢？这就不太好想了。 让我们先来考虑一下简单的情况。如果整个公司只有两个女生，显然一通电话就够了；如果整个公司只有三个女生，显然需要三通电话。如果整个公司只有四个女生呢？一个非常巧妙的方法是，让A、B互相通话，让C、D互相通话，此时每个人都知道了（包括自己的）两条消息；然后A和C通话，B和D通话，从而使得每个人都获知另外两条自己还不知道的消息。 现在，我们就有了一种方法，可以让100个女生用196通电话解决问题。首先，从100个人当中选出四个人作为消息汇总人。其余每个人都任意选择一个汇总人并与之通话，这一共需要96通电话。接下来，这四个汇总人再用刚才的方法，用4通电话互相更新一下消息。最后，四个汇总人再把电话打回去，实现所有消息的全部共享，这又需要96通电话。于是，我们总共只用了196通电话。 事实上，如果公司里有n个人的话（这里假设n≥4），那么2n-4通电话已经是最好的方法了。最常见的一种证明方法由Brenda Baker和Robert Shostak在1972年给出。