几个根基东西的证明

邱志红

（这是Part1,还请留意后面的Part2,Part3……等）

魔方中有很多重要的变换及定律在论坛里都被大家默认为是正确的而直接加以运用，往往这些都是经验所得，其理论的根基相当薄弱。许多人都是知其然，而不知其所以然，感觉魔方的变化是被什么定理定律所支配，但又说不清楚是什么。而且在遇到不同类型的魔方的时候，发现以前的经验在有的地方行不通，便搞起特殊情况特殊对待来了，对魔方没有形成统一的，深入的认识。希望下面我的证明用到的知识方法及思路思想能让你对魔方有一个较清晰的“再”认识。而且证明过程力求深入浅出，几乎人人能懂。

注意：需要重视的是我证明用到的知识方法及思路思想，而不是对某个具体问题的具体证明过程。另外下文所述的一转都是指的魔方的单位转动。

有这样一个事实：魔方不能只是两角对换或者两棱对换。这个问题一直都是默认的，没有证明，我就来证明一下。

首先我来引进高等代数中的几个定义与定理。

定义 1 由1，2，…，n组成的一个有序数组称为一个n级排列。

例如，2431是一个四级排列，45321是一个5级排列。

显然12…n也是一个n级排列，这个排列具有自然顺序，就是按递增的顺序排起来的；其他的排列都或多或少地破坏自然顺序。

定义 2 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序，一个排列中逆序的总数就称为这个排列的逆序数。

例如2431中，21，43，41，31是逆序，2431的逆序数就是4。而45321的逆序数是9。

定义 3 逆序数为偶数的排列称为偶排列，逆序数为奇数的排列称为奇排列。

例如，2431是偶排列；45321是奇排列；12…n的逆序数是零，因之是偶排列。

把一个排列中某两个数的位置互换，而其余的数不动，就得到另一个排列。这样一个变换称为一个对换。例如，经过1，2对换，排列2431就变成了1432，排列2134就变成了1234。显然，如果连续施行两次相同的对换，那么排列就还原了。

关于排列的奇偶性，我们有下面的基本事实。

定理 1 对换改变排列的奇偶性。

这就是说，经过一次对换，奇排列变成偶排列，偶排列变成奇排列。

证明   先看一个特殊的情形，既对换的两个数在排列中是相邻的情形。排列

                   …jk…              （1）

经过j,k对换变成

                                     …kj…              （2）

这里“…”表示那些不动的数。显然，在排列（1）中如j,k与其他的数构成逆序，则在排列（2）中仍然构成逆序；如不构成逆序的则在（2）中也不构成逆序；不同的只是j,k的次序。如果j,k原来组成逆序，那么经过对换，逆序数就减少一个，如果j,k原来不组成逆序，那么经过对换，逆序数就增加一个。不论增加1还是减少1，排列的逆序数的奇偶性总是变了。因之，在这个特殊的情形，定理是对的。

再看一般的情形。设排列为

                …ji₁i₂…i_sk…                 （3）

经过j,k对换，排列（3）变成

                …ki₁i₂…i_sj…                 （4）

不难看出，这样一个对换可以通过一系列的相邻的数的对换来实现。从（3）出发，把k与is对换，再与is-1对换，也就是说，把k一位一位地向左移动，经过s+1次相邻位置的对换，排列（3）就变成

                …kji₁i₂…i_s…                 （5）

从（5）出发，再把j一位一位地向右移动，经过s次相邻位置的对换，排列（3）就变成排列（4），因之，j,k对换可以通过2s+1次相邻位置的对换来实现。2s+1是奇数。相邻位置的对换排列的奇偶性，显然奇数次这样的对换的最终结果还是改变奇偶性。

定理证毕。

回到魔方上面来，其实可以给每一块按一定的顺序编上号，按什么顺序并不重要。比如对复原的魔方就按自然顺序，顶层的优先从左到右，而后从上到下，再对中层也一样的方式编号，最后是下层，也用一样的方式编号。

这样就构成了一个排列：1 2 3 … 27。是自然的排列，是偶排列。

定理  魔方小块位置状态的排列的奇偶性不变。

下面只是用数学归纳法来证明排列为偶数的情况，奇排列的情况可以同理证明。

证明： 1．初始状态是偶排列

2．假设魔方转动n次，魔方小块位置状态的排列是偶排列

转动n+1次的时候，为了方便讨论及一般性，就随便取九个层中的一个层来讨论，并按自然顺序编为

a  b  c

d  e  f

g  h  i

        假如按顺时针来转动，结果就是

g  d  a

h  e  b

