最长的例外序列，求证。

lulijie

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

因为有两个连续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个小笼包

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

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

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

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

第8个小笼包

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

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

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

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

lulijie

我觉得找到一种普适的构造方法，用这种构造方法保证能构造出例外数列，那么就证明了。
我有个思路，从最短序列比如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个小笼包

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

lulijie

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

第8个小笼包

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

lulijie

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

lulijie

AAABAACABBABCACBACCBBBCBCCCAA   中没有你说的那样啊

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

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