趣题:Alice和Bob的等值交易

    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 ,答案有所重新叙述。

12 条评论

发表评论

4  +  3  =