i  f  c

        这个变换可以分解为角块位置的3次对换加棱块位置的3次对换。一共是6次对换，是偶数次对换，不改变排列的奇偶性。

        逆时针的情况可以同理来证明。

    由上面的两步得，魔方小块位置状态的排列的奇偶性不变。

       

    有了上面的定理就可以解释开头提出的问题。因为对换会改变魔方小块位置状态的排列的奇偶性，是违背该定理的，是不成立的，自然实际转动中也不可能实现。

 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

帖子原创者:邱志红

联系方式
电话:13667278577

qq:357484743

Email:gongsui002@163.com

Biog:http://hi.baidu.com/魔方空间

权力声明
保留著作所有权力,限于非商业性使用,允许原文转载,但要注明作者

作者希望
若能为同好做出有益的参考,实为本人最大满足,希望我的论文终结除最优解法以外的所有困惑.
发行日期

完成日期:2006年11月6日
发表日期:2006年11月7日

[此贴子已经被作者于2006-11-16 15:59:37编辑过]

黑白子

四阶魔方的两棱对换又如何解释呢？

mokona

酱油党路过飘过啦！

黑白子

邱志红 发表于 2006-11-24 18:03
（Part4）  重新认识中心块。 上面一直都没有讨论中心块的色向问题，现在我来专门谈谈我的见解。 我觉 ...

绝妙的证明！精美的叙述，这是用文字叙述三阶魔方定理。

黑白子

N阶魔方角块状态的逆位总数是0，是否就是角块的色向和为0
N阶魔方棱块状态的逆位总数是0，是否就是棱块的色向和为0

Cielo

以前看了居然都没有顶，惭愧！

邱志红

对

10 11 12/1 2 3/4 5 6/7 8 9/13 14 15/16 17 18/19 20 21/22 23 24

各部逆位数都为0，和自然为0。 

不引用三进制也可以，但定理中“为0”就要改为“为3的整数倍”。

意思一样，但“为0”方便些，也好与一般认为的色向和“为0”表达起来相一致。

rongduo

引用14楼——

“很容易就发现上面顶层转动90度之后的排列

10 11 12/1 2 3/4 5 6/7 8 9/13 14 15/16 17 18/19 20 21/22 23 24

的逆位数就是：0 ”

这里的逆位数0也是通过对三进制数的加运算后得来的，对吗？因为你在下文才提到了三进制。

邱志红

这里的排列说的数字的排列，而数字则是对各块的编号了。

所谓自然排列就是，数字按从小到大依次排列。1   2   3    4……   就是了。

——————————————————————————————————

那么，这4 1 2 3属于奇排列，对吗？（我还不大清楚为何1234是偶排列的话，4123就算奇排列，大概那“三次对换”就算改变奇偶性了。再说吧。一口吃不成胖子。）

那就看看第一部分（1楼），有详细的定义，是从书上抄的。奇排列，偶排列是由逆序决定的，逆序等这些定义1楼都有

[此贴子已经被作者于2006-11-24 21:59:32编辑过]

乌木

还不大懂。试试解读22楼，帮我看看对不对。
 您说“ k为偶数的时候也可以同理证明。”  好，试试：
1.初始状态三簇都是自然的排列，都属于偶排列。
2.假设魔方转动k次，三阶魔方三簇位置状态的排列满足该定理。暂设k为偶数，则三簇位置状态的排列都为偶排列。
转动k+1次时，某一表层四角，四棱，中心四小块各自进行一次四轮换（顺时针或逆时针），等价为各簇进行了3次对换。则三簇位置状态的排列同时都变为奇排列。满足定理。
…………

这三处蓝色字改得没错吧？下面继续解读：

您说“1.初始状态三簇都是自然的排列，都属于偶排列。” 好，我就把通常所说的的六面复原态作为初始态，它是偶排列的。对吗？
取k＝0，做第k+1＝1转－－U 后，原来四个角1 2 3 4次序（读者自定一下即可）变为4 1 2 3。
好，这4123经过1次“4和1对换”变为1423，第2次对换2和4，次序变为1243，第3次对换4和3，次序就是1234。可见，上面说，做第k+1转后，确实等价于（角块）进行了3次对换。
那么，这4 1 2 3属于奇排列，对吗？（我还不大清楚为何1234是偶排列的话，4123就算奇排列，大概那“三次对换”就算改变奇偶性了。再说吧。一口吃不成胖子。）
对棱块和中心块来说，类推。

最后问一下：您说“初始状态三簇都是自然的排列，都属于偶排列。” 那么， 任何合法态（包括扰动态和非扰动态）都是“自然的排列”吗？它们就没有奇排列吗？或许您是假设它们都属于偶排列？也或许您是选取它们之中的偶排列？

[此贴子已经被作者于2006-11-24 21:02:52编辑过]