魔方吧·中文魔方俱乐部

标题: 最长的例外序列，求证。 [打印本页]

作者: lulijie 时间: 2009-1-25 11:52:00 标题: 最长的例外序列，求证。

若每道选择题有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 编辑 ]

作者: 汪小光 时间: 2009-1-25 11:58:09

不懂……等强人解释一下

作者: R'cube 时间: 2009-1-25 12:01:30

做板凳观望了~~~~~~~

作者: haohejiao 时间: 2009-1-25 12:03:28

哈哈地板等等 ~~~~~~~~

作者: R'cube 时间: 2009-1-25 12:52:14

貌似没人来解答难题啊

作者: juventus66 时间: 2009-1-25 13:27:45

惭愧,不会啊~~~~

作者: 骰迷 时间: 2009-1-25 16:27:15

樓主好像很喜歡另外開帖哈
頂一下

作者: 第8个小笼包 时间: 2009-1-26 00:02:10

把已经找到的例外数列首位相接，应该能称为一个例外的环。我真的不会这个题目，希望能有高手教教。

作者: lulijie 时间: 2009-1-31 11:49:27

8楼的环的概念很赞。
长度为256的由ABCD四个字母组成的首位相接的环，从环上任意截取连续的4个字母为一个组合，再截取另一个组合（按相同方向排列，比如都是顺时针）。求证必然存在一个环，在它上面不存在两种相同的组合，我们把它叫做例外环。若存在例外环，一共有几个例外环？

以下长度259的例外序列：
DADDACDDCBCDCABCDBCADDBDCAACDCDDAABCBCCDCCCCBCABBDCBADABCCABD
DADAADACBAADCDABACACADBCDACCBBACDAAAACBBCBDABDBCCCAADBAACCDDDD
CDCBDCCBABCAAABBBCCBDBBCACCACBCBACBDDCACDBBBBABBAAADDCCADADBBA
DCBBBDBACCCDADCADCCDBABABDACAABAABDCDBDBDDBADDDBCBBDDDABBCDDBB
DAACABADBDAD

若去掉尾部与头部相同的3个字母，首尾相接，组成长度256的环。但它不是例外环。
----------------------
看错了，它是例外环，但一共有几个例外环呢？，字母ABCD互换位置，也是例外环。

[ 本帖最后由 lulijie 于 2009-1-31 13:01 编辑 ]

作者: o嗬飽彈o 时间: 2009-1-31 11:58:18

楼上很强大

作者: 第8个小笼包 时间: 2009-1-31 15:09:22

应该只有m是奇数的情况，才可能出现有例外数列但不是例外环的情形，m是偶数的情形下，应该一定存在例外环的情形。

作者: bhw19930503 时间: 2009-1-31 15:12:09

无语啊完全不只所云

作者: lulijie 时间: 2009-1-31 15:32:33

3X3最大例外序列，长度29：AAABAACABBABCACBACCBBBCBCCCAA
3X3最大例外环，长度27：AAABAACABBABCACBACCBBBCBCCC （首尾相接）

作者: lulijie 时间: 2009-1-31 15:35:22

2X2最大例外序列，长度5：AABBA，BBAAB 只有两个。还有倒过来2个，ABBAA，BAABB
2X2最大例外环，长度4：AABB（首尾相接），只有1个。

[ 本帖最后由 lulijie 于 2009-1-31 21:55 编辑 ]

作者: lulijie 时间: 2009-1-31 15:38:52

3X3的最长的例外序列就很多了：以下都是
ABCAACCACBAAABABBBCBCCCBBACAB
ABCAACCACBAAABABBBCCCBCBBACAB
ABCAACCACBAAABABBCBCCCBBBACAB
ABCAACCACBAAABABBCCCBCBBBACAB
ABCAACCACBAAABACABBBCBCCCBBAB
ABCAACCACBAAABACABBBCCCBCBBAB

作者: 第8个小笼包 时间: 2009-1-31 16:49:05

应该跟同构有点关系，另外，无论是2×2还是3×3，楼上，都不要把它看成是N^N+N-1是最大序列，这样掩盖了一般情况，应该看成N^N是最大序列，不过2×2的一定能成循环，但3×3的不一定。否则你加一个和环首位字母一样的，则永远无法构成循环环。

[ 本帖最后由第8个小笼包于 2009-1-31 17:02 编辑 ]

