三个好朋友到一家餐厅吃饭。饭快吃完的时候，一个服务员过来告诉他们说，他们的账单已被匿名支付了。三个人都尊重他人匿名付款的权利，但同时他们也想知道，这个匿名支付者是他们三位中的一个，还是他们三人之外的一个第四者。有没有什么办法能够让他们知道在他们之间是否有人付账，但又保证任何人都推测不出究竟是谁付的账？利用三枚硬币可以轻易做到这一点。你能想到这个办法吗？
假设这三个人围着一张圆桌坐成一圈。每个人都在自己和右手边那个人中间抛掷一枚硬币，并用另一只手挡住硬币，使得这枚硬币只有他俩才看得见。这样的话，每个人都只能看见他左右的两枚硬币（但看不见桌子对面的第三枚硬币）。每个人都大声报出，自己身边的两枚硬币的正反面是否相同。如果他们之间有人付账，则这个人报出与实际情况相反的词，相同的话说“不同”，不同的话则说“相同”。显然，如果大家说的都是真话，则报“不同”的次数一定是偶数次。如果有奇数个人说的“不同”，那么一定有一个人说的假话，这表明匿名支付账单的人就在他们之间。
注意到这个算法可以扩展到n个人。我们只需要证明，假如有n个人坐成一圈，如果大家都说真话，则说“不同”的次数一定是偶数次。证明很简单：假设所有硬币都是正面，则“不同”次数为0；另外，每把一个正面变成反面，则“不同”的次数要么不变，要么加2或者减2。
这个算法还可以用于匿名的消息广播。假如一群人围坐成一圈开会，会议过程中需要在场的一个不愿透露自己身份的人进行匿名发言（一个实际例子是，四叶集团高层开会，死亡笔记的持有者想发言）。为此，大家可以统一采用上面的投硬币协议。发言人将信息编码为01串。硬币投掷分若干轮进行。第i轮中，其他人都严格按照实际情况报是否相同，发言人则根据编码信息的第i位的值来通报：若第i位为0，则按照实际情况通报；若第i位为1，则说与实际情况相反的词。这样，实际的信息就应该是每轮叫“不同”的次数模2后的序列。这个协议过程看似很复杂，但在计算机通信中则非常实用。
Nice,sofa!!
强大……
再推广一下可以，每相邻m个人生成一个0~m-1的随机数，要发言的人再加上范围是0~m-1的一个信息，最后求和模m也是这个效果。这样“抛硬币”的次数仍然是n，广播出来的信息量达到m，但提高了“抛硬币”的成本（抛硬币机每次要发送m个信息，信息量m）。
其实之前说的一个方法也行得通，就是从一个随机数开始大家轮流往上加的办法。如果说那方法的缺点，一个是不能同时处理（网络造成的延迟会有很大影响），二是容易两个人串通对付中间那个。不过这次的方法也很容易让两个人串通求得中间那个是不是发了言，而且m越大还越容易串通。不过反过来说，这容易纠错……
有那么复杂吗？
每个人一个硬币，付钱的就翻成正面，没付的反之
依次用一个不透明的杯子倒扣住
最后打开杯子，就知道结果了，而且也不知道是谁付的
圣诞快乐
呵呵~~赞死亡笔记~~我读到前一句的时候也想到这个了~~~
开头我也想到Yann的办法的……
不过这个题目的要求是不存在提供匿名服务的第三方……
有这么麻烦吗？直接问一下服务员小姐：请问是我们中的一个人买单的吗？
@cuiaoxiang：这个方法让我想起了“如何用气压计测量高度”的经典笑话～
这个方法适合人，不适合计算机
你写段程序试试看，很容易出问题
如果在n人中找出付款的两个人，或者偶数个人呢？
其实用在计算机上还是可行的，只是感觉效率会比预料的低
呃，这个方法似乎需要一个server
问题在于，server可信么？
要严防中间人攻击啊
一个非常直接的方法。。三枚硬币交给服务员当消费请她告诉我是否是我们三人中的一个人付的帐
还是有一个小问题：如果两个人同时要证明自己没付钱，至少其中一个可以得到证明……
我觉得有一个更简单的方法，只使用一枚硬币，正面朝上，然后盖上一块餐巾布，这样谁都看不到硬币，然后三人依次伸手进去，付了款的人将硬币翻面，没付款的人就什么也不做。然后撤开餐巾布，如果硬币仍是正面，则说明是第四人付款的，否则，付款人在他们三人之中。
异或恩
这个证明可以很简单。。