【Think】无穷的非生成序列
2016/5/18 超级数学建模

     上方超级数学建模可加关注

     传播数学干货，学会理性的方式去思考问题

     (猛戳瞧瞧→)上期题目

     上期答案揭晓

     我们可以假设两人手中所有物品的总价值不相等(否则问题就直接解决了)。无妨假设 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 ，那么一定能从两个数列中各取一段连续子序列，使得它们的和相等。

     今日问题

     如果删除字符串A中的若干字母可以得到字符串B，我们就说A包含B(熟悉相关概念的小伙伴可能知道，有一个准确的说法叫做“B是A的子序列”，但为了避免和后面的“序列”混淆，我们不用这种说法)。例如，字符串“matrix”包含了“mix”，也包含“ati”，但不包含“it”。字符串序列aaaaa, ab, bbaa, baaaa, aa, bbacc, cbcacc, bb中的每个字符串都不包含它前面的任何一个字符串，我们称这样的字符串序列为“非生成序列”(我自己取的名字，意思是说任一字符串都不能由前面的项通过添加字母生成出来)。我们可以构造出任意长的非生成序列，例如字符串长度严格递减的序列，或者所有不同的长度为n的字符串。现在的问题是，你能构造出一个无穷长的非生成序列吗？当然，你不能使用无穷多种字母来达到这一点。

     赶紧带着你的朋友到留言区秀智商吧!!!

     也欢迎分享给爱烧脑的伙伴们!

     欲了解更多think题目，请关注并打开菜单栏“往期爆文”

    

     题目投稿：supermodeling@163.com

    http://www.duyihua.cn
返回 超级数学建模 返回首页 返回百拇医药