作者: lulijie 时间: 2009-1-31 17:41:38

3X3的最长的例外序列只要首2个字母和尾2个字母相同，就必然能成例外环。
但存在不存在首尾不相同的例外序列呢？
不存在。最长的例外序列首尾两个必然相同。
可以这样证明：最长的例外序列中涉及到所有的组合，以3X3为例，3个字母一组总共有27种组合，涉及到3x27=81个字母，它们只由ABC三个字母组成，由于高度对称性，A、B、C涉及到的个数相等，都等于27个。
而长度29的例外序列，涉及到的组合数就是全部组合，将这所有的组合全部相加，A、B、C的个数就都是27，为3的倍数。
该序列的首和尾第一个字母计算了1次，首和尾第二个字母计算了2次，其他字母都计算了3次。
因为A、B、C的总个数为3的倍数。所以首1、首2、尾1、尾2  四个字母中，A在其中的个数
                  要么0个。
                  要么2个，首1尾2 或首2尾1。
                  要么4个全是。
同理B、C也相同。所以首2个字母与尾2个字母必相同。
同理对其他m*n的最长的例外序列也能证明头尾N-1个字母必须相同，
所以最长的例外序列必能构成例外环，与奇偶无关。

作者: 第8个小笼包 时间: 2009-1-31 18:12:18

你是对的，我忽略了。你想到解题的方法了吗？

作者: lulijie 时间: 2009-1-31 18:30:59

对一般情况 m*n 的证明我还不会。但如果m、n已知的话，可以让电脑来找例外序列。电脑虽然在速度方面明显优于人脑，但对一般情况的证明、归纳却不如人脑。电脑来证明一般情况，只能采取穷举法，（如魔方最少步数的证明），但m、n却又无穷个，显然电脑无法胜任。

作者: 第8个小笼包 时间: 2009-1-31 18:38:31

你不是都已经发现每个数都重复3次了吗，应该很接近答案了。这里讨论很不方便啊，很多时候词不达意。

作者: lulijie 时间: 2009-1-31 18:52:12

17楼的证明：
因为A、B、C的总个数为3的倍数。所以首1、首2、尾1、尾2  四个字母中，A在其中的个数
                  要么0个。
                  要么2个，首1尾2 或首2尾1。
                  要么4个全是。
同理B、C也相同。所以首2个字母与尾2个字母必相同。
---------------------------------------------
红字部分有疏漏，2个A的情况也可以是首1首2或尾1尾2。如果首1首2为A，尾1尾2为B，那么首尾就不相同了。但这种情况存在吗，在电脑找到的例外序列中还没见过这种情况。

作者: lulijie 时间: 2009-1-31 19:37:43

因为有两个连续A的组合共有：AAA，AAB，AAC，BAA，CAA 共5种。
假设最长3*3序列的首1首2为AA，那么假设AAA出现在该序列的最前，那么该序列就可表示为AAAX，（X表示不定长度的序列）。这3个A涉及到的含AA组合数为2个，那么应该还有AA落在该序列中，假设它落在中间部分，那么它涉及到组合2个，因为涉及到AA的组合总共5个，所以还有一个含AA的组合，它只能落到尾部，（只有AA落到尾部，它才只涉及到一个组合）。所以头为AAA，尾必为AA。
另外假设头为AA，那么它涉及到的含AA的组合为1个，另外此序列中还必有AAA，假设AAA在尾部，那就证明了首尾2个字母相同。所以假设AAA在中间，若AAA在中间，那么它涉及到的含AA的组合为3个，所以还剩1个含AA的组合，同理它只能落到尾部。
综上所述，假设最长例外序列的首2个字母相同，那么尾2个字母必与它们相同。

作者: 第8个小笼包 时间: 2009-1-31 21:14:06

很好，这个方法显然可以推广到N个情形，第一步已经完成，假设存在最长例外数列，则一定形成一个环状。而且你不必假设AAA出现在首位，如果出现在中间，我们可以把它切断，然后把多余的补到新数列的最后。

---------------------------------------------

现在只需要证明一定存在最长例外序列而已，我尝试过用反证法，但是不成功。

[ 本帖最后由第8个小笼包于 2009-1-31 21:35 编辑 ]

作者: 第8个小笼包 时间: 2009-1-31 21:17:08

