S3E30. 貌似无限的有限——良拟序(well quasi ordering)关系

请你玩玩看如下的这个写数列游戏，游戏目标是写出尽可能长的数字序列。但要符合以下规则：    数列的第n项，最多有n位。    数列左边的项，不能“嵌入”所有其右边的项。“嵌入”的定义如下：有数字字符串a和b，b的长度大于等于字符a，且存在以下情况：可以从b中删除若干字符，留下与a相等长度的字符串，留下的字符前后位置关系保持不变，并记作b'。如果a比b'按位比较，每一位数字上，a的数字都小于等于b'上的数字，称a可以“嵌入”b。比如：a=“2” 可以嵌入 b="3"，其中取b'='3'a=“321” 可以嵌入 b="13312"，其中取b'='332'a=“132” 不可以嵌入 b="2131"，因为b中找不到符合要求的3个字符的子串。以上是游戏的定义。当用n个数字玩以上游戏，可以写出的数列的最长长度，记作s(n)。思考题：对任意大的n，s(n)是否总是有限的？ 扩展思考题：去掉游戏中的第一个条件，对任意大的n，s(n)是否总是有限的？良拟序定义：喜马拉雅FM：https://www.ximalaya.com/keji/6310606/ 微信关注：dalaoli_shuxue B站: https://space.bilibili.com/423722633 知乎：https://zhuanlan.zhihu.com/dalaoli-shuxue/ 电邮 ：[email protected]   

There are no comments yet.

Please log in to write the first comment.