最长的例外序列，求证。

lulijie

若每道选择题有m个选项，N道题的答案按顺序组成一个序列。每连续的n 道题为一个组合，若某一个序列，在其中找不到两组相同的组合，那么称其为例外序列。（比如4道题为一个组合，那么第1-4题的答案为一组合，第2-5题的答案也是一个组合）
                求证：     例外序列的最大长度为m^n+n-1。
本人还不会证明，发一贴，希望集思广益，能有所突破。
------------------------------------------------------------------------------------------------
有些人看不懂这个题目，我就换一种等价的方法来描述，或者先看看n=m=4的特例情况，骰迷的帖子
     http://bbs.mf8-china.com/viewthread.php?tid=20414&;extra=page%3D2
有一个字符串S，由m种字符组成，若它上面的任何长度为n的子字符串都不相同，那么这个字符串S就称为m*n型的例外字符串，
    求证：m*n型的例外字符串的最大长度为m^n+n-1 。

[ 本帖最后由 lulijie 于 2009-2-5 22:37 编辑 ]

kexin_xiao

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

ggglgq

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

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

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的字符串，找到，在其尾部剪断，在头部加上该字符串，得到新序列，其与原序列等长，那么肯定能在其末尾加上一个字符，使得它是例外序列。

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，没有鼠标，只要键盘。

第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楼用归纳递推构造数列的方法只需要删除第四步即可使用。楼主应该是学计算机专业的吧。

第8个小笼包

楼主牛人啊，谢谢楼主

lulijie

按照数学归纳法的证明精神：从一个给定的例外序列，可以按照以下构造方法，让它不断增长，直到达到最长长度。
m* n一般情况。
第一步：在序列中检查末尾n-1个字符构成的字符串，若除末尾外，最多找到m-1处，那么肯定能在末尾加上一个字符，使得它是例外序列。
第二步：若找到m次，那么，其头n-1个字符与尾n-1个字符必定相等，将尾部这n-1个字符剪掉，使头尾相接成为环。
第三步：在环中找只出现m-1次或以下次的长度为n-1的字符串，找到，在其尾部剪断，在头部加上该字符串，得到新序列，其与原序列等长，那么肯定能在其末尾加上一个字符，使得它是例外序列。
第四步：若环中所有长n-1的字符串都出现m次，那么肯定是n>m的情况，那么至少有一种长度为n-1的字符串不在环中出现，称它为字符串S，然后在环中找S的前面部分字符串（长度从n-2一直到找到1），找到后就在其尾部剪断，在头部加上剪断后新序列的末尾n-1个字符，尾部添加一定长度的字符串，使得其末尾字符串为S，这样得到的序列就是增长的例外序列。

lulijie

那么当n>m时，在环中任何一个长度为n-1的子字符串都至少出现m次以上的情况，存不存在呢。
假设存在，因为长n-1的子字符串总可能数有m^(n-1)种，
        如果环中所有可能的长n-1的子字符串都出现，那么因为每种字符串都出现m次，所以环中以该字符串为开头的长度为n的字符串也都出现m次，由于它是例外环，所以它们都不相同。因为m^(n-1)种字符串，每种都出现了m次，所以环中长n的字符串也出现了m^(n-1) * m=m^n次，所以环长度最少为m^n次，所以序列的长度i最少为m^n+n-1，与假设矛盾。
        所以环中所有可能的长n-1的子字符串至少有一个未出现，那么假设该未出现的子字符串为U，前n-2个字母组成字符串R，末尾字母为y：
        那么在该环中，如果在环中字符串R出现，就将环在字符串R的尾部剪开，让这个序列以R为尾，在该新序列头部加上与尾部n-1个字母相同的字符串，在尾部加上y，就得到长度为i+1的新的序列,它是例外序列。
        如果在该环中，字符串R未出现。那么就设U的前n-3个字母组成字符串R1，后2个字母组成字符串y1，在环中找R1，找到R1，在其尾部剪开，让这个序列以R1为尾，在该新序列头部加上与尾部n-1个字母相同的字符串，在尾部加上y1，就得到长度为i+1的新的序列,它是例外序列。若找不到，就按该段的方法一直往前找，直到Rx为1个字母为止，肯定能找到，也按照该方法剪开加上，得到长i+1的例外序列。
－－－－－－－－－－－－－－－－－－
所以n>m时，题目也成立。

第8个小笼包

原帖由 第8个小笼包 于 2009-1-31 21:14 发表
很好，这个方法显然可以推广到N个情形，第一步已经完成，假设存在最长例外数列，则一定形成一个环状。而且你不必假设AAA出现在首位，如果出现在中间，我们可以把它切断，然后把多余的补到新数列的最后。

-------- ...

还是不要用截取的方法，不一定能保证形成最长序列，用分类讨论吧，AAA在序列的边上已经证完，由于BC地位一样，不妨设AAB在序列的边上，方法一样，还剩下4个带AA的组合，其中在中间的AAA独占3分，所以，只剩下一个带AA的组合在序列的另一边。还有一种情况，同理，不妨设AB在边上，带AB的组合总共有6个，除了序列边上的还剩5个，中间的每个AB组合各占2个，所以一定纯在一个带AB的组合在序列的另一边。所有情况讨论完毕。这个方法同样可以推广到N个的情形。