以3×3的序列为例，我尝试把它分成3个相同的，2个相同的，还有互不相同的三种，但是我并没有什么进展。你有什么高见呢？

---------------------------------------------

像你上面那样构造行不行，首先以AAA……A（N个）排头，然后还有2（N-1）个含AAA……A（N-1个）的组合，然后让他们彼此分开，再以其中一个押尾。再以反证法辅助，不知可行否？

[ 本帖最后由第8个小笼包于 2009-1-31 21:35 编辑 ]

作者: lulijie 时间: 2009-1-31 21:45:51

我觉得找到一种普适的构造方法，用这种构造方法保证能构造出例外数列，那么就证明了。
我有个思路，从最短序列比如A开始，逐步往后添加新的字母，从最小开始，比如一律先加上A，若加了A后，发现不行，再改加B，不行再改加C.................
m*n 序列
比如第1到第n个可以是A，第n+1只能是B，第n+2至2n个可以是A，第2n+1只能是C,.............
我就是用这种方法让电脑很快找到例外序列的。

[ 本帖最后由 lulijie 于 2009-1-31 21:51 编辑 ]

作者: 第8个小笼包 时间: 2009-1-31 22:02:01

但是如果这样操作存在一个难点，有可能出现某个数不能马上判断它不能填，而是在进行了一定操作以后才发现之前的判断是错误的
例如AAABACABBBCCCBCBBABBCACCAACBA，第6个字母本来应该填A才是，按照字典排列法，应该先排完AA才到AB，但是第6个字母却跳过A直接填C，因为如果再填A的话，下一个只能填C，例如AAABAAC，至此AA后跟一个的全部排完，只能接AB，例如AAABAAC，但是实际上出现排列的顺序实际上是AAA,AAB,ABA,BAA,AAC，并不能保证它按字典排列顺序的方法进行

作者: lulijie 时间: 2009-1-31 23:06:20

本序列为例外序列 AAABAACABBABCACBACCBBBCBCCCAA
可以按字典的方法排列。
4*4的按字典顺序排列最前的是：
AAAABAAACAAADAABBAABCAABDAACBAACCAACDAADBAADCAADDABABACABAD
ABBBABBCABBDABCBABCCABCDABDBABDCABDDACACADACBBACBCACBDAC
CBACCCACCDACDBACDCACDDADADBBADBCADBDADCBADCCADCDADDBAD
DCADDDBBBBCBBBDBBCCBBCDBBDCBBDDBCBCBDBCCCBCCDBCDCBCDD
BDBDCCBDCDBDDCBDDDCCCCDCCDDCDCDDDDAAA
4*2按字典顺序排列最前的是
AABACADBBCBDCCDDA
4*3按字典顺序排列最前的是
AAABAACAADABBABCABDACBACCACDADBADCADDBBBCBBDBCCBCDBDCBDD
CCCDCDDDAA
3*2按字典顺序排列最前的是
AABACBBCCA

作者: 第8个小笼包 时间: 2009-1-31 23:17:39

按字典排列法的话，AAA×排完以后，应该是AABA才对啊，怎么接AABB了？

作者: lulijie 时间: 2009-1-31 23:23:28

5*4按字典顺序排列最前的例外序列：
AAAABAAACAAADAAAEAABBAABCAABDAABEAACBAACCAACDAACEAADBAADCAADDAADEAAEBAAECAAEDAAEE
ABABACABADABAEABBBABBCABBDABBEABCBABCCABCDABCEABDBABDCABDDABDEABEBABECABEDABEEACA
CADACAEACBBACBCACBDACBEACCBACCCACCDACCEACDBACDCACDDACDEACEBACECACEDACEEADADAEAD
BBADBCADBDADBEADCBADCCADCDADCEADDBADDCADDDADDEADEBADECADEDADEEAEAEBBAEBCAEBDAEB
EAECBAECCAECDAECEAEDBAEDCAEDDAEDEAEEBAEECAEEDAEEEBBBBCBBBDBBBEBBCCBBCDBBCEBBDCBB
DDBBDEBBECBBEDBBEEBCBCBDBCBEBCCCBCCDBCCEBCDCBCDDBCDEBCECBCEDBCEEBDBDBEBDCCBDCD
BDCEBDDCBDDDBDDEBDECBDEDBDEEBEBECCBECDBECEBEDCBEDDBEDEBEECBEEDBEEECCCCDCCCECCD
DCCDECCEDCCEECDCDCECDDDCDDECDEDCDEECECEDDCEDECEEDCEEEDDDDEDDEEDEDEEEEAAA
5*3按字典顺序排列最前的例外序列：
AAABAACAADAAEABBABCABDABEACBACCACDACEADBADCADDADEAEBAECAEDAEEBBBCBBDBBEBCCBCDBCE
BDCBDDBDEBECBEDBEECCCDCCECDDCDECEDCEEDDDEDEEEAA
5*5按字典顺序排列最前的例外序列：电脑算了10分钟都没出结果。
------------------------------------------------------
不知能不能从中找到规律。

