三轮换的故事之三

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 编辑 ]

earthengine

原帖由 <i>乌木</i> 于 2008-8-19 23:19 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=218109&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
1楼说：“由于周期的存在，对于每个变换t，必然存在另一个变换t'能把t造成的影响复原。”我想，一般而言，一个变化的事物，其状态无论有无周期性，只要有关的变换是可逆的，那么，当状态变换到任一态时，总是有相应的 ...

<br><br>
不可以。因为我们的变换仅包括“合法变换”也就是等价于公式的变换。因此逆变换虽然总是存在，但是它的合法性需要证明。

earthengine

原帖由 <i>ocp</i> 于 2008-8-20 08:02 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=218198&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
初态:1234
f1=312
f2=412
&nbsp;
f1:3124
f2:4321
&nbsp;
终态：二个二元环（41）（32），这是三置换吗？

<br>双二元环不是三轮换。注意我用的术语是三轮换，它表示仅有三个相关位置的变换。<br>

earthengine

原帖由 <i>乌木</i> 于 2008-8-19 23:35 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=218135&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
1楼：“一般来说，给定节点和位置后，可以存在很多变换，但我们要选择其中一部分作为基本动作。”
&nbsp;
我认为，对于给定的一种类型的魔方，其基本动作是确定的，不容我们选择的吧？倒是或许得说明一下何为基本动 ...

<br><br>基本动作是可以随意选择的。因为动作代表变换，而变换定义了从<span style="color: Red;">任意</span><br>状态进行变化的规则。因此两个变换总是可以叠加。比如说，把魔方的棱块3置换看成基本操作，也是可以的。当然这可能最后得出不同的魔方。

earthengine

原帖由 <i>乌木</i> 于 2008-8-20 10:34 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=218394&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
1楼说：“当把3阶魔方基本动作限制为L,U时，棱块仍然存在三轮换。不要想当然以为这是必然的，因为对于角块这是不成立的。”
&nbsp;
如果按照你说的“对于角块这是不成立的”，那么另一帖（<a href="http://bbs.mf8-china.com/v" target="_blank">http://bbs.mf8-china.com/v</a> ...

注意我说的三轮换是独立三轮换。角块在这种情况必然存在另一个三轮换。这叫双三轮换，跟三轮换是两回事。
<br>120是正确的答案。因为LU魔方的角块自由度为3，我们固定2个角块的位置有6*5=30种方法，然后剩余的节点只能四轮换，有4种变换，因此总共30*4=120种状态。<br>（我发不了帖子了，在这里回答乌木）<br>

原帖由 <i>乌木</i> 于 2008-8-20 11:06 发表 <a href="redirect.php?goto=findpost&amp;pid=218464&amp;ptid=12822" target="_blank"><img src="images/common/back.gif" alt="" border="0"></a>

&nbsp;
我很难理解一个正确魔方中有“存在而不合法”。
&nbsp;
一个步步都是可逆动作的变换，沿原路做逆动作返回，难道非要拉进周期不周期的前提吗？

<br>但是如果我没有定义逆动作也是基本动作呢？在魔方里，我完全可以定义L为基本动作，而L'=LLL为派生动作。比如，在魔方上装棘轮，使它只能朝一个方向转动。<br>

原帖由 <i>乌木</i> 于 2008-8-20 11:46 发表 <a href="redirect.php?goto=findpost&amp;pid=218522&amp;ptid=12822" target="_blank"><img src="images/common/back.gif" alt="" border="0"></a>

&nbsp;
难道一个立方体三阶魔方的基本动作不是UU'DD'RR'LL'FF'BB'吗？莫非你还要从中“随意选取”什么东西吗？

<br>这可不一定。魔方特殊转法的研究是非常重要的。例如U2D2R2L2F2B2构成了魔方状态空间一个非常有意思的子集。这是数学家最初论证步长上限时所用到的。还有之前提到的LU子集也是选取出来的。关于周期性的讨论只是说明了，无论你选择基本动作的时候，有没有遗漏其中互逆的动作，结果都不会有所不同。这难道不是一个有意义的结果吗？选择三轮换作为基本动作当然是可以的。众多可能的三轮换（甚至所有的变换）都一律平等，没有哪个比哪个更基本的问题（也许有点过火，至少0变换——什么都不变就不和其它变换平等）。基本动作集是可以任意选定的，但当我们讨论特定结构的魔方时，有时候采用某一些比另一些更方便，如此而已。<br>

