三轮换的故事之三

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

魔鱼儿

楼主一天发好几贴哦,太专业,还是看不明白?

知Shmily足

LZ还真是能写啊！佩服！

乌木

楼主写得专业一些也罢，对我们这样非专业人士还希望你再多作些解释和举例为盼。

乌木

1楼说：“由于周期的存在，对于每个变换t，必然存在另一个变换t'能把t造成的影响复原。”我想，一般而言，一个变化的事物，其状态无论有无周期性，只要有关的变换是可逆的，那么，当状态变换到任一态时，总是有相应的逆变换可以复原。所以，你的叙述中那“由于周期的存在”是否应该删去，而应该加进“魔方的任何变换都是可逆的”之类的叙述？

pengw

你跟这个好大喜功、魔方无知、术语成嗜、纸上谈兵的家伙说得清楚吗？哈哈哈

[ 本帖最后由 pengw 于 2008-8-19 23:24 编辑 ]

乌木

<P>1楼：“对于两个变换t1和t2，如果存在一个变换t3满足t1=(t3)(t2)(t3')，那么t1的相关位置上的节点在t3下将全部移动到<FONT color=red>t1</FONT>的相关位置上……”</P>
<P>&nbsp;</P>
<P>似乎最后那红色的t1应为t2吧？当然，在继续经过变换t2和t3'之后，t1的相关位置上的节点又全都回到t1的相关位置上的。</P>

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

pengw

三轮换的故事讲了三个章节，是不是还要另起一回？我怎么看别人用二个四轮换就说明白了，楼主是真能演义还是不懂乱说啊？

乌木

<P>1楼：“一般来说，给定节点和位置后，可以存在很多变换，但我们要选择其中一部分作为基本动作。”</P>
<P>&nbsp;</P>
<P>我认为，对于给定的一种类型的魔方，其基本动作是确定的，不容我们选择的吧？倒是或许得说明一下何为基本动作。否则，有些动作看起来蛮“基本”，其实属于无效动作，比如有的类型的魔方做了该动作之后，无法接续做别的应该做的动作了，这就应该把它排除在基本动作之外。</P>

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