作者: lulijie 时间: 2009-1-31 23:27:11

AAABAACABBABCACBACCBBBCBCCCAA 中没有你说的那样啊

哦我知道了，你是说4*4中的。
因为AABA，在序列的3-6位已经有了，不能再排它了。

[ 本帖最后由 lulijie 于 2009-1-31 23:31 编辑 ]

作者: 第8个小笼包 时间: 2009-1-31 23:30:23

原帖由 lulijie 于 2009-1-31 23:06 发表
本序列为例外序列 AAABAACABBABCACBACCBBBCBCCCAA
可以按字典的方法排列。
4*4的按字典顺序排列最前的是：
AAAABAAACAAADAABBAABCAABDAACBAACCAACDAADBAADCAADDABABACABAD
ABBBABBCABBDABCBABCCABCDABDBABDC ...

在出现完AAAD以后，为什么是接AABB而不是AABA呢？

作者: lulijie 时间: 2009-1-31 23:40:29

请看30#的说明，因为前面已经有了

作者: 第8个小笼包 时间: 2009-1-31 23:42:38

你这样要不断检查之前出现的组合，是算一种计算机算法吧，不太像证明的思路。

作者: 第8个小笼包 时间: 2009-1-31 23:52:51

对了，以3×3的为例，以AAA排首位，再以AA结尾，中间再有一个AA连续。然后对于B和C来说，都在序列的中间了，而且只有连续的BBB，BB，CCC，CC各一个而已，剩下的就是单独的两个A，B和C个四个，这样来插入排序的方法不知可行否？

作者: ursace 时间: 2009-1-31 23:54:48

用归纳法怎么样

作者: 第8个小笼包 时间: 2009-2-1 00:06:17

有点困难，问题是在于组合的数多了一个以后排列的顺序全部不一样了，很难使用第一和第二归纳法

作者: lulijie 时间: 2009-2-1 10:04:37

感谢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 编辑 ]

作者: 第8个小笼包 时间: 2009-2-1 12:32:03

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

-------- ...

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

作者: lulijie 时间: 2009-2-1 13:05:41

那么当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时，题目也成立。

作者: lulijie 时间: 2009-2-1 13:45:24

按照数学归纳法的证明精神：从一个给定的例外序列，可以按照以下构造方法，让它不断增长，直到达到最长长度。
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，这样得到的序列就是增长的例外序列。

作者: 第8个小笼包 时间: 2009-2-3 12:56:11

楼主牛人啊，谢谢楼主

作者: 第8个小笼包 时间: 2009-2-5 12:32:37 标题: 回复 37# 的帖子

楼主基本上使用的方法和证明的方向都对了，修正一些小错误就行了。作为对楼主给我们这么清晰的一个证明方案，我在这里代为修正。
因为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 时间: 2009-2-5 19:55:47

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 时间: 2009-2-5 20:37:17

我也觉得无论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 时间: 2009-2-11 09:23:52

　　　　
　　　　　
　　　　
　　　　
　　lulijie 的数学能力很强呀！春节期间为我们大家提供了很多数学“大餐”，

为魔方吧 ★ 数学、算术趣题 ★ 增添了很多绚丽“色块”，很好！

　
　　　
　　　　

不知 lulijie 是否愿意把您所发表或参与的有心得的主题整理成一个

汇总集，置顶以便大家学习？帖子格式可以参考魔方常用软件分类汇总

http://bbs.mf8-china.com/viewthread.php?tid=3132&extra=page%3D1　
  　　　　
加上心得注释和超级连接等内容，您的帖子一定很受欢迎！
　　　　
　　　　
　　　　
　　　　　　　
　　　　
　　　　
　　　　

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

作者: kexin_xiao 时间: 2009-4-5 23:34:51

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)