三轮换的故事之三

earthengine

<br>这是一个被放逐的系列文章，前两篇在这里：<br>
<br>http://bbs.mf8-china.com/viewthread.php?tid=12795<br>
<br>http://bbs.mf8-china.com/viewthread.php?tid=12813<br>
<br>之前我为了照顾该版面某些人士的智商，放弃采用数学的精确描述方式，改用故事的方式来叙述，希望能讲得浅显一些。结果反被认为是童话。现在，我将直奔主题。<br>
<br>http://bbs.mf8-china.com/viewthread.php?tid=12745 这里有一些相关的定义，有些不是很数学，这也是为了照顾那个版的朋友们。现在我不再有这方面的顾虑，所以让我重新定义一次。<br>

<br>广义魔方：它包括一些节点，一些位置，以及允许的基本动作。它有一种以上的状态，在每个状态下，每个节点占据一个位置，但不会有两个节点占据同一位置，也不会有一些位置空着。将给定的开始状态下一些位置上的节点移动到别的位置，从而形成新的状态的一套规则称为变换。一般来说，给定节点和位置后，可以存在很多变换，但我们要选择其中一部分作为基本动作。<br>
<br>
一个公式是基本动作的序列，又可称为派生动作。如果两个公式总是把同样的开始状态变为同样的结束状态，则这两个公式叫做全等公式，换句话说，全等的公式对应于同样的变换。公式这一概念我们将尽量少用，仅在讨论一些形式问题例如公式长度的时候，才使用公式，一般情况下我们用变换。但是记住，如果没有标明，这里的变换都是指合法变换，或者对应于公式的变换。一个变换能影响0个或多个位置上的节点，这些位置称为变换的相关位置。<br>

<br>
由于节点数目有限，因此状态数目有限。从而任何变换重复若干遍之后必然回到之前出现过的状态，最小的这个遍数叫做周期。由于周期的存在，对于每个变换t，必然存在另一个变换t'能把t造成的影响复原。这个t'叫做t的逆。下文我们就用加撇号表示逆。<br>

