- 最后登录
- 2013-11-11
- 在线时间
- 873 小时
- 阅读权限
- 40
- 注册时间
- 2008-9-15
- 积分
- 1194
- 帖子
- 924
- 精华
- 6
- UID
- 44804
- 性别
- 保密
- 积分
- 1194
- 帖子
- 924
- 精华
- 6
- UID
- 44804
- 性别
- 保密
|
感谢TLTV,感谢CCTV,最主要的是感谢35#LV
你的提议有如深夜中的一声惊雷,震醒了在黑暗中艰难摸索的我们。我要继承你的提议,完成你未尽的事业,完成用数学归纳法来证明的壮举。
m*n序列(m>=n),字母m个,组合长度n个,那么例外序列的最大长度为m^n+n-1。
对于长度为m^n+n的序列中可选择的组合有m^n+1个,而组合总共只有m^n,所以必有两个组合相同,所以它肯定不是例外序列。
下面我们证明m^n+n-1长度的序列必定存在例外序列:
我们用P(k)表示长度为k的序列。
第一步:k=n+1 时,P(k)存在例外序列。
显然,由n个A和1个B组成的序列就满足条件。
第二步:假设k=i 时,P(k)存在例外序列,那么P(k+1)也存在例外序列。(i<m^n+n-1)
对于长度为i的例外序列,假设其末尾n-1个字母是字符串S,
那么如果在该序列中,字符串S除了末尾的外只出现m-1次,那么必然可以在末尾加上一个字母,使它仍然是例外序列。(因为以字符串S开头,n长度的组合共有m种)。
而如果在该序列中字符串S除了末尾的外出现m次,那么就不能在末尾加上任何字母使得它成为例外序列,这种情况,该序列必然是字符串S开头。(因为以字符串S结尾,n长度的组合共有m种,该序列包括尾部的字符串S,总共出现m+1,所以必有一个出现在头部)。我们去掉尾部的字符串S,首尾相接,就构成长度为i-n+1的例外环。在这个环中,假设存在一个子字符串Z(长度为n-1),它在该环中最多只出现m-1次,那么我们从Z的前面剪开环,在尾部加上字符串Z,得到长度为i的新的序列,该序列必定是例外序列。由于除了尾部的字符串Z外,字符串Z只在该序列中出现m-1次,所以必定可在尾部加上一个字母,使其仍然是例外序列,我们就得到长度为i+1的例外序列。
那么在环中任何一个长度为n-1的子字符串都至少出现m次以上的情况,存不存在呢。
假设存在,比如字符串Z,出现了m次,那么那么该字符串加上在它后面的字母组成长度为n的组合也有m个,由于它们都是由字符串Z开头,而该环又是例外环,所以它们是相互不同的组合,它们尾部的字母必定不相同。也就是说所有的可能字母(m个)全部出现。对于字母A来说,假设它前面的n-2个字母与它构成字符串Y,那么Y也在该环中出现m次,所以字母A在该环中至少出现了m次。同理,对于其他任何字母,也都出现了至少m次,所以该环的长度至少为m^m,由于m>=n,所以该环的长度必定大于或等于m^n,所以i>=m^n+n-1。这与第二步的假设(i<m^n+n-1)相矛盾。
综上所述,假设k=i 时,P(k)存在例外序列,那么P(k+1)也存在例外序列。(i<m^n+n-1)。
所以i=m^n+n-1时,也存在例外序列。
--------------------------
因此 例外序列的最大长度为m^n+n-1。
---------------------------------------------------------------------------------------
上述红字部分有错误,谢谢42#指出。
[ 本帖最后由 lulijie 于 2009-2-5 21:28 编辑 ] |
|