最长的例外序列，求证。

第8个小笼包

楼主牛人啊，谢谢楼主

第8个小笼包

楼主基本上使用的方法和证明的方向都对了，修正一些小错误就行了。作为对楼主给我们这么清晰的一个证明方案，我在这里代为修正。
因为m个字母总共出现m次，这个环的总长度应该是m^2而不是m^m。
其实也不需要分n≤m和m＞n两种情况进行证明。
证明的方法首先是
引理1.证明如果存在最长无重复组合的序列，一定构成首尾相接的循环环，方法参考38楼；
引理2.证明如果一个无重复组合的序列某n-1长度的组合已经出现m次，仍然构成一个循环环，方法参考37楼第二步第三段；
引理3.证明如果任意一个无重复组合循环环中的任意n-1长度的组合均出现m次，则这个循环环已经包含了这m个字母的所有组合，即已经是最大循环环。
证明方法如下：
不妨设引理3所述循环环为X
对于m个字母组成的n长度的任意组合X1X2X3……Xn，一定能在X中找到。因为任意以X1结尾的n-1长度的组合已经全部出现，故一定存在以X1X2结尾的n长度的组合；
同理，以X1X2结尾的n-1长度的组合也全部出现，也可以找到以X1X2X3结尾的n长度的组合；
以此类推，一定能从中找到n长度的组合X1X2X3……Xn，证毕。
根据引理1，2，3不难推出任意有m个选项，每连续N道题的答案为一个组合的最大不重复循环环的长度为m^n，也即最大例外序列的长度为m^n+n-1。
另外，40楼用归纳递推构造数列的方法只需要删除第四步即可使用。楼主应该是学计算机专业的吧。

lulijie

42#的楼主看的很仔细嘛，m个字母总共出现m次，这个环的总长度应该是m^2而不是m^m。谢谢楼主指出。所以我后面部分给出的证明就不对了。其实我在n>m的证明过程中都没有涉及到n比m大这个条件，所以这个证明同样适用于n<=m的情况。所以对于任何n，m的情况，k=i存在例外序列，那么k=i+1同样存在例外序列。所以命题成立。
而楼主在证明引理3时：
对于m个字母组成的n长度的任意组合X1X2X3……Xn，一定能在X中找到。因为任意以X1结尾的n-1长度的组合已经全部出现，故一定存在以X1X2结尾的n长度的组合；
楼主得出的红字部分，本人智愚，理解不了，我只能得出X1在序列中出现了至少m次，所以以X1为结尾的n-1长度的组合也至少出现了m次，而以X1为结尾的n-1长度的组合总共有m^(n-2)种，所以远比m种多，所以得出红字部分的结论，我觉得好像不行。
循环环中的任意n-1长度的组合均出现m次，不等于所有可能的n-1长度的组合均出现。
就算经过证明前者能推导出后者，也是需要证明的，不能拿来就当做理所当然的。
--------------------------------------------------------------------------------------------
还有，本人不是计算机科班出身，本人的工作是救死扶伤。上计算机课只在大学里上过1个学期，那时学的还是DOS，LOTUS123，没有鼠标，只要键盘。

lulijie

我也觉得无论m和n 谁大谁小（引理3.证明如果任意一个无重复组合循环环中的任意n-1长度的组合均出现m次，则这个循环环已经包含了这m个字母的所有组合，即已经是最大循环环。）
这个判断成立。
因为所有m个字母都出现，那么对于任何字符X1，以X1结尾的n-1长度的字符串因为出现了m次，加上跟在它后面的字母组成的n长度的组合也出现了m次，又因为环为例外环，所以后面的的字母全不相同。（此论断我前面已经提过），所以X1后面的字符可以是任何值，所以对于任何字母X1，X2，X1X2字符串在环中肯定出现。同样对于以X1X2结尾的n-1长度的字符串，因为也出现了m次，同理得出X1X2后面的字母可以是任何值，所以对于任何字母X1，X2，X3，X1X2X3字符串在环中肯定出现，同理可以推导出楼主的结论：
   对于m个字母组成的n长度的任意组合X1X2X3……Xn，一定能在X中找到。
所以就证明了楼主提出的引理3。
也可能楼主就是这个意思，不过用文字表达的时候，让人不明白，至少是让我不明白。
经过35#的天才创意，以及楼主和本人的努力，我觉得这个题目的论断应该是得到了完善的证明。
-------------------------------------------------------------------------------------------
按照数学归纳法的证明精神：从一个给定的例外序列，可以按照以下构造方法，让它不断增长，直到达到最长长度。
m* n一般情况。
第一步：在序列中检查末尾n-1个字符构成的字符串，若除末尾外，最多找到m-1处，那么肯定能在末尾加上一个字符，使得它是例外序列。
第二步：若找到m次，那么，其头n-1个字符与尾n-1个字符必定相等，将尾部这n-1个字符剪掉，使头尾相接成为环。
第三步：在环中找只出现m-1次或以下次的长度为n-1的字符串，找到，在其尾部剪断，在头部加上该字符串，得到新序列，其与原序列等长，那么肯定能在其末尾加上一个字符，使得它是例外序列。

ggglgq

　　　　
　　　　　
　　　　
　　　　
　　lulijie 的数学能力很强呀！ 春节期间为我们大家提供了很多数学“大餐”，
  
为魔方吧 ★ 数学、算术趣题 ★ 增添了很多绚丽“色块”，很好！
  
　   
    　　　
　　　　   
   
    不知 lulijie 是否愿意把您所 发表 或 参与 的有心得的主题整理成一个
  
汇总集， 置顶 以便大家学习 ？ 帖子格式可以参考 魔方常用软件分类汇总
  
    http://bbs.mf8-china.com/viewthread.php?tid=3132&extra=page%3D1　
  　　　　
加上 心得注释 和 超级连接 等内容，您的帖子一定很受欢迎！
　　　　
　　　　
　　　　
　　　　　　　
　　　　
　　　　
　　　　

[ 本帖最后由 ggglgq 于 2009-2-11 11:16 编辑 ]

kexin_xiao

ＬＺ是高手啊，已经５贴精华了，数学方面的确有造诣