原帖由 <i>乌木</i> 于 2008-8-20 11:29 发表 <a href="redirect.php?goto=findpost&amp;pid=218500&amp;ptid=12822" target="_blank"><img src="images/common/back.gif" alt="" border="0"></a>

&nbsp;
嗯，这“独立三轮换”算是你在补漏洞吧。
&nbsp;
不过，我手边就做成了“RU魔方”的角块单一三轮换－－但是我得坦白，1、为了选取我要的两个角块置于1、2号位，我不得不违反只转RU的限制；2、虽然另三个 ...

<br>声明：这可不是补漏洞而是我们的理解不同。你要是违反了限制，得不到结果也就是必然的。提示一下如何定位两个任意角块：注意应用L的相似变换ULU'。<br>

[ 本帖最后由 earthengine 于 2008-8-20 12:25 编辑 ]

earthengine

原帖由 <i>ocp</i> 于 2008-8-20 08:02 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=218198&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
初态:1234
f1=312
f2=412
&nbsp;
f1:3124
f2:4321
&nbsp;
终态：二个二元环（41）（32），这是三置换吗？

<br>可能我这里写错了，检查一下。<br>
<br>检查结果是没有错。我文中并没有断定任意两个三轮换的复合是三轮换。但是如果两个三轮换的复合不是三轮换，那么把其中一个取逆后和另一个三轮换复合必然是三轮换。按照你的例子f1=[123]，f2=[124]，(f1)(f2)=[123][124]=[14][23]，(f1)(f2')=[123][142]=[234]，(f1')(f2)=[132][124]=[134]，有问题吗？

[ 本帖最后由 earthengine 于 2008-8-20 14:42 编辑 ]

earthengine

原帖由 <i>乌木</i> 于 2008-8-20 20:14 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=219073&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a> 你这自由色片的二阶魔方也变成类似Puzzler中另一种玩法的魔方－－色片推移一般的游戏了。我手中一个二阶魔方的色片可是“死的”，8个角块再怎么自
由，也得同一角块上的三个确定的色片一起移动、一起取色向的。对面色色片永远“自由”不到同一个角块上去。同一角块上的三个色片之间的相对布排关系永无“
自由”。

<br>这个不能得出“角块、棱块无区别”的结论。其实这个魔方和正常带有色向的魔方具有同样的状态数。那些角块棱块虽然不是节点，却是节点的连锁组：它们总是一起变化。为什么呢？这是被选定的基本动作限定死了的，如果每个基本动作都不能拆散它们，那么任何派生动作都不能够。在这种情况下二阶魔方的一个转动是3个4轮换，而不是1个。3阶中心块无向时是20个4轮换，有向是21个。<br>

earthengine

原帖由 <i>乌木</i> 于 2008-8-20 21:02 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=219100&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
那么，二阶的四个红色色片要有区别标记，四个白色色片也要区别，…………，对吗？
&nbsp;
还有，三阶中心块无色向时，魔方表层一次转动，角块、棱块的20个色片只会发生5个四轮换（角块的一个四轮换改为角块色片的3 ...

<br>你是对的，中心块无色向是5个4轮换，有色向6个。此时要把中央块切成4个小块，于是就有了4轮换。我昨天写得匆忙。<br>

earthengine

原帖由 <i>乌木</i> 于 2008-8-21 21:24 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=219365&amp;ptid=12822" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
先把色片分开考虑，后又把几个色片弄成“连锁组”，有何必要或有何奥妙？

<br>连锁组不是<span style="color: Magenta;">规定</span>的，是根据我们选取的规则，自行产生的。如果把基本动作看成是公理，那么连锁组是由它推出的定理。目的只有一个：让我们的置换理论可以应用。因为目前理论中的节点没有状态，为了加入状态，我们增加更多的节点。并且，在选取基本动作的时候，注意使它们能连锁变化，如此而已。<br>

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 编辑 ]