最长的例外序列，求证。

第8个小笼包

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

bhw19930503

无语啊    完全不只所云

lulijie

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

lulijie

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

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

lulijie

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

第8个小笼包

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

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

lulijie

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个小笼包

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

lulijie

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

第8个小笼包

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