Alice 的手中有 n 件物品，每件物品的价值都是一个 1 到 n 之间的整数； Bob 的手中也有 n 件物品，每件物品的价值也都是 1 到 n 之间的整数。现在，两人想要进行一次等值的交易，即 Alice 从自己手中拿出至少一件物品， Bob 从自己手中拿出至少一件物品，使得两人所拿出的物品总价值相等。求证：这是总能办到的。
我们可以假设两人手中所有物品的总价值不相等（否则问题就直接解决了）。无妨假设 A 手中的物品的总价值小于 B 手中的物品的总价值（否则的话，交换 A 、 B 的身份即可）。
现在，从 A 开始，两人轮流从自己手中挑选物品摆在桌面上。在第 i 轮中， A 摆出自己的第 i 件物品， B 则适当地摆出零件、一件或多件物品，让桌面上 B 的物品总价值等于 A 的物品总价值，或者小于 A 的物品总价值，但差值不超过 n – 1 。注意到 B 所拥有的物品总价值比 A 更高，并且所有物品的价值数目都是 1 到 n 之间的数，因此这一点是一定能办到的。第 n 轮结束后， A 就已经把自己手中所有的物品都摆上桌面了，但 B 还没有把自己手中所有的物品都摆上去。让我们把第 i 轮结束后，两人摆在桌面上的物品的总价值差记作 Ri 。
如果存在某个 Ri = 0 ，这就说明在某个时刻，桌面上的物品已经等值了，问题就解决了。如果所有的 Ri 都不等于 0 呢？这样的话，数列 R1, R2, …, Rn 中的所有数都只有 1 到 n – 1 共 n – 1 种可能的取值，然而数列中一共有 n 个数，因此其中必然会有两个相同的数，比方说 Rx = Ry （不妨假设 x < y ）。这就说明，在第 x 轮结束后，桌面上 A 的物品总价值比 B 的物品总价值大多少，到第 y 轮结束后，桌面上 A 的物品总价值也就比 B 的物品总价值大多少。因此，在第 x + 1 轮到第 y 轮之间，两人各自摆上桌面的物品就是等值的了。
注意，我们实际上证明了一个更强的结论：假如有两个长度均为 n 的正整数序列，其中每个数都不超过 n ，那么一定能从两个数列中各取一段连续子序列，使得它们的和相等。
问题来源： http://www.cs.cmu.edu/puzzle/puzzle24.html ，答案有所重新叙述。
声明：文章转自Matrix67博客，版权归原作者所有，转载仅供学习使用，不用于任何商业用途，如有侵权请联系删除，谢谢。
