几个根基东西的证明

邱志红 发表于 2006-11-7 10:49:36

（这是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，排列的逆序数的奇偶性总是变了。因之，在这个特殊的情形，定理是对的。再看一般的情形。设排列为                …ji1i2…isk…                 （3）经过j,k对换，排列（3）变成                …ki1i2…isj…                 （4）不难看出，这样一个对换可以通过一系列的相邻的数的对换来实现。从（3）出发，把k与is对换，再与is-1对换，也就是说，把k一位一位地向左移动，经过s+1次相邻位置的对换，排列（3）就变成                …kji1i2…is…                 （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  ah  e  bi  f  c        这个变换可以分解为角块位置的3次对换加棱块位置的3次对换。一共是6次对换，是偶数次对换，不改变排列的奇偶性。        逆时针的情况可以同理来证明。    由上面的两步得，魔方小块位置状态的排列的奇偶性不变。            有了上面的定理就可以解释开头提出的问题。因为对换会改变魔方小块位置状态的排列的奇偶性，是违背该定理的，是不成立的，自然实际转动中也不可能实现。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~帖子原创者:邱志红联系方式 电话:13667278577qq:357484743Email:gongsui002@163.comBiog:http://hi.baidu.com/魔方空间 权力声明 保留著作所有权力,限于非商业性使用,允许原文转载,但要注明作者 作者希望 若能为同好做出有益的参考,实为本人最大满足,希望我的论文终结除最优解法以外的所有困惑. 发行日期完成日期:2006年11月6日 发表日期:2006年11月7日
[此贴子已经被作者于2006-11-16 15:59:37编辑过]

邱志红 发表于 2006-11-7 10:56:20

还有三交换一直是被默认为是魔方的最基本的变化，其实不然，对换才是最基本的，三交换其实就是两对换的结果，是满足上面定理的。而所谓的扰动现象也可以很容易用上面的定理解释。发生扰动的时候，棱块进行了奇数次对换，角块进行了奇数，合起来是偶数次，满足上面定理。这还是不能解释为什么表层转动奇数次不能通过偶数次还原。这就要灵活运用上面定理的证明方法及思路了，上面的定理是针对对魔方小块整体位置状态的排列而言的。现在单就角块这一簇来讨论，棱块这一簇同理。初始复原态的排列就是偶排列了，转动一次就等价于三次对换，转动奇数次就等价于该转动次数三倍的对换，最终还是奇数次对换。得到的是奇排列，改变了排列的奇偶性。而转动偶数次就等价于该转动次数两倍的对换，最终还是偶数次对换。不改变排列的奇偶性。所以表层转动奇数次不能通过偶数次还原。这讨论的都是三阶魔方，二阶魔方的情况可以用同样的方法分析。它的块可以两对换也可以很容易解释。奇数次转动就可以达到。 五魔方也一样，五魔方转动一次等价与四次对换，是不改变魔方小块位置状态的排列的奇偶性的。所以五魔方怎么转动都不会出现三阶魔方中的扰动现象。其他任何魔方都可以把小块编上数字，然后用排列及其分析方法来分析。这都是魔方小块位置的问题，色向的问题我正在思考中……

smok 发表于 2006-11-7 11:25:21

对N阶色子阵魔方，PENGW好像说过，四轮换是最基本变换，而对换和三交换是四轮换复合使用的结果，严格地讲，二二对换和三交换是四轮换偶次使用的结果，单一对换（或单一偶环）是该簇四轮换奇次使用的结果。如果将三阶角块看成一列有序数，角块的变换是通过对这一列有序数上特定位置的角块（本质上是由结构决定的）实施结构决定的轮换来体现，这是本质。关键问题是，真接变换（四轮换）是由结构决定，而非随意可行。其它一切变换（包括三交换和对换）都是真接变换复合使用的结果。最小步的本质，就是状态变换中使用最少的直接变换扰动的本质，是多个簇被迫同时参与直接变换造成的一种现象，对二阶而言，块的位置可以随意指定而不违法，因为二阶不会强迫其它簇共同变换。最复杂的变换应属N阶色子阵魔方，其结构和变换没有明确的“方向和个性”，而其它异型多少带有一定的导航“路标”和“个性”。
[此贴子已经被作者于2006-11-7 11:46:00编辑过]

邱志红 发表于 2006-11-7 11:55:01

扰动的本质，是多个簇被迫同时参与直接变换造成的一种现象我的证明或多或少解释了这种“被迫”，而同时也解释了五魔方的角块与棱块之间又为什么“不被迫”。这样大家对魔方就会有一个统一的新认识，而不是对不同类型的魔方都特殊处理，喊出特殊性质之类的话来。

smok 发表于 2006-11-7 11:59:32

个性是由结构决定的，位子轮换和色向变换（当然不是所有类型都有色向）是共性，所以本质上是相同的，我的理解仍然是，真接变换才是最基本的变换，再说深一点，扰动就是描述那些簇可以同时保持奇数次真接变换
[此贴子已经被作者于2006-11-7 12:02:46编辑过]

