趣题：匿名的消息广播

三个好朋友到一家餐厅吃饭。饭快吃完的时候，一个服务员过来告诉他们说，他们的账单已被匿名支付了。三个人都尊重他人匿名付款的权利，但同时他们也想知道，这个匿名支付者是他们三位中的一个，还是他们三人之外的一个第四者。有没有什么办法能够让他们知道在他们之间是否有人付账，但又保证任何人都推测不出究竟是谁付的账？利用三枚硬币可以轻易做到这一点。你能想到这个办法吗？

假设这三个人围着一张圆桌坐成一圈。每个人都在自己和右手边那个人中间抛掷一枚硬币，并用另一只手挡住硬币，使得这枚硬币只有他俩才看得见。这样的话，每个人都只能看见他左右的两枚硬币（但看不见桌子对面的第三枚硬币）。每个人都大声报出，自己身边的两枚硬币的正反面是否相同。如果他们之间有人付账，则这个人报出与实际情况相反的词，相同的话说“不同”，不同的话则说“相同”。显然，如果大家说的都是真话，则报“不同”的次数一定是偶数次。如果有奇数个人说的“不同”，那么一定有一个人说的假话，这表明匿名支付账单的人就在他们之间。

注意到这个算法可以扩展到n个人。我们只需要证明，假如有n个人坐成一圈，如果大家都说真话，则说“不同”的次数一定是偶数次。证明很简单：假设所有硬币都是正面，则“不同”次数为0；另外，每把一个正面变成反面，则“不同”的次数要么不变，要么加2或者减2。

这个算法还可以用于匿名的消息广播。假如一群人围坐成一圈开会，会议过程中需要在场的一个不愿透露自己身份的人进行匿名发言（一个实际例子是，四叶集团高层开会，死亡笔记的持有者想发言）。为此，大家可以统一采用上面的投硬币协议。发言人将信息编码为01串。硬币投掷分若干轮进行。第i轮中，其他人都严格按照实际情况报是否相同，发言人则根据编码信息的第i位的值来通报：若第i位为0，则按照实际情况通报；若第i位为1，则说与实际情况相反的词。这样，实际的信息就应该是每轮叫“不同”的次数模2后的序列。这个协议过程看似很复杂，但在计算机通信中则非常实用。