<br>
对于两个变换t1和t2，如果存在一个变换t3满足t1=(t3)(t2)(t3')，那么t1的相关位置上的节点在t3下将全部移动到t2的相关位置上，同时t1和t2的内部构造也是相同的（这一点要展开的话受篇幅所限，但相信各位魔友明白我的意思是指里面包括的轮换数目和次数必须对应相等，等等）
<br>
如果两个变换有部分相关位置重叠，那么两个变换相交，否则平行。重叠的位置叫做交点。如果交点只有一个，那么两个变换相切。这一概念的重要性我们很快就能看到。
<br>
如果存在一个变换能把一个位置上的节点移动到另一个，则这两个位置是同类的。所有同类位置叫做族。把同族的变换独立出来看成一个广义魔方，有时候很有用。在后面讨论自由度时，我们用的都是魔方，但这些概念也同样适用于一个魔方内部的族。这时我们会用族内自由度等说法，后不赘。<br>

<br>在之前的两篇故事中，我们主要的目的是证明了一个重要定理：
<br><blockquote>如果两个变换t1和t2在结构上除了一个位置不同以外完全相同，那么(t1)(t2')是一个三轮换。</blockquote>
正如我在第二篇故事结尾提到的，这个定理应用上比较难。因为已知t1时要找这么个t2不是很容易。现在我们要简化这个t2的寻找。我们要证明
<blockquote>如果两个变换t1和t2相切，那么(t2)(t1)(t2')(t1)是一个三轮换。</blockquote>
证明很简单，因为t2和t1相切，那么他们的相关位置上只有一个交点。(t2)(t1)(t2')是(t1)的相似公式，那么这个交点上的位置必然被t1移到了别的什么地方，但其它部分应该完全和t1相同。这么一来(t2)(t1)(t2')和t1就符合了第二篇故事里要证明的定理。<br>

<br>之前的文章里，我把这个定理也当作引理介绍。但其实它是一个威力强大的定理，能得出无数的推论，用于魔方的那个“定理”只是它微不足道的一个推论而已。所以，我将把对于魔方的应用放在最后介绍，到那时候因为我们手上已经拥有更强的终极定理，将能得出更强的结论。<br>

<br>对于三轮换的存在性，一般来说相切定理已经足够强大。例如，它能让我们推论出，当把3阶魔方基本动作限制为L,U时，棱块仍然存在三轮换。不要想当然以为这是必然的，因为对于角块这是不成立的。<br>
<br>然而我们不仅希望能证明三轮换存在，还希望能证明它是自由的——也就是说，同一族中任意三个位置，都存在三轮换。为了证明这个，我们要引入自由度的概念。<br>
<br>一个广义魔方是自由的，意味着把它任意节点移到任何一个位置的变换都存在。一般来说魔方不是自由的。例如，我们不能把角块移到棱块的位置上。但是2阶魔方是自由的，即使我们讨论的节点不是块而是色片（每个角块有3片，共24片）。<br>
<br>有时候，光是自由还不足够，我们还得看有多少自由。一个广义魔方有大于1的自由度，意味着我们可以设想把一个节点固定住，剩余的节点仍然是自由的。2阶魔方的自由度显然大于1，但是要是我们讨论的是色片而不是块，那么它的自由度就不能大于1。因为当固定住一个节点时，我们同时固定了同一个角上的另外2个节点（它们现在被固定住了。即使我们允许做镜像操作，它们也只能有２个不同位置）。这时候我们说它的自由度正好是1。<br>
<br>我们还可以定义大于2的自由度，等等。一个例子是，仅允许LU操作时，魔方可移动的角块部分有自由度3，(而魔方的“整体翻滚”动作有自由度2。——其实这是错误的，看出来了吗？自由度为1)，另一个例子是如果把2阶魔方的“偶整体翻滚”（可以绕轴转动90度，但必须进行偶数次）把角块分成两个族，每个族有自由度2。<br>
<br>关于自由度，一个显而易见的定理是<br>
<blockquote>如果广义魔方有n个节点，且存在自由对调（任何两个节点可以对调），则自由度为n。反之亦然。这时候，这个魔方是自由变换的：任何变换都是合法变换。</blockquote>
<blockquote>如果广义魔方有n个节点，且存在自由三轮换但不存在对调，则自由度为n-2，反之亦然。这时候魔方是自由偶变换的：一切偶变换都合法。</blockquote>
注意第一个命题的自由度不是n-1！因为当剩下最后一个节点时尽管它动不了，但剩下的位置也只有一个，所以这个节点还是自由的。满足以上两种情形的魔方很重要，因为它们的性态比较容易研究。<br>
<br>当把自由度概念推广到族而不是整个魔方时，根据族的定义每个族显然都至少有1的自由度。所以，说一个族是自由的，我们的意思是指它有大于1的自由度。另外，我们可以证明，自由度与具体选定的节点无关，只要是同族的节点，都是平等的。
<br><br>
下面我们来探讨自由度和三轮换的关系。有人以为，只要存在三轮换，就能自由三轮换，因为有相似公式可以把它变过去。但这是不正确的。设想我们有两个2阶魔方（显然存在三轮换），且它们的对调也是合法动作。那么这里显然不存在跨越2个魔方的三轮换。
<br><br>
问题在于这种情况下自由度只有1，所以即使有三轮换它也不能自由。那么能自由三轮换的条件是什么呢？显然，要是自由度大于2，那么我们可以随意安排3个节点的位置了，当然这时候它就自由了。但是我们还有更强的结果：
<blockquote>如果自由族上存在三轮换，那么该族上是自由偶变换的。</blockquote>
这就是说，族的自由度大于1就可以了。证明是这样的：
<br>既然存在一个三轮换，那么在族的每个节点上都存在三轮换。选定节点a，设找到的三轮换为[abc]，也就是a移动到节点b所在位置，b到c，然后c回到a。我们再任意选定一个节点d（要是节点都用完了，那么[abc]和它的逆[acb]就是可能存在的所有三轮换），由于自由度大于1，将必然存在一个变换f能把d变到b的位置。这时候，f'[abc]f=[adc]。现在我们再任意选定节点e，同理可以得到[aec]这个三轮换和它的逆[ace]。于是[adc][ace]=[ade]，由于a/d/e三个节点都是任意选定的，那么自由三轮换就成立。我们忽略的情况是选择e的时候可能节点已经用完了，我们可以选到b或者c。这种情况可以例外处理。读者可以自己试一下。（如果不熟悉以上用到的表达方式，我会另贴阐述。）<br>
<br>
<br>终极定理出台的时刻到了。先表述这个定理：
<blockquote>若存在两个变换相切于一个自由族的位置上，则该族是偶变换自由的。</blockquote>
用相切定理和自由三轮换定理很容易证明。要注意它的逆定理在该族少于5个节点时不一定成立，但要是有5个节点以上则偶变换自由蕴含存在两个相切的三轮换，因此逆定理成立。<br><br>关于自由度，有一些比较困难的问题！想证明自由度大于n很多时候比较容易，但想证明恰等于n就比较难了。作为例子，前面提到LU魔方自由度为３。要想证明的话就不那么容易了。此外，２阶LUF魔方是偶变换自由的。<br>

[ 本帖最后由 earthengine 于 2008-8-22 17:31 编辑 ]

xiaoshudian

太专业,还是看不明白?

乌木

嗯…………………………

earthengine

原帖由 <i>乌木</i> 于 2008-8-24 12:08 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=221924&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
魔方的转层动作实实在在是双向的，因而任何两态之间的任一条变换路线都是双向的，不是我的假设。
&nbsp;
目前的魔方转轴没有“棘轮”，以后实现了的话，也只是用LLL代替L' 而已，不会改变魔方变化规律吧？也不会改 ...

<br>变化规律没有变化，但是最小步长的计算会发生很大变化。<br>

乌木

<P>魔方的转层动作实实在在是双向的，因而任何两态之间的任一条变换路线都是双向的，不是我的假设。</P>
<P>&nbsp;</P>
<P>目前的魔方转轴没有“棘轮”，以后实现了的话，也只是用LLL代替L' 而已，不会改变魔方变化规律吧？也不会改变态态变换路线的双向性吧？</P>

[ 本帖最后由 乌木 于 2008-8-24 14:40 编辑 ]

smok

三置换的故事就这么动听,记得有一个儿童故事,讲述蚂蚁从粮仓偷米的故事,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,一只进去,一只出来,循环了8.3*10^22次,写满足了二个图书馆,楼主明白吗?

earthengine

原帖由 <i>乌木</i> 于 2008-8-23 16:18 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=221237&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
所谓逆步骤，在具体执行的时候，和“前进”没区别，好像上海到北京是“朝前”开车的，北京回上海也是“朝前”开车的。逆不逆的，还是要看初终态，中间过程的变化一一对应起来是效果相反的，则两个步骤串互逆。另一种 ...

<br>对。但你这是假设线路都是双向的。不过实际中，有些地铁轨道是环线，都是单向的，所以你不一定能走回头路。但是如果线路都可以循环，那么你可以从一个站到另一个站，也就一定可以从那个站回来。这就是逆的存在性。<br><br>你可以參考我在另一个帖子<a href="http://bbs.mf8-china.com/viewthread.php?tid=12958">http://bbs.mf8-china.com/viewthread.php?tid=12958</a> 里面对你的回复，有时候即使可以回头，但两者的代价不一定相同。在那里我举了魔方投币游戏的例子，你完全可以规定L‘要4个币才能转，而L只要一个。于是这是所有理智的游戏者都会选择用LLL代替L'。<br>

[ 本帖最后由 earthengine 于 2008-8-24 11:22 编辑 ]

乌木

所谓逆步骤，在具体执行的时候，和“前进”没区别，好像上海到北京是“朝前”开车的，北京回上海也是“朝前”开车的。逆不逆的，还是要看初终态，中间过程的变化一一对应起来是效果相反的，则两个步骤串互逆。另一种回到初态的机理就不同了，是因循环变化而达到复原。

乌木

<P>不知楼主是否此意，这里也不必管了。好像大家已经有个不成文的约定，t' 表示t的逆步骤，这也不去管它。你的说法蛮有意思。可是我有两个问题：</P>
<P>&nbsp;</P>
<P>1、何必非把巨大的循环公式前一半后一半地等分呢？哪怕（比如）把绝大部分看作t，把最后几步，甚至最后一步看作t'，照样也属于“把t所造成的打乱状态复原”。或者，那大循环公式的第二步（连一遍公式都还没有做完！）开始就可以算作恢复第一步所造成的打乱态－－一种很大很大的“曲线救国”嘛。对吗？</P>
<P>&nbsp;</P>
<P>2、“巨大循环公式”的后一半决不是前一半的逆步骤！一个公式重复若干遍之所以能复原魔方，不是靠什么半途而退，而是靠魔方状态变化的循环性质，坚持<FONT color=red>前进</FONT>，从而达到“柳暗花明又一村”，但不过是兜了一大圈之后的“同一村”。</P>

[ 本帖最后由 乌木 于 2008-8-23 10:10 编辑 ]

rubik-fan

你误解了搂主的意思。我猜想你理解的意思是：魔方任何变换公式t，都可以找到一个t‘，可以复原t所造成的打乱状态，那么最起码，可以让t’是t的逆。所以没有必要说“由于周期的存在”。而搂主之所以说“由于周期的存在”是这个意思：任何一个变换公式t，都是一个巨大的循环公式的前半部分，这个循环公式的后半部分就是t‘。t'之所以能把t所造成的打乱状态复原，是因为两者加在一起刚好是一个周期。乌木先生，你说呢？