炫智商--趣题：Alice和Bob的等值交易
摘自Ｍatrix67
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 ，那么一定能从两个数列中各取一段连续子序列，使得它们的和相等。
收集：詹妮
后期：谢天扬
===============================================================================
===============================================================================
===============================================================================
欢迎致订SUFE-ERC学术班微信公众平台！
如果大家对我们的工作有好的建议，或是
有宝贵的资源愿意与大家分享，请向我们
邮箱投稿，不胜感激！也欢迎登陆我们的
贴吧论坛，发表您的观点评论或参与话题
讨论，激荡思维！
我们的邮箱：xueshuban321@126.com
我们的论坛（百度）：（sufe_erc学术班）
http://tieba.baidu.com/f?kw=sufe_erc%D1%A7%CA%F5%B0%E0&fr=index
摘自Ｍatrix67
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 ，那么一定能从两个数列中各取一段连续子序列，使得它们的和相等。
收集：詹妮
后期：谢天扬
===============================================================================
===============================================================================
===============================================================================
欢迎致订SUFE-ERC学术班微信公众平台！
如果大家对我们的工作有好的建议，或是
有宝贵的资源愿意与大家分享，请向我们
邮箱投稿，不胜感激！也欢迎登陆我们的
贴吧论坛，发表您的观点评论或参与话题
讨论，激荡思维！
我们的邮箱：xueshuban321@126.com
我们的论坛（百度）：（sufe_erc学术班）
http://tieba.baidu.com/f?kw=sufe_erc%D1%A7%CA%F5%B0%E0&fr=index