邱志红 发表于 2006-11-7 13:06:29

赞同，再严密的数学推导都是建立在实物结构之上的。结构决定性质，而数学方法的运用往往能解释结构怎样决定性质的，但不能左右实物的性质。这是我的理解大家有时候认识到魔方的一个性质的时候，不妨也考虑下结构是怎样决定性质的，而不是一句“结构决定性质”搪塞过去。另外位子轮换的确是魔方最基本的，而我用的数学方法把最简单的对换作为最基本的，是为了中间分析过程的方便。最后“输出”，也就是运用到实物上则更多的是三交换，轮换等。说到底，总的模式是：实物→数学模型→实物，解决实际问题才是目的。
[此贴子已经被作者于2006-11-7 13:08:13编辑过]

pengw 发表于 2006-11-7 17:10:17

极为辩证，非常欣赏。我有一个建议，用小邱在数方面的优势，建立单簇层面的数学变换模型，如果能够从中获得求取簇最小步数的一般性方法，则利用我的“基于N阶定律的最小步数分析”中构建的方法，可以较为现实的计算出三阶的最小步数/最远状态，由此可以免受一些颠三倒四的谬论搔扰，如何？哈哈哈

jinyou 发表于 2006-11-8 09:17:04

<div class="msgheader">QUOTE:</div><div class="msgborder">以下是引用邱志红在2006-11-7 10:49:36的发言： 定理  魔方小块位置状态的排列的奇偶性不变。</div>前段时候，我们就是讨论这方面的问题，现在得到证明，太好了。

邱志红 发表于 2006-11-8 11:25:31

<div class="quote" twffan="done">以下是引用邱志红在2006-11-7 13:06:29的发言： 赞同，再严密的数学推导都是建立在实物结构之上的。结构决定性质，而数学方法的运用往往能解释结构怎样决定性质的，但不能左右实物的性质。这是我的理解 </div>关于这一点有一个很好的例子。假如你不考虑魔方的结构，而单纯去抠定理 魔方小块位置状态的排列的奇偶性不变。是会闹笑话的。 这个定理只是魔方状态的个必要条件不是充分条件。也就是说任何合法状态的魔方必须满足这一条，连这个必要条件都不满足的状态就当然不可能存在。但反过来满足这一条的不一定都是合法状态。 比如，中心块三交换满足该定理，但其实那是不可能的。究其原因在于魔方的结构。  魔方的实际结构限定了中间层转动时各中心块的交换形式。看下图：  我也不硬说6个中心块是固定在中心上的，相对位置是不变的，但最起码相对的两个中心块是固定在一条直线上，绕中点旋转。也就是说一个中心块就决定了相对的那个中心块。也就是说6个中心块是由其中某3个中心块决定的，于是在转化为排列的时候就可以记为（1 2）（3 4）（5 6）。比如 1  2  3  4所在层转动90度后，排列变为（3 4）（2 1）（56）。即使继续转下去，（1 2），（3 4），（5 6）各对都是不分家的。如果要实现三交换，就必定要拆散某一对，这是与各对不分家是相悖的，不能成立的。中心块的交换只能成对地进行。所以还是印证了结构决定性质，而数学方法的运用往往能解释结构怎样决定性质的，但不能左右实物的性质。就像大自然的规律是既定的，人只能认识并利用大自然的规律而不改变大自然的规律一样。 其实往往为了研究的方便，可以固定六个中心块。另外除去中心块的特殊轮换，那个定理 魔方小块位置状态的排列的奇偶性不变 就是三阶魔方各块位置状态的充分必要条件了。 
[此贴子已经被作者于2006-11-8 11:26:11编辑过]

pengw 发表于 2006-11-8 20:50:17

论述的很好，数学与现实就是这种关系,数学层面的美如同音乐一般,但现实的呈现又使的数学的表达带上了约束条件,必竟数学是表达现实的一种工具,但又不完全仅仅只是一种工具,如同音乐可以表达思想,但绝非是仅仅用于表达思想.另我还注意到,仅仅用小邱的正方体色子阵模型堆彻的魔方(各层沿假想转轴转动)与现实魔方的性质是一样的,不受现实中的转轴影响.当前大家对一些经典魔方的状态描述已不是问题,公式循环的原理与极限及公式步数的奇偶性已被讨论很透彻了,完全足够指导操作与理解状态,使的一些经典问题:复原,花样设计,公式循环,状态数计算完全失去神秘色彩,我们这些老一辈玩家做到这些,已退而无憾了.并且,解决最小步数的方向与方法也已清晰呈现,余下的问题在技术层面,只有各类簇最小步数的一般性数学表达与求解,各种各样的昏论/迷宗/神喻基本失去存在的价值,我建议大家集中精力,将主攻方向放在最小步数问题的解决上,建议小邱率领大家,立用强大的数学手段,攻克最后一个堡垒.
[此贴子已经被作者于2006-11-8 21:07:15编辑过]

页: [1] 2 3

魔方吧·中文魔方俱乐部's Archiver

几个根基东西的证明