黄瓜西红柿减肥法:魔方组合原理
来源:百度文库 编辑:中财网 时间:2024/05/03 04:41:53
目录
前言 - 1 -
第一章 预备知识 - 2 -
(一) 魔方的结构 - 2 -
(二) 术语记号 - 2 -
(三) 程序、对称程序与逆程序 - 3 -
第二章 开解法 - 5 -
(一) 上边块 - 5 -
(二) 上角块 - 5 -
(三) 中边块 - 6 -
(四) 下角块 - 7 -
(五) 下边块 - 9 -
第三章 开解法证明(Ⅰ) - 11 -
(一) 上层和中层开解法的完备性 - 11 -
(二) 置换概念初步 - 11 -
(三) 下角块定位开解法的完备性 - 13 -
第四章 开解法证明(Ⅱ) - 15 -
(一) 跷跷板原理 - 15 -
(二) 扭转代数 - 16 -
(三) 下角块定向开解法的完备性 - 17 -
第五章 开解法证明(Ⅲ) - 20 -
(一) 翻转代数与下边块定向开解法的完备性 - 20 -
(二)置换代数 - 20 -
(三)下边块定位开解法的完备性 - 21 -
第六章 方块的空间状态暨魔方表示定理 - 23 -
(一) 方块的空间状态 - 23 -
(二) 魔方表示定理 - 25 -
第七章 几个重要的计数公式 - 27 -
(一) 轮换的计数公式 - 27 -
(二) 方块平均分组 - 28 -
(三) 平均分组下的置换计数公式 - 29 -
(四) 表达式※的推导 - 30 -
第八章 魔方组合计数 - 32 -
(一) 方块的方向组合数 - 32 -
(二) 角块的置换组合数 - 33 -
(三) 边块的置换组合数 - 34 -
(四) 魔方方块的总组合数 - 36 -
(五) 总组合数的另外两种计算法 - 36 -
【附 录】魔方角块方向问题的群论模型 - 38 -
修订后记 - 43 -
前言
关于魔方的书并不很多,我所见到的极为有限的几种,其主题都是魔方的玩法或开解法。至于魔方的组合原理,在这些书中或者只有只言片语,或者只是一种雾里赏花式的漫谈。不过它们都说:要真正理解魔方,必须懂得一门高深的数学,叫作什么“群论”(怪怪的名字!)。
本书则不然。首先,它以魔方的组合原理为主题,所给的开解法(虽然可能特别适合于初学者)只是主题开展过程中的一个环节;其次,它尽可能追求系统性和严密性,而不满足于漫谈;最后但也可能最重要的是,它不需要“群论”[注]!凡是学习过中学数学中排列组合知识的人,都可以完全地读懂本书的正文部分。
跷跷板原理构成了本书的主线和理论基础。或许正是因为有了跷跷板原理,才使我们得以绕开一些过于抽象的代数知识,对魔方方块那令人眩晕、烦心的组合作出了澄明透彻的解释与刻划。我希望,这一原理能使本书有别于其它所有同类的书。
我还真诚地希望,每一个魔方玩家和中学生都能够赏玩这本书。
最后补充说明两点:一是现在魔方种类很多,本书所讨论的仅限于由三层共26个小方块构成的那一种,即最原始的鲁毕克魔方( 详见本书第一章(一) );此外,对目前一些魔方玩家热心探究的魔方中心块的方向问题,本书按既定体例不予涉及。
魔方是由其六个平面中央的6个方块(称为中心块)、每三个平面交会所成角位置上的8个方块(称为角块)以及各平面边缘位置上的12个方块(称为边块)计26个方块组成(图1)。转动任意一个平面(90°,-90°,180°,360°等),该平面的中心块保持不变,而4个角块和4个边块则发生旋转移动。通过选取适当的平面进行转动,可以使一个角块取代任意另一个角块的位置,一个边块也可以取代任意另一个边块的位置;在这一过程中,每一方块上各面(为一些小正方形)的朝向也随之发生变化。要复原一个混乱的魔方,则必须注意到任何一个可转动方块只适合于一个位置。例如,白绿色边块(每个边块有两种颜色)只能适合白色和绿色平面之间的边缘位置。而一个平面的颜色,是由那个平面上固定的中心块的颜色来决定的。再如,同时染着红色、蓝色和白色的角块(每个角块有三种颜色),其位置应在交会红色、蓝色和白色三个平面的那个角上。一个方块被安放在它应在的那个位置,可以称为位置正确或已归位。当一个方块不但位置正确,而且它的各面的颜色分别和所在平面的中心块的颜色相一致时,我们便说它位向正确或已归位定向。如果因位置不正确而导致一个方块仅有一个面的方向正确,则称此方块对该面已定向。一个被打乱的魔方当其每一个可动方块都已归位定向时,魔方的开解即告完成。
1.约定魔方六个平面的名称如下:
上(U):上平面(任意选一种你喜爱的颜色)
下(D):下平面
前(F):前平面 后(B):后平面
左(L):左平面 右(R):右平面
以后我们将用上面括号中的字母去代替括号前面的字。上平面是在开解前任意选定的,选定后在整个开解过程中必须保持不变,从而下平面也将保持不变。前平面根据被打乱魔方的图案在四个竖直面中临时选定,而在开解中又常常需要改选新的前平面,所以它可以是四种颜色之一。每选定或改选一次前平面,左平面、右平面和后平面也就随之而定。
2.对各平面进行转动的记法是:
U+:把上平面按顺时针方向转动90°
U-:把上平面按逆时针方向转动90°
U2:把上平面转动180°
D+:把下平面按顺时针方向转动90°
D-:把下平面按逆时针方向转动90°
D2:把下平面转动180°
F+:把前平面按顺时针方向转动90°
F-:把前平面按逆时针方向转动90°
F2:把前平面转动180°
B+:把后平面按顺时针方向转动90°
B-:把后平面按逆时针方向转动90°
B2:把后平面转动180°
L+:把左平面按顺时针方向转动90°
L-:把左平面按逆时针方向转动90°
L2:把左平面转动180°
R+:把右平面按顺时针方向转动90°
R-:把右平面按逆时针方向转动90°
R2:把右平面转动180°
3.称现在位于右平面和前平面之间的一个边块为右前;称现在位于右平面、前平面和上平面之间顶角上的那个角块为右前上。以此类推,十二个位置上的边块分别称为:
前下、后下、左下、右下、
左前、右前、左后、右后、
左上、右上、前上、后上。
八个位置上的角块分别称为:
左前下、右前下、左后下、右后下、
左前上、右前上、左后上、右后上。
在本书中,任何转动及其所涉及的的方块一律用上述术语或记号表示。此外,要使用本书的开解法,你必须按一定方向持握魔方,使将要予以变动的方块与文中所述的情形相一致。例如,你希望安放一个后上角块,但说明中提供的是一组安放一个前上角块的转动,那么,你就必须整体转动魔方使所考虑的后上变为前上。其余可类推。
为节省时间,你可以跳过本节径直去阅读后边的第二章,等在第二章学会了基本的开解方法以后,如有必要,再回头阅读本节。以下是本节的内容。
1.本书中所说程序是指可以运用于魔方的一组预定的(而不是随意的)转动。某些程序可能只包含一个转动,但更多的程序则包含有多个转动。
2.对如下的转动程序:
P0 L+,R-,F-,D2
可以构造另一个程序:
R-,L+,F+,D2
我们把程序 称为P0的对称程序,其代号“ ” 可以读作“对称P0”。此时,又可以把P0称为原程序。一般地,对于一个原程序Pi ,把它所包含的每一个转动都换成一个与之对称的转动,我们就得到了它的对称程序 。求一个转动的对称转动的规则是:
前后上下面不变,左右面互变;
数字2不变,正负号互变。
比如,按照上述规则的第二句和第四句,我们可以确定L+的对称转动是R-;按照规则第一句和第三句,可以确定U2的对称转动还是U2。此外,我们还可以确定R2的对称转动是L2,D+的对称转动是D-,如此等等。
3.像每一个程序都有它的对称程序一样,对每一个程序Pi,我们还可以构造出它的逆程序 (读作“逆Pi”)。构造的方法是:先由Pi求出 ,再把 中所有转动的先后顺序倒过来重新排列,即把 中的倒数第一个转动现在排为第一个转动,倒数第二个转动排为第二个转动,如此继续下去,直到把 中的第二个转动排为倒数第二个转动、第一个转动排为倒数第一个转动为止。这样所得的新程序即为原程序Pi的逆程序 (注意: 并不是 的逆程序)。以前面所给的程序P0为例,其逆程序为:
D2,F+,L+,R-
逆程序是相对于原程序而言的。在对魔方运用了一个程序以后,再运用一次这个程序的逆程序,就可以使魔方恢复原状。如果把原程序比喻为“向前走去”,那么逆程序就相当于“按原路倒退着走回”。
开解法
从直观上看,魔方的全部方块可以按上、中、下分为三层。上平面的方块构成上层,前、后、左、右四个平面上的中心块以及四个中边块构成中层,下平面的方块构成下层。本章所给开解法的总思路是由上到下,逐层给各个可转动方块归位定向。这一过程又可以依次分为六个较小的环节:①上边块的归位定向;②上角块的归位定向;③中边块的归位定向;④下角块的归位;⑤下角块的定向;⑥下边块的归位定向。
应归位于上平面的四个边块总称上边块。上边块的归位定向在六环节中是最容易的。本节将要介绍的方法主要是面向初次接触魔方的读者。它比较呆板,但却能有效地预防某些常见的错误。读者不妨依据这些提示进行最初的演练,但在稍微熟练后就不必再去理会那一大堆谨小慎微的玩意儿——你尽可以灵活地去选择那些合目的的转动。
动手开解前,先任意确定一个平面为上平面。在上一章已经指出,上平面一旦确定,在以后的整个开解过程中是不宜变动的。
⒈选定一个竖直面为前平面,使前上部位并无已经归位而且定向的方块(你可能必须在手中整个地转动魔方才能做到这一点,这样,必然地会使前平面发生变换)。接下来,在魔方中寻找出应属于这个前上部位的边块.
⒉这个边块也许恰巧就在前上,只是未曾定向,请作如下转动:F+, U-, R+, U+。
⒊如果所寻的边块在下平面,可以适当转动(有时不需要转动)下平面,使该边块位于前下。这时进行观察(而不是立即转动),看是否可以将前平面转动180°而使这一边块既归位又定向。如果可以,那么转动180°以后问题就得到了解决。如果察知转动180°以后还不能定向,可改作如下的转动(注意,此时所论的那个边块还位于前下):F-, U-, R+, U+。
⒋如果所寻的边块在前平面的中层,观察(而不是立即转动)是否可以把前平面转动90°或-90°使这一边块归位而且定向。如果可以,则转动后问题得到解决。如果察知仅仅能归位而不能定向,则选做如下的转动。
① 所寻方块位于右前时:U-, R+, U+。
② 所寻方块位于左前时,使用上一程序的对称程序:U+, L-, U-。
⒌所寻的方块位于后平面的中层时,可以选用如下的程序将该边块移至前下。
①所寻方块在右后:R+, D-, R-。
②所寻方块在左后,运用上一程序的对称程序: L-, D+, L+。
然后返回步骤3。
⒍所寻的方块在上平面前上以外的位置上,可将其所在的竖直面(左平面、右平面、或后平面)转动180°,使该边块移至下平面,然后返回步骤3。
由于四个上边块是逐一归位定向的,因此可能需要反复运用以上的六个步骤,直到四个上边块全部归位定向。
本节的目的是使属于上平面的四个角块——上角块归位定向。在后面所给的一系列的转动中,已安放好的四个上边块可能会被被暂时移动,但最终都会自动还原。
1.选定一个竖直面为前平面,在这个前平面的右前上位置并无已经归位而且定向的方块。接下来,在魔方中寻找应属于右前上位置的角块。
2.如果所寻的角块位于下平面,可适当转动(有时不需转动)下平面,使该角块位于右前下(与右前上在同一竖直线上),并注意观察构成该角块的三个小正方形染着(“着”读zhuó)的三种颜色。
①该角块染着上平面颜色的那个小正方形位于前平面时(见图2①),请选用下列程序(二者任选其一)。
P1 (上角块归位定向程序) F+, D+, F-
P1’ D-, R-, D+, R+
[插图说明] i ) 为了方便,本书在举例时总是假定:上平面红色、前平面蓝色、左平面白色、右平面黄色、后平面绿色、下平面土黄色(图④显示了后平面和下平面)。应注意实际开解不一定是这样。 ii ) 图中的灰色表示不确定的颜色。
②如果所论的角块染着上平面颜色的那个小正方形位于右平面(见图2②),可运用如下的程序:
P2(上角块归位定向程序又) R-, D-, R+
③如果所论角块染着上平面颜色的那个面位于下平面(见图2③),运用如下的程序:
P3(上角块归位定向程序又) F+, L+, D2, L-, F-
3.如果属于右前上位置的那个角块已经归位,但方向不对,此时可运用程序“R-, D-, R+”将其移到下平面,然后返回2。
4.如果属于右前上位置的角块现在位于左前上,或右后上,或左后上,可按照提示适当选用下列程序将其移至下平面:
① 所论角块在左前上:L+, D+, L-
② 所论角块在右后上:R+, D-, R-
③ 所论角块在左后上:L-, D2, L+
然后返回2。
和上边块的情形一样,四个上角块也是逐一进行归位和定向的,因此可能需要反复运用上述1至4所提供的方案。
中边块是指应属于魔方中层的四个边块。开解前,未归位和定向的那些中边块可能位于魔方的下平面,也可能位于中层。开解时,须依循以下的方案逐块进行。
1.考虑位于魔方下平面的一个中边块的归位和定向,先观察该边块竖直面的颜色,然后适当转动(有时不需要转动)下平面,使得该竖直面位于颜色相同的那个中层中心块的正下方,并定这一中心块所在的平面为前平面。接下来,对准备归位定向的中心块(现在位于前下),按其位于下平面的那个小正方形的颜色,判定其应归位于右前还是左前。
2.如果所论的中边块应归位于右前(见图3①),请运用如下程序:
P4(中边块归位定向程序)D-, R-, D+, R+, F-, R+, F+, R- (8次转动)
如果所论中边块应归位于左前(见图3②),请运用P4的对称程序:
D+, L+, D-, L-, F+, L-, F-, L+
3.如果未曾归位、或已经归位但未定向的中边块位于魔方的中层,则无论是中层的哪一个位置,都可以通过适当选择前平面,使该边块现在的位置为右前,进而运用以下程序将它移至下平面:
P5(右前至下平面换位程序) F+, D-, F-, D-, R-, D+,R+ (7次转动)
然后返回1。
下角块自然指应位于下平面的四个角块。流行的开解顺序是先定位,后定向。这种顺序比较合理(但仍然存在着相反的顺序和一次性定位定向的程序,此类“高级开解”问题本书不予讨论),本节将依循这一顺序给出具体的开解方案。
(甲)定位
1.中层开解完毕后,适当转动(有时不需要转动)下平面,就可以使至少两个、甚至是四个下角块全部归位。
2.如果两个位置不对的下角块相邻,可令二者所在的竖直面为左平面,然后运用以下程序:
P6(下角块定位程序) R-, D+, L+, D-, R+, D+, L-, D2
3.如果两个位置不对的下角块不相邻(即处于下平面的一对对角上),可选任意一个竖直面为前平面,运用如下的程序:
P7(下角块定位程序又) F+, D+, L+, D-, L-, F-
然后适当转动(有时不需要转动)下平面,就可以使四个下角块全部归位。
(乙)定向
归位后四个下角块的方向或者完全正确,或者在下平面形成如图4(①—⑦)中的某一个图案。下文将给出两套开解方案,读者可任选其一。
第一方案——
1.观察魔方的下平面,适当整体转动(有时不需要转动)魔方,使下平面与图4中的某一个图案相吻合。
2.如果魔方的下平面如图案①,可运用如下的程序:
P8(下角块定向程序) R-, D-, R+, D-, R-, D2, R+, D2 (8次转动)
3.如果魔方的下平面如图案②,可运用P8的对称程序:
L+,D+, L-, D+, L+, D2, L-, D2
4.我们把图案①和②称为标准化图案,图案③至⑦称为非标准化图案。魔方的下平面如果是一个非标准化的图案,那么对这图案运用一次P8,然后返回1。
第二方案——
第一方案需要反复进行图案的核对,而核对有时既不方便(比如你给别人表演开解时),又容易出错。为此,特提供第二方案。第二方案只要求记牢图4中的标准化图案①和②(包括二者对前平面的选择),魔方出现这两种图案时,仍按第一方案中的2或3处理。如果魔方出现的是非标准化图案(对应于图案③至⑦中的某一个),你可以随意选一个竖直面为前平面(不需要与图4核对),先运用一次程序P8,完毕观察下平面是否标准化(注意,标准化图案最显著的特征是:只有一个下角块方向正确);如果没有,则沿用上一步选定的前平面,再运用一次P8的对称程序 ,再观察下平面是否标准化……,如此交替运用P8和 ,直到下平面达到标准化为止。此后,按第一方案中的2或3去处理。比如,对于图案④,假如你无意中将图4规定的后平面取成了前平面,那么你只须如此运用P8和 共三次:
P8→ →P8
就可以使图案④标准化为图案①。
正确的位置在下平面的四个边块统称下边块。下边块的开解是魔方开解的最后一道工序。我们的开解思路是:先考虑四个边块对下平面的定向问题,待这一问题得到解决后再考虑定位问题。现分述如下。
(甲)对下平面定向
一个方块对一个平面的定向问题在第一章(一)的结尾已经提说过。现在所说的对下平面的定向,具体是指对已经位于下平面的四个下边块,不管其位置是否正确,先使它们居于下平面的那些小正方形的颜色与下平面中心块相一致。或者说,现在就是要让下平面只有一种颜色。
1.开解前,我们所希望的下平面颜色一致的情形或许已经自动形成。如果不是这样,那么和中心块颜色不一致的小正方形(下边块的一个面)或者是两个,或者是四个。
2.如果这样的小正方形是两个,那么下平面可能呈现的图案将如图5所示(也许需要适当整体转动魔方,才能使它与图5中的某一个图案相一致)。
3.如果魔方的图案如图5①,请运用如下程序:
P9(下边块定向程序) R-, D-, R+, D+, R+, L-, F-, R-, F+, L+ (10次转动)
如果如果魔方的图案如图5②,则可运用P9的逆程序:
L-, F-, R+, F+, L+, R-, D-, R-, D+, R+
4.如果下平面中与中心块颜色不一致的小正方形有四个,则可以令魔方的任意一个竖直面为前平面,运用3中的程序P9,将下平面的图案转化为图5②,然后返回3。
(乙) 定位
完成了对下平面的定向以后,四个下边块或者已经全部归位,或者仅有一个归位,或者全部没有归位。
1.如果四个下边块仅有一个归位,可令已归位的那个边块所在的竖直面为右平面,运用如下的程序:
P10(下边块定位程序) F+, D+, L+, D-, L-, F-, D2, F-, R-,D-, R+, D+, F+, D2 (共14次转动)
如果运用后仍有三个边块没有归位,那么再运用一次P10,必使魔方获得彻底的开解[注]。
2.如果四个下边块全部没有归位,可任选一个竖直面为前平面,运用一次1中的程序P10后,必有一个边块归位。然后返回1。
开解法证明(Ⅰ)
第二章介绍六步开解法时,对每一步骤我们都估计了所涉方块在开解前可能的状态,进而针对所估计的状态给出了行之有效的开解方案。现在的问题是:我们是否已经充分估计了所涉方块所有可能的状态?或者说,是否存在某些图案,使我们所给的开解方案显得文不对题?如果我们认为所作的估计是充分的,所给的开解方案在任何时候都不会失效,则必须给出证明。可以把需要给出的证明称为完备性证明,即证明所给的开解方案对于魔方中一切实际可能的图案来说是足够的,或者说是完备的。
先考察第二章(一)对上边块的开解。一个被打乱的魔方,其任意一个上边块在逻辑上只能属于如下三类状态中的一类:
(i )位向正确;(ii)位置正确而方向不正确;(iii)位置不正确(不论方向)。
类状态(i)不论。对于后两类状态,我们当时针对其在逻辑上可能的子类,分别给出了有效的开解法。如该章节开解步骤2所针对的就是这里的状态(ii)。关于类状态(iii),一个上边块的位置不正确,在逻辑上它只能出现在魔方上中下三层共11个位置的某一个位置上。如果出现在下层,按该章节步骤3可予开解;如果出现在中层(共有四个可能的位置),按步骤4,5可予开解;如果出现在上层(共有3个可能的位置),按步骤6可予开解。通过如此的的讨论,事实上我们就证明了如下的命题:
第二章(一)所给的魔方上边块的开解方案是完备的。
如本章开头所说,这里的“完备”一词与“足够”同义。
依照上述思考方法,读者不难自行证出如下两个命题:
第二章(二)所给的魔方上角块的开解方案是完备的。
第二章(三)所给的魔方中边块的开解方案是完备的。
如此就完成了魔方上中层开解法完备性的证明。
在上述证明中,我们从逻辑上穷尽了所涉方块可能有的位向状态,由此证明的完备性又可以称为逻辑的完备性。
一个方块取代另一个方块的位置,这在魔方上是常见的,我们把这种现象称为置换。如果通过某些转动,使魔方上的方块a从原位移到方块b的位置(此时b又被移到了其它位置),我们就说a置换了b,或b被a所置换。很显然,置换只能发生在同类方块之间。
最基本的置换是对换:如果在a置换b的同时,b也置换a,则称a和b发生了一次对换。简单一点说, a和b互换位置就构成一个对换。
另一类重要的置换是轮换。如果a置换b,b置换c,c又置换a,则称三个方块a,b,c发生了一次轮换,记为(abc)。如若这三个方块正好在魔方的同一平面上,则相应的轮换按方向又可以分为顺时针轮换和逆时针轮换两种。
四个或四个以上方块轮换的定义可仿照三个方块轮换的定义给出:设有n个方块a1,a2,…,an,若a1置换了a2,a2置换了a3,…,an-1置换了an,an又置换了 a1,则称这n个方块发生了一次轮换,记为(a1a2…an)。
魔方某一平面上四个方块的轮换可以分为两类。如果四个方块中的每一个都按一定的方向置换自己的相邻块,则称如此的轮换为为相邻轮换。相邻轮换又可以按方向分为顺时针轮换和逆时针轮换两种。
平面上四个方块的另一类轮换称为“8”字轮换。在这种轮换中,任意一个方块若置换它的相对块,则它自身被一个相邻块所置换;反之,如果这方块置换它的一个相邻块,则它自身被一个相对块所置换。由于这类轮换发生在四个角块时移动路径的图形为“ ”或“ ”,发生在四个边块时移动路径的图形为“ ”或“ ”,故因其形象而被我们命名为“8”字轮换。
对于下角块的“8”字轮换中平卧的图形“ ”,只须将魔方整体转动90°(以上下中心块的连线为轴),该图形即变为直立的“8”字图案“ ”。又方块沿“8”字“笔画”的运动似乎有两个方向,如图9所示。
不妨假定图9①所示的方向为正,图9② 所示的方向为负,然后请读者把这本书倒转过来(从而使这一页的字全部倒立),你会看到图9①的方向由正变成了负,图9②的方向由负变成了正。由此可见两个图形所以看似不同,是因为魔方放置的方向(或读者的视向)不同。调整放置方向,一个图形就会完全地变成另一个。它表明下角块的“8”字轮换在我们目前的的讨论中其实只有一种[ 注 ]。以后讨论这种轮换时,除非必要,我们将只采用图9①。(显然,以上结论原则上也适用于斜“8”字轮换,即在不计方块的颜色时,下边块的斜“8”字轮换其实也只有一种)。
下来我们引入魔方平面(下平面)方块置换的示意图。记魔方左前下位置为A,右前下位置为B,右后下位置为C,左后下位置为D;依次记应属于这四个位置的方块为a,b,c,d,且依次分别称A,B,C,D为a,b,c,d的本位。若四个方块的位置正确,则其置换(为零置换,即所有方块不动的那个“置换” )的示意图为图10①。
如果此时发生了轮换(bcd),则图10①转化为图10②。如若再对图10②施行相邻轮换(adbc),则可使图10②转化为图10③。
由图10③可看出,依次对图10①施行两个轮换(bcd)和(adbc),相当于对图10①施行了(abdc)这一个轮换。而后一轮换正是“8”字轮换。类似地,我们可以给出下平面四个边块的置换示意图。比如应属于前下A'和后下B'的两个位置的方块a'和b'由本位发生对换,其示意图为图11。
在第二章(四)(甲)中我们指出,魔方上中层开解完毕后,适当转动(有时不须转动)下平面,下角块的位置状况总可以归结为如下三类情形中的一种:
(i ) 四个下角块已全部归位;
(ii) 仅有两个相邻下角块相对于本位发生对换;
(iii) 仅有两个相对下角块相对于本位发生对换。
对于后两类待解情形,我们当时给出了有效的定位开解方法,现在证明所给开解方法的完备性。
证明的思路是,逻辑地考虑四个下角块每一种可能的位置状态,对于不属于上述情形(i ) (ii) (iii)中的那些状态,指出如何转动下平面,使之化归为(i ) (ii) (iii)中的某一类,从而证明所给开解法的完备性。
【证明】⒈四个下角块皆未归位,此类状态分为四种情况。
(1)四个角块相对于本位呈现顺时针(或逆时针)相邻轮换,此时只须将下平面逆时针(或顺时针)转动90°,则转化为前述的情形(i )。其过程显然。
(2)四个下角块相对于本位呈现“8”字轮换,只须将下平面转动180°,则转化为情形(ii)。如图12所示。
(3)相邻角块相对于本位两两对换,可将下平面不论方向转动90度,则转化为情形(iii)。如图13所示。
(4)相对角块相对于本位两两对换,可将下平面转动180°,则转化为情形(i)。置换示意图略。
⒉仅有一个下角块归位,则其余三个角块必相对于原位呈现顺时针或逆时针轮换,如将下平面逆时针(或顺时针)转动90°,可转化为情形(ii)。图14显示了三个角块呈顺时针轮换时转化的情景。
⒊仅有两个下角块归位,正好是情形(ii)或情形(iii)。
⒋逻辑上不存在三个下角块已经归位而一个下角块仍未归位这种状态。
至此,下角块定位开解法的完备性得证。事实上,这里的完备性也是一种逻辑的完备性。
开解法证明(Ⅱ)
魔方是高度对称的机械。三类方块——中心块、边块和角块中的每一个方块,都和任意一个同类方块形成一定的对称关系。这些对称关系或隐或显,但却始终地、必然地制约着魔方图案的变化。即使是一个被彻底打乱的魔方,其图案也存在着严整的对称性(虽然常常不易察觉)。对称性是把握魔方奥秘的钥匙。
在魔方众多的对称性中,有一种最值得注意,我们把它称为跷跷板原理,并作为以后证明的公设。
跷跷板原理 对呈现于魔方的每一基本状态,在同一魔方上必然同时呈现出另外一些可以与之相互抵消的状态。
原理中所说的基本状态包括:
(i)零状态。 指一个位置或方向正确的方块的状态。它分为位置的零状态和方向的零状态。方向的零状态又分指两种情形:一是位向正确的方块的方向状态;另一种是,在魔方的上、下平面,不管一个方块是否归位,只要这方块对上平面或下平面已定向(参见第一章(一)的结尾文字),我们也说这方块的方向状态为零状态。借用代数方法,我们规定所有的零状态具有相同的状态值,这个值记为φ。
至于强调“上、下平面”,其用意到第六章自明。
(ii)一个角块的扭转。
(iii)两个同类方块的对换。
(iv)一个边块的翻转。
跷跷板原理是从跷跷板的运动悟出来的。跷跷板运动的基本特点是,两端运动者的起落状态总是相互抵消,一个运动者上跷一尺,另一个运动者必然同时下落一尺,二者位移的和等于零。魔方的结构、转动与跷跷板很相似,只不过更为复杂,状态间相互抵消的性质不像跷跷板那样一目了然。所谓“相互抵消”,其直观的含义主要是指一个非零的基本状态不可能在魔方上单独出现,它必然与另一些非零的状态相伴生,共同体现和满足魔方的机械结构与性能。
为了精准地凸显状态间相互抵消的关系,需要借助于数学方法。拟采用的数学方法的大义可叙述如下:
第一,给每一基本状态作一个记号,把这记号看成是这一状态的值。比如我们已经把零状态的值记为φ。
第二,给出几种类似于加法的运算并采用加法符号“+”,将某些同时出现的基本状态的值相加;如果按运算的定义相加的和恰好等于零状态的值φ(即各状态相互抵消),则我们说由这些基本状态组成的图案符合跷跷板原理,否则说图案不符合跷跷板原理。
第三,用上一步运算和判别的结果为论据,证明第二章所给的下角块定向开解法以及下边块定位、定向开解法的完备性。
下来我们对以上的方法作些初步的例说。为叙述方便,我们把可与一种基本状态相互抵消的状态称为这种基本状态的逆状态。按跷跷板原理,零状态也应有自己的逆状态,规定零状态的逆状态是它自身;后文将证明:
φ+φ=φ
又设X为某一基本状态的值,我们将指出:
X+φ=X
此外,在一个已开解的魔方上,所有方块的位向状态的值均为φ,设共有n个φ值,由等式φ+φ=φ可得:
φ+φ+…+φ=φ (等号左边共有n个φ相加)
此式意味着已开解魔方的图案也符合跷跷板原理。
易知一个角块由三个两两相交的小正方形构成。如果角块的位置不变,而三个小正方形发生了一次轮换,即第一个小正方形置换第二个小正方形,第二个小正方形置换第三个小正方形,第三个小正方形又置换第一个小正方形,我们就称该角块发生了一次扭转。扭转的方向按小正方形轮换的方向可以分为顺时针和逆时针两种。一个扭转变换,顺时针时记其状态值为S,逆时针时记其状态值为-S。通过观察可知,一个零状态角块顺时针扭转两次所成的图案,相当于这角块逆时针扭转一次所成的图案,故可以定义如下的加法运算:
S+S=-S ①
同理又有:
-S+(-S)=S ②
又因为一个零状态角块顺时针扭转一次再逆时针扭转一次,则角块方向复原,故可以定义:
S+(-S)=φ ③
同理又可定义:
-S+S=φ ④
此外,在第三章(二)我们曾提及置换。置换、扭转及后文将要考察的翻转可以统称为变换。可以改变魔方当前图案的那些变换称为非零变换。但在对魔方进行数学描述时,还必须用到零变换这一概念。我们把保持魔方的当前图案不变也看成是一种变换,并称之为零变换。教师在教室里对学生发出的“不准调位”的指令,是零变换的另一个现实模型。虽然我们将在不同的场合把零变换分别称为零扭转、零置换或零翻转,但这后三种“具体化”的零变换彼此并无实质的不同:它们都不会改变魔方任意既有的图案。基于这一原因,我们把所有的零变换或零状态不加区别地统统记为φ。
上一节所说方块的状态(或基本状态)其实可以看成是对方块施行一个变换(包括零变换)的结果。
一个方块的状态X0是相对于某一静止时刻而言的。对X0施行一个动态的变换X1(通过某些转动)后,X0变成另一状态X2。这一过程可用加法表示为:
X0+ X1= X2
与通常加法不同的是,这里不是数值的加法而是方块图案的“加法”。普通加法中的加数、被加数与和只能属于同一类型的数(在计算机的算法中尤其注重这一点),类比之下,方块图案加法中的X0,X1,X2也应属于同一类型的“值”。虽然,我们把X0和X2称为“状态”,把X1称为“变换”,但它们却都是图案加法数域中的元素。在以后的讨论中,一般我们将忽略“状态”和“变换”二者之间的自然语义的差别,只是把它们看作同一类型的值,可以自由地对它们进行图案加法的运算。此外,我们还将把图案的加法径直称为加法。
现记一扭转(可以是顺时针、逆时针或零扭转)的值为X(X可以是S,-S或φ),如果在这一扭转发生之前或之后,角块“发生”了一次零扭转,则这一扭转与零扭转的变换值的和可以记为φ+X或X+φ。但按照零扭转的意义,一个角块在一个扭转之前或之后保持不动,一旦该扭转发生,则角块的状态仍然会是这一扭转所导致的结果,故有:
φ+X= X ⑤
X+φ= X ⑥
作为特例,我们有:
φ+φ=φ ⑦
代数式①至⑥是魔方实验的记录,现以此作为出发点,推导“+”运算的交换律和结合律。
(i)交换律
证明交换律,就是要证明S和-S、S和φ、-S和φ这三对元素关于“+”运算的可交换性。
事实上,③式和④式共同显示了S和-S的可交换性;⑤式与⑥式显示了φ与任意扭转值X的可交换性。运算的交换律于是得证。
(ii)结合律
可供我们运算的仅有的三个元素为S,-S和φ,我们可以三个三个地任意选取这三个元素并组成的连加式,比如如下的式子:
-S +S+φ
S +S+(-S)
S+(-S)+ S
根据排列论,诸如这样的式子共有33=27个,这27个式子是:
⑴φ+φ+φ
⑵φ+φ+(-S)
⑶φ+φ+S
⑷φ+(-S)+φ
⑸φ+(-S)+ (-S)
⑹φ+(-S) +S
⑺φ+S+φ
⑻φ+S+(-S)
⑼φ+S+S
⑽-S +φ+φ
⑾-S +φ+(-S)
⑿-S +φ+S
⒀-S+(-S) +φ
⒁-S +(-S) +(-S)
⒂-S +(-S) +S
⒃-S +S+φ
⒄-S +S+(-S)
⒅-S +S+S
⒆S+φ+φ
⒇S+φ+(-S)
(21)S+φ+S
(22)S+(-S) +φ
(23)S+(-S) +(-S)
(24)S+(-S) +S
(25)S+S+φ
(26)S+S+(-S)
(27)S+S+S
我们可以逐个地来证明这27个式子都满足结合律,比如⒃式:
∵-S+S+φ=φ+φ=φ
-S+(S+φ)=-S+S=φ
∴-S+S+φ=-S+(S+φ)
又比如(26)式:
∵S+ S+(-S)=-S+(-S)= S
S+( S+(-S))= S+φ=S
∴S +S+(-S)= S+( S+(-S))
对所有的式子都进行如上的检验将是冗长乏味的,但如果我们进行了这样的检验,就会发现运算的结合律确实成立。
以上所讨论的“+”运算共有S,-S,φ三个元素,这些元素连同算式①,②,③,④,⑤,⑥,我们称之为扭转代数。而此代数中交换律、结合律和⑤,⑥,⑦式在后续的置换代数和翻转代数中仍然对应成立,届时将径直运用而不再予以推导。
按本书第二章(四)(乙),在完成定位开解后,魔方四个下角块的方向或者完全正确,或者呈现如图4所示的图案。而那些图案皆可以采用扭转代数予以描述。
运用扭转代数,容易验证图4中各图案之未定向下角块的状态值的和皆等于零状态值φ,亦即这些图案全部符合跷跷板原理。以图4-1为例,魔方的三个未定向下角块的状态皆为顺时针扭转,其状态值的和(记为Σ)应为:
Σ=S+S+S=-S+S=φ
对其余各图案皆可以仿此进行验证。
从逻辑完备性的角度考虑,除过已开解状态,魔方四个下角块一切逻辑上可能(自然包括实际可能)的方向状态的组合、以及这些组合各自状态值的和可列示如表1。
(表1)
未定向下角块的组合表
总类
细类
具体状态
状态值
的和Σ
四个
下角块
皆未定
向
1
四个下角块逆时针扭转
-S
2
三个下角块逆时针扭转,一个反之
S
3
两个下角块逆时针扭转,另外两个反之
φ
4
一个下角块逆时针扭转,其余三个反之
-S
5
四个下角块顺时针扭转
S
仅有
三个下
角块未
定向
6
三个下角块逆时针扭转
φ
7
两个下角块逆时针扭转,一个反之
-S
8
一个下角块逆时针扭转,两个反之
S
9
三个下角块顺时针扭转
φ
仅有
两个下
角块未
定向
10
两个下角块逆时针扭转
S
11
一个下角块逆时针扭转,另一个反之
φ
12
两个下角块顺时针扭转
-S
仅有
一个下
角块未
定向
13
一个下角块逆时针扭转
-S
14
一个下角块顺时针扭转
S
【说 明】(1) 最右一栏中的Σ的值,系依据对应的具体状态,运用扭转代数计算而来的。如细类7,按具体状态其状态值的和可计算如下:
Σ=-S+(-S)+S=S+S=-S
(2) 有些细类在逻辑上还可以分出更小的类,但进一步的分类并不会改变Σ的值。
表中方块扭转状态的组合计四总类,十四细类。凡∑≠φ,亦即不符合跷跷板原理的那些组合所对应的魔方的“图案”,皆为逻辑上可能而实际不可能的图案;所有符合跷跷板原理,亦即∑=φ的那些组合所对应的魔方的图案,皆为实际可能(自然也是逻辑可能)的图案。从表上可以看到,符合跷跷板原理的只有3,6,9,11四个细类。而这四类刚好对应着第二章图4的七个图案,其详情如下。
细类3谓“两个下角块逆时针扭转,另外两个反之”,但在魔方的下平面上,两个同向扭转的下角块的位置可以是相邻的,也可以是相对的,故细类3实际可以再分为两个小类。此两个小类分别应着图4⑤(同向扭转的方块相邻)、图4③(同向扭转的方块相对)。
细类6对应图4②,细类9对应图4①。
细类11仅有两个下角块互为反向扭转,但它们在下平面的位置也可以是相对的或相邻的。位置相对的那一小类对应着图4⑥。而位置相邻的那一小类还可以进一步进行分类。为了便于叙述,我们把魔方下角块(以及以后还要论及的下边块)染着下平面颜色的那个小正方形称为下色面。这样,上述位置相邻的小类就可以按两个扭转下角块的下色面是否是在魔方的同一侧面,划分为两个更小的类。划分后一个更小的类对应图4④(两个下色面位于魔方的同一侧面),另一个更小的类对应图4⑦(两个下色面位于魔方的不同侧面)。
至此我们就可以断言,从逻辑上推定的所有符合跷跷板原理的未定向下角块的组合,正好对应着图4中的七个图案。于是第二章(四)(乙)所给的下角块定向开解法的完备性得证。
本章所证明的完备性可以称为相对于跷跷板原理的完备性。它与上一章所说的逻辑的完备性有深刻的差别,但对这些差别的讨论却不属于本书的任务。
开解法证明(Ⅲ)
为了证明下边块定向开解法的完备性,须要引入翻转(音zhuǎn)代数。
魔方中构成一个边块的两个小正方形交换方向,这一置换称为一个翻转,记为T。一个边块翻转一次再翻转一次,就恢复了原来的方向,据此可以定义翻转的基本运算:
T+T=φ
和扭转代数一样,在翻转代数中,加运算的交换律和结合律成立,并且:
T+φ=T, φ+φ=φ
第二章(五)(甲)在考虑下边块对下平面的定向时,认为在完成了该章步骤(一)至(四)所述的开解后,如果有下边块相对于下平面呈现翻转,则翻转的方块只能是2个或4个,并针对这两类情形给出了开解方法。
两个翻转状态的方块,无论其位置相对还是相邻,其状态和皆为:
∑=T+T=φ
四个翻转方块的状态和为:
∑=T+T+T+T=φ+T+T=T+T=φ
故该处所论的两类待解情形完全符合跷跷板原理。现在假设翻转的下边块为一个或三个,则其状态和分别为:
∑(1)=T≠φ
∑(3)=T+T+T=φ+T=T≠φ
∑≠φ意味着假设的1个或3个下边块翻转的图案不符合跷跷板原理,故而在正常的魔方上不会出现这两种图案。如此,我们就证明了第二章(五)(甲)所给的下平面定向开解法的完备性。
为了证明下边块定位开解法的完备性,须要引入置换代数。
对换是最简单最基本的置换。用C表示一个对换;一个对换总须涉及两个方块,两个方块对换一次再对换一次,二者又都回归到了各自原来的位置,据此可以定义对换的基本运算为:
C+C=φ
与翻转代数相类似,在对换代数中亦有:
C+φ=C, φ+φ=φ
且加运算的交换律和结合律成立。
为了便于讨论,有时又把a,b两个方块的对换记为(ab)。
轮换也可以看成是一种基本的置换。记a,b,c三个方块的轮换为(abc),原则上,三个方块的轮换总可以化归为两个对换。具体的化归过程是:先对换a,b,然后再对换b,c。用算式表达即为:
(abc) =(ab) + (bc)
仿此亦不难推出四个方块所形成的轮换总可以化归为三个对换。一般地,我们有如下的定理:
化归定理 大于2的n个方块的轮换可以化归为n-1个对换。
【证明】 运用构造法来证明,即构造出n-1个对换,使其等同于已知的n元轮换。
记n个方块a1,a2,…,an所成的一个轮换为(a1a2…an),又记方块ai在置换发生前的原初位置为Ai,对这n个方块做如下n-1个系列对换:
(a1a2) + (a2a3) + (a3a4) + … + (aiai+1) + … + (an-1an)
按上式,第1个对换发生后,a1到达A2,a2到达A1;第2个对换发生后,a2到达A3,a3到达A1,此时方块的排布是:
位置
A1
A2
A3
A4
…
Ai
Ai+1
方块
a3
a1
a2
a4
…
ai
ai+1
第i个对换发生后,ai到达Ai+1,ai+1到达A1。此时方块的排布是:
位置
A1
A2
A3
A4
…
Ai
Ai+1
方块
ai+1
a1
a2
a3
…
ai-1
ai
由上表可以看到,方块a1,a2,…, ai,ai+1正好形成了一个i+1元的轮换(a1a2…aiai+1)。
继续进行系列对换,当第n-1个对换(an-1an)完成后,其结果正好是轮换(a1a2…aiai+1…an)。
——证毕。
由化归定理不难得出如下两个推论:
推论1 奇数个方块的轮换可以化归为偶数个对换,偶数个方块的轮换可以化归为奇数个对换。
推论2 奇数个方块所成轮换的状态值为φ,偶数个方块所成轮换的状态值为C。
完成了下边块对下平面的定向以后,第二章(五)(乙)指出:如果此时下边块没有归位或没有全部归位,那么实际可能的情形是:或者仅有一个下边块已归位,或者四个下边块全部没有归位。现从逻辑完备性的角度出发,运用跷跷板原理和置换代数予以证明。
1. 仅有一个下边块未归位,这在逻辑上不可能。
2.仅有两个下边块未归位,则这两个方块只能形成一个位置对换,其图案的状态和为:
∑=C≠φ
这不符合跷跷板原理,故实际不会出现这种情形。
3.仅有三个下边块未归位,则这三个方块必构成一个轮换,由上节知三个方块的轮换可以化归为仅涉及这三个方块的两个对换,故此时下边块的状态和为:
∑=(a1a2a3)=C+C=φ
这符合跷跷板原理,而这正是第二章(五)(乙)1所估计的。
4.第二章(五)(乙)2给出了四个下边块皆未归位的开解方法,其实它所针对的只是如图15所示的两类对换情形:
在图15①中,本位为A的边块a与本位为B的边块b互占对方的本位,边块c与边块d也互占对方的本位,此为位置相对的边块两两对换;而图15②中所示的则是位置相邻的边块两两对换。两个图案各有两个对换,其各自的状态和皆为:
∑=C+C=φ
此与跷跷板原理相符。
此外,从逻辑上说,四个未归位方块还应有三种轮换的形式:顺时针相邻的轮换,逆时针相邻的轮换,斜“8”字轮换(参见第三章(二))。但无论哪种形式,依据置换代数,由四个方块构成的一个轮换总可以化归为三个对换的和,故而这三种图案的状态和皆为:
∑= C+C+C=φ+C=C≠φ
这与跷跷板原理不符,故而在所论的开解时刻(其它时刻未必),魔方的四个下边块不会呈现轮换图案。
至此,我们就证明了第二章(五)所给的下边块定位开解法的完备性。
现在让我们来概括地回顾一下第三章至本章主要的内容。针对第二章所给的魔方开解的顺序(共六个环节,见第二章引言),在第三章中,我们仅从逻辑完备性的角度出发,列举了所论的各开解步骤(包括子步骤)实施前所涉方块所有可能的图案;在第四章与本章中又同时依据跷跷板原理,指出所论的逻辑可能的图案哪些实际上不可能存在;而在这三章中我们还陆续指出了:一切实际且逻辑可能存在的图案,均在第二章开解方案所考虑的范围之内。
所以,第二章所给的开解方案是完备的。
方块的空间状态暨魔方表示定理
前边具体讨论魔方方块的状态时,主要是在一个层面内——下层面进行的。本节将转入魔方空间——三层、六个面的方块状态的讨论。
对于位置状态,即使在空间中,我们仍然可以仅凭观察就可以确定哪些方块相对于原位发生了对换,哪些方块相对于原位发生了轮换。
为了确定方块在魔方空间中的方向状态,我们必须事先约定魔方六个面的方向:你可以任意地指定前、后、左、右、上、下平面,然而一旦这种指定完成,就不能随意改换。这一点与前面开解法中的规定稍有不同。
此外,还需要以下术语:
上色面——一个方块上染着上平面颜色的那个小正方形。
下色面——一个方块上染着下平面颜色的那个小正方形。
前色面——一个方块上染着前平面颜色的那个小正方形。
后色面——一个方块上染着后平面颜色的那个小正方形。
完成了这些准备工作,就可以对方块在魔方空间中正确的方向状态(其方向状态值为φ)进行如下的约定:
上角块位于本层且其上色面位于上平面时,方向正确;位于下层而其上色面位于下平面时,方向正确(仅仅只是位置发生了变化)。
下角块位于本层且其下色面位于下平面时,方向正确;位于上层而其下色面位于上平面时,方向正确。
——以上两种方块在不同层面、不同位置上的顺时针和逆时针的扭转状态与前面章节的约定相同。
上边块位于本层且其上色面位于上平面时,方向正确;位于中层且其上色面位于左平面或右平面时,方向正确;位于下层且其上色面位于下平面时,方向正确。
下边块位于本层且其下色面位于下平面时,方向正确;位于中层且其下色面位于左平面或右平面时,方向正确;位于上层且其下色面位于上平面时,方向正确。
中边块位于本层且其前色面或后色面均位于前平面或后平面时,方向正确;位于上层且其前色面或后色面不在上平面时,方向正确;位于下层且其前色面或后色面不在下平面时,方向正确。
——所有边块不符合以上所说的情形时,其方向状态均为翻转状态。
为了便于读者在魔方空间上验证跷跷板原理,特将以上的约定集中列示为表2。
表2约定是基于如下一些考虑而做出的。
以边块为例,虽然当一个边块不在本位时,我们很难说它是否发生了翻转,但它依然像在本位时那样具有两个可能的方向。这两个方向与其在本位时的两个方向之间存在一一对应关系[注1],任选一种一一对应关系,把与值为φ的那个本位方向状态对应的非本位方向状态的值也记为φ,把另一个非本位方向状态的值记为T[注2]。这样,一个边块即使不在本位,我们仍然可以按它的方向状态的值称其为翻转(当值为φ时)或未翻转(当值为T时)。
(表2)
位 置
方向
状态值
说明
方 块
类 型
在上层
在中层
在下层
上角块
√
上色面位于上平面
φ
其它方向状态的值为S或-S
√
上色面位于下平面
下角块
√
下色面位于上平面
√
下色面位于下平面
上边块
√
上色面位于上平面
φ
其它方向状态的值为T
√
上色面位于左或右平面
√
上色面位于下平面
中边块
√
前或后色面不在上平面
√
前或后色面位于
前平面或后平面
√
前或后色面不在下平面
下边块
√
下色面位于上平面
√
下色面位于左或右平面
√
下色面位于下平面
不过仅用一一对应的思想作指导还不够。在约定方块在魔方空间中的方向状态时,还必须考虑魔方的对称性。对称性的约束从表2中可以很明显的看出。表中横栏“上边块”第二行约定:当一个上边块位于中层时,仅当“上色面位于左或右平面”,其方向状态值为φ。所谓“上色面位于左或右平面”又可以表述为:上边块的上色面不在前平面或后平面。而在横栏“中边块”第一行则有与此完全对称的表述:位于上层时,中边块的“前或后色面不在上平面”,其状态值为φ。整个表2其实正是用这样的对称表述架构而成。
最后的问题是,由对称性约束而得来的表2,是否仍然与跷跷板原理相合?答案是肯定的。因为跷跷板原理是对称性的集中表现,事实上我们也可以不刻意追求上面那种对称的语义表述,而直接运用跷跷板原理来约定方块在魔方空间中的方向状态,最终仍然可以得出与表2相同的内容。对此就不作详述了。
二) 魔方表示定理
在前几章中,我们多次提到了所谓“逻辑上可能而实际不可能”的图案,并强调此类图案不会出现在在一个正常的魔方上。不过,在一个组装错误的魔方上,这些图案却可能出现。下面所给的就是关于组装错误的魔方所遵循的一个定理。
魔方表示定理 把一个正常的魔方拆散后随意组装,不管在组装过程中发生了多少组装错误,组装完成后总可以使这些错误化归为魔方某一平面上不超过三个方块的错误。
【说明】从逻辑上看,在跷跷板原理的支配下,定理中所说的化归后的错误只能是如下11类错误中的一类:
当其它所有方块都正确时,在魔方的某一平面上——
(ⅰ) 一个角块顺时针扭转;
(ⅱ) 一个角块逆时针扭转;
(ⅲ) 一个边块翻转;
(ⅳ)两个边块对换[注1];
(ⅴ) 一个边块翻转且它同时与另一个边块对换;
(ⅵ) (i)和(ⅲ)的组合;
(ⅶ) (ⅱ)和(ⅲ)的组合;
(ⅷ) (i)和(iv)的组合;
(ⅸ) (ⅱ)和(iv)组合;
(x) (i)和(v)的组合;
(xi) (ⅱ)和(v)的组合。
以上11类错误再加上正确的一类,正好对应于所谓的魔方组装的12个族。
就思路而言,本定理的证明与前面开解法完备性的证明并无二致。为避免冗长,这里我们仅指出证明的思路。
在第三章,我们证明了第二章所给的下角块定位及其以前各步骤的开解法具有逻辑的完备性,故而一个魔方无论有多少组装错误,并不影响第二章所给的上边块、上角块和中边块的定位定向开解法的有效性和充足性,也不影响下角块定位开解法的有效性和充足性。故而按第二章的开解步骤,在完成了下角块的定位开解后,魔方的全部组装错误将表现于下平面。
如果组装确有错误,则下平面的图案必然不符合跷跷板原理。当我们逻辑地列出所有不符合跷跷板原理的图案时(麻烦和冗长就在这里),就会发现,我们总可以选择(有时不须选择)第二章中的某些转动程序,使这一图案化归为本节上文【说明】中所列的某一类图案。比如,假设一个组装错误的魔方此时其下平面呈现图案如图16①:
此图案不符合跷跷板原理。对此图案运用一次程序P8(见第二章),再以魔方上下中心块的连线为轴,将魔方整体转动180°,则呈现图案如图16②。对图案16②运用一次P8的对称程序 :
L+,D+, L-, D+, L+, D2, L-, D2
图案转化为图16③,这正是【说明】中所举的错误(i)。[注2]
对所有不符合跷跷板原理的图案,均可以通过类似于以上的步骤,使之转化为前面【说明】中所列的错误(i)至(xi)中的某一种。又所有符合跷跷板原理的图案与不符合跷跷板原理的图案可以构成一个全集——亦即魔方上一切逻辑可能(无论其正确与否)的图案的集合。至此魔方表示定理可以得证。
几个重要的计数公式
我们准备运用跷跷板原理和排列组合知识来计算魔方上所有图案的组合数。为此,需要先引入和证明几个重要的组合计数公式。本章的数学意味太浓且论证琐细,不感兴趣的读者可以只看结论而略去过程。
记n个连续自然数的集合{1,2,3,…,n}为N(n),并用这n个自然数来标记n个不同的方块,这样n个方块的任意一个轮换可以表示如图17。图中的每一个ni N(n),且i N(n),当i≠j时ni≠nj。
此图是以n个数为顶点、n个箭头为边的多边形。用这样的图形来表示轮换,可以使互为反向的轮换或魔方实际中更为复杂的轮换路径的图案(这些图案还可能是立体的)得到统一的、简单的表示。比如位于魔方同一平面的n1,n2,n3三个方块,其顺时针轮换可表示为图18①,逆时针轮换可表示为图18②。
图18中①和②所用箭头完全相同,不需要再使用相反的箭头把逆时针轮换表示为②a,也不须考虑这三个方块是否在同一平面。故而,在标准的轮换示意图18①和18②中,完全可以用直线来代替箭头。这样n个方块构成的任意一个轮换又可以由图17进一步简化表示为图19:
现另举一个例子来说明这种表示法的好处。按本书第三章(二),如果考虑方块的不同颜色,一个平面上四个角块n1,n2,n3,n4的“8”字轮换须分别表示为图20中的①和②,而采用标准示意图,则①简化为①a,②简化为②a。这样就避免了实际中“8”字图案所带来的困惑。
记n个方块(n.≥3)所成的轮换数为R(n),现在证明:
R(n)=(n-1)! (n.≥3) ………………A
【证明】 用数学归纳法[注]。
当n=3时,R(3)=(3-1)!=2,此时公式③成立(三个方块仅有的两个轮换见本节图18①和②)。
设n=k时R(k)=(k-1)!成立,考虑n=k+1。已知k个方块的任意一个轮换可用边数为k的多边形表示,任取这多边形的一条边,将其“切断”,在断点处插入一个新的方块l,就可以构成一个k+1元的轮换,如下图。
由于k元轮换多边形有k条边,故而可供l插入的位置有k个;而l每插入一个位置,就与原来轮换中的所有元素构成一个新的k+1元轮换,即在一个k元轮换中插入一个元素,可以生成k个互不相同的k+1元轮换。但由归纳假设,k个方块所成的k元轮换又有(k-1)!个,故而增加一个方块后生成的k+1元轮换总共应有k(k-1)!=k!个,即
R(k+1) =k!
——证毕。
计算魔方方块的组合数,常常需要把一些方块分成相等的几组。
中学数学课本中有类似于这样的习题:把6个方块平均分成两组,有几种分法?答案是:用6个元素中选取3个元素的组合数除以2,即
现在考虑把6个方块平均分成3组。先用连续自然数1至6给6个方块编号。通常的考虑是先从6个方块中选取2个为第一组(有 种选取法),再从剩下的4个方块选取2个为第二组(有 种选取法),最后剩下的2个作为第三组(有 =1种选取法),按照排列论,这样的分法的个数为:
……………… Δ
以下是这种分法的一个实例:
Ⅰ
第一组:{1,2}
第二组:{3,4}
第三组:{5,6}
Ⅱ
然而按这种分法至少还有以下的两个实例:
第一组:{3,4}
第二组:{1,2}
Ⅲ
第三组:{5,6}
第一组:{5,6}
第二组:{3,4}
第三组:{1,2}
但按我们的目的——只是把6个方块平均分成三组,并不需要考虑组的先后顺序,这样以上三个实例只能算是同一个分组。显然,Ⅰ、Ⅱ、Ⅲ属于既定的三个组集合的3种排列,按照排列论,这样的排列共有3!种。这意味着按Δ式所进行的计数有重复,每一个分组被计算成了3!个,去掉重复后符合我们目的的分组的个数应为:
从以上的特例可以过渡到一般情形。设k整除n,把n个方块平均分成k组,每一组的方块数为l,则如此分组的个数为:
(l≥2 ) ………………… ※
其推求的途径与上边的特例相仿,只是符号表述过于复杂,在本章最后一节给出其推导的全过程。
由表达式※立刻可以得出:设n为偶数,l = 2,从而 ,记这n个方块可以形成的对换个数为f(n),则
……………… B
当n=2时,f(2)=1 。
若l大于等于3,按本章(一)公式A,l个方块可以形成(l-1)!个轮换。当n个方块被平均分成k组且每一组为l个方块(l≥3)时,记这n个方块可形成的l元轮换的个数为g(n,k,l),则由表达式※及公式A可得:
※·[R(l)]k = ……………… ☆
即:
……………… C
注意在☆式中之所以取因式[R(l)]k而不是R(l),是因为 个分组中的每一个分组都有k个组,而k个组中的每一个组都可以独立地形成R( l )个不同的轮换。
公式A,B,C与组合数 的计算公式,是下一章计算方块置换数的主要公式。现预先举例说明如下。
【例1】6个活动角块,其中4个角块轮换,剩余2个角块对换,这样的置换的组合数为:
C ·R(4)· f(2)= C (4-1)! f(2)
= ·3! = 2520
【例2】9个活动边块形成三个3元轮换,轮换组合的总数为:
g(9,3,3) = 492800
【例3】8个角块,其中4个角块形成两个对换,另4个角块形成一个四元轮换,这样的置换的组合个数为:
f(4)· R(4) = f(4)·3! = 1260
在下一章表6和表7中,皆循以上诸例列式并计算。其中【例3】不符合跷跷板原理,故未被列入表6。
若k整除n,则n个方块被平均分成k组时,每组有l = 个方块。为推导表达式※,我们对这k个组用1至k共k个连续自然数进行编号,然后先让第1组从n个方块中选取l 个方块,再让第2组从n-l个中选取l个,组序递增,每一组均在前面各组选取后剩余的方块中选取l个方块;至第k组,从n-(k-1)l=l个方块选取l个方块。按照排列组合知识,如此选取所得的组合数为(注意n= k l):
… …
在这 个组合中,从不计先后顺序而分组的角度来看有些是重复的。用bij(i=1,2,…,k;j=1,2,…,l)表示n中的方块,考察这 个组合中的以下两个组合:
Ⅰ
第1组:{b11,b12,…,b1l}
第2组:{b21,b22,…,b2l}
………………………
第 i组: {bi1,bi2,…,bi l}
………………………
第k 组:{bk1,bk2,…,bkl}
Ⅱ
第1 组:{bi1,bi2,…,bi l}
第2 组:{b21,b22,…,b2l}
………………………
第i 组:{b11,b12,…,b1l}
………………………
第k 组:{bk1,bk2,…,bkl}
组合Ⅰ中的第1组与第i 组互换位置即为组合Ⅱ,可见Ⅰ和Ⅱ只是k个既定集合的两个不同排列。按我们的要求,以上两个排列只能算是同一个分组。依据排列论, k个元素的不同排列共有k!个,而所有这k!个排列在此都应视为同一分组,故而,符合我们目的的分组的个数应为:
(l≥2 )
——表达式※推导完毕。
魔方组合计数
用状态值来表示,则一个角块三种可能的方向状态是:φ,S,-S,而任意多个角块的方向状态的和也只能是这三个值。
现在先考察两个角块的情形。如果不考虑跷跷板原理,则对于第一个方块的三个方向状态中的每一个,第二个方块都有三个方向状态与之配对,故而此时两个方块的方向组合数为32=9(这些组合并不完全符合跷跷板原理),如下表所示。
(表5)
第一个角块的值
第二个角块的
对应值
状态和
φ
φ
φ
φ
S
S
φ
-S
-S
S
φ
S
S
S
-S
S
-S
φ
-S
φ
-S
-S
S
φ
-S
-S
S
现在过渡到3个方块。对于前两个方块9个方向组合中的每一个,第三个方块也都有三个方向状态分别与之配对(配对的结果不一定符合跷跷板原理),故而此时3个方块的方向组合数为33=27。
重复以上步骤可以推算出4,5,6,7个角块的方向组合数。其中7个方块的方向组合数为37=2187。
当我们考察8个方块的方向组合的时候,就必须考虑跷跷板原理了。这是因为跷跷板原理只能且必须体现在完整的魔方中,而少于8个角块的魔方是不完整的。
7个方块的37=2187个组合中的每一个,其状态值只能是集合{φ,S,-S }中的一个元素;在跷跷板原理的支配下,如若这37个组合中的某一个组合的状态值为φ,则第八个方块只能等于φ,而不能像上边那样随意地取S或-S;当有另外两个组合的状态值分别为S和-S时,第八个方块又只能分别对应地取-S和 S值。概括地说,对于7个方块的37个方向组合中的每一个,第八个方块只能有一种方向状态与之对应组合。所以,在跷跷板原理的支配下,魔方上8个角块的方向组合数应为:
37×1=37=2187
用同样的思路,我们可以算出12个边块的方向组合数。注意到一个边块只有两个方向状态,则12个边块的方向组合数应为:
211=2048。
在第三章(二)中,置换被划分成对换和轮换两种。现在我们把参与了非零置换的那些方块称为活动方块,而方块的置换组合数是由活动方块数决定的。在若干个活动方块中,一部分可能形成对换,另一部分则可能形成轮换。下面给出8个角块所有符合跷跷板原理(实际可能)的置换组合表:
(表6)
符合跷跷板原理的角块置换组合一览表
活动
方块数
细类
组合方案
组合算式
组合值
0
①
没有角块参与非零置换
1
3
①
3元轮换
112
4
①
两个对换
210
5
①
5元轮换
1344
6
①
4元轮换,1个对换
2520
②
两个3元轮换
1120
7
①
7元轮换
5760
②
两个对换,一个3元轮换
1680
8
①
6元轮换,一个对换
3360
②
5元轮换和3元轮换各一
2688
③
两个4元轮换
g(8,2,4)
1260
④
四个对换
f(8)
105
合计
20160
容易知道,8个角块所有的置换(无论是对换或轮换)都属于8个角块的全排列。依据排列知识,8个角块的全排列数为
8!= 40320
从中减去表6中“组合值”栏的“合计”数:
40320-20160 = 20160
所得的结果为不满足跷跷板原理的角块的组合数, 它正好与满足跷跷板原理的角块的组合数相等——这一现象绝非偶然,但我们不讨论这一问题。
现在来看表6中的组合方案是如何得来的。简单地说,它们是通过整数分拆得来的。整数分拆属于数论知识,本身比较复杂。所幸的是需要我们分拆的数很小:角块时最大为8,边块时最大为12;所以完全可以通过简单地思考得到全部符合条件的分拆。下边予以具体说明。
对于i个活动方块,把它们分拆为若干组,使各组分别形成对换或轮换,这首先要求i大于3,同时要求各组所含的方块数大于等于2——这些要求的正当性在逻辑上显然。此外按照数学惯例,i=0也是可以允许的;事实上,i=0表明没有方块发生置换,即所有的方块位置正确,这是一种符合跷跷板原理的合法的组合。现在以i=6为例来看看具体的分拆过程。先考察含有0个对换的分拆(注意这里与表6所列的顺序并不一致,但不影响考察的结果),此时方块只能分拆为一个6元轮换或两个3元轮换,后者因其状态和符合跷跷板原理而被列入表中;如果分拆仅含有1个对换,此时方块只能被分拆为一个对换与一个4元轮换这共存的两组,此两组的状态和也符合跷跷板原理,故而被列入表中;仅含有2个对换的分拆逻辑上不存在;含有3个对换的分拆因其状态和不符合跷跷板原理而未被列入表中。这样,我们就在表6中列出了6个活动角块符合跷跷板原理的全部置换组合方案。表6中其余的组合方案以及下一节表7中所列的活动边块的组合方案,其求取的思路与以上所说的完全一致。
12个边块符合跷跷板原理的置换组合值,当活动边块数k小于9时,可将表6中对应的k个活动角块的组合值除以 再乘以 即可得到,由此得k小于9时的12个组合值是:
1,440,1485,19008,83160,36960,570240,166320,1663200,1330560,
623700,51975
这12个值的和已填入表7“组合值”栏第一行。表7的最后给出了所有符合跷跷板原理的边块置换组合数的合计值为:239500800。
(表7)
符合跷跷板原理的边块置换组合一览表
活动
方块数
细类
组合方案
组合算式
组合值
小于9
合计
4547049
9
①
9元轮换
·8!
8870400
②
三个3元轮换
492800
③
一个对换,4元轮换和3元轮换各一
3326400
④
二个对换,一个五元轮换
1995840
10
①
7元轮换和3元轮换各一
11404800
②
6元轮换和4元轮换各一
9979200
③
两个五元轮换
4790016
④
一个对换,一个8元轮换
14968800
⑤
两个对换,两个3元轮换
1663200
⑥
三个对换,一个4元轮换
1247400
11
①
11元轮换
43545600
②
两个4元轮换,一个3元轮换
4989600
③
一个5元轮换,两个3元轮换
5322240
④
一个对换,6元轮换和3元轮换各一
13305600
⑤
一个对换,5元轮换和4元轮换各一
11975040
⑥
两个对换,一个7元轮换
8553600
⑦
四个对换,一个3元轮换
415800
12
①
9元轮换和3元轮换各一
17740800
②
8元轮换和4元轮换各一
14968800
③
7元轮换和5元轮换各一
13685760
④
两个6元轮换
g(12,2,6)
6652800
⑤
四个3元轮换
g(12,4,3)
246400
⑥
一个对换,一个10元轮换
23950080
⑦
一个对换,两个3元轮换,一个4元轮换
3326400
⑧
两个对换,5元轮换和3元轮换各一
3991680
⑨
两个对换,两个4元轮换
1871100
⑩
三个对换,一个6元轮换
1663200
⑾
六个对换
f(12)
10395
合计
239500800
(四) 魔方方块的总组合数
本章以上已分别计算了角块、边块各自符合跷跷板原理的方向组合数与置换组合数,现在汇总计算魔方方块的总组合数。为方便引用,我们把已算出的结果集中列示如表8。
(表8)
组合类型
组合数
计算所在的章节
角块方向组合
37=2187
本章(一)
边块方向组合
211=2048
本章(一)
角块置换组合
20160
本章(二)
边块置换组合
239500800
本章(三)
按表8,已经知道角块的方向组合数为2187,角块的置换组合数为20160,在不考虑边块时,符合跷跷板原理的角块的组合总数为:
2187×20160 ①
同样,在不考虑角块时,符合跷跷板原理的边块的组合总数为表8中边块的方向组合数与置换组合数的乘积:
2048×239500800 ②
此外,单独看角块,其不符合跷跷板原理的置换组合数为:
8!-20160=20160
单独看边块,其不符合跷跷板原理的置换组合数为:
12!-239500800=239500800
当边角两类方块的置换同时不符合跷跷板原理时,其各自的状态和皆为C,但这两个状态和的和为:
C+C=φ
这又符合跷跷板原理,故由这两类不符合跷跷板原理的置换相互搭配所成的组合,仍然是合法、正确的魔方图案,应计入组合总数中。此两类搭配所成的置换组合数为:
20160×239500800
再考虑到方向数,则这两类搭配所成的组合的总数应为:
20160×239500800×2187×2048 ③
现在,可以计算魔方方块的总组合数如下:
①×②+③=2187×20160×2048×239500800+20160×239500800×2187×2048
=2×20160×239500800×2187×2048
=43252003274489856000
≈4.3×1019
至上一节完成的魔方方块组合数的整个计算过程具有较强的直观性,它使读者能具体地了解到魔方的方块是如何组合、如何置换的。但表6和表7中繁复的数字计算却显得有些丑陋。为避免这种丑陋,以下给出另外两种算法。
(甲)引用魔方表示定理
按照排列组合知识,易知8个角块在魔方上的逻辑可能的置换组合可以看成是8个角块的全排列,其数值为8!;同理12个边块逻辑可能的置换组合数为12!。又易知8个角块逻辑可能的方向组合数为38,12个边块逻辑可能的方向组合数为212。这样魔方全部逻辑可能的图案数为:
8!×38 ×12!×212
这是所有组装正确和组装错误的魔方图案的总数。由魔方表示定理知道,这样的图案可分为12个族,其中仅有一个族的图案为组装正确的魔方的图案。各族的图案数应该相等——这是因为,一个组装错误的魔方与组装正确的魔方有着完全相同的物理构造和转动方式。不妨想象已知的组装错误的魔方只是对一个组装正确的魔方进行重“染色”而成的,“染色”行为显然不会改变这个魔方中方块的组合数。故而,任意一个既已组装的三阶魔方(无论其组装正确与错误)的图案的总数应为:
(乙)引用群论中的一个知识点
在本书结尾的这一部分,我们稍微提及群论。但我们的讨论只能是概要的、不甚严密的。
本书前面所说的符合跷跷板原理的置换,在群论中称为偶置换,不符合跷跷板原理的置换被称为奇置换。计算魔方方块的组合数,在不论方块的方向时,就是计算方块的偶置换数。
在群论中证明了: n个元素所成的n!个置换(即全排列)中,奇偶置换各占一半,即奇偶置换各为 n!,故而8个角块所成的偶置换数为 个,12个边块所成的偶置换数为 个。
角块、边块之间的偶置换与偶置换的组合是偶置换,这种组合共有 个。
角块、边块之间的奇置换与奇置换的组合也是偶置换,这后一类偶置换也有 个。
以上两类偶置换数的和为:
再考虑到角块和边块的方向,则魔方方块的总组合数为:
顺带指出,魔方中方块的扭转和翻转也可以转化为纯粹的群论问题去进行处理,但不能像处理置换这样简洁和直接。对此,后面的附录有详细论证。
2004年12月11日21时51分电子版初稿
2007年2月19日星期一下午2时23分重修订完毕
【附录】
本书正文初稿在网上挂出后,有读者问:既然在第八章的结尾引用了置换群的知识来简化方块置换组合数的计算,那么群论能够处理方块的方向问题吗?本文将解答这一疑问,不过这要求读者拥有群论和向量代数的初步知识。
以下论述凡提及处,皆指全部角块已经归位的鲁毕克魔方。
在正文第四章(二)中,为处理角块的方向组合问题,我们在集合A={φ, T, -T}上定义了一个运算“+”(直接称为“加”、“加运算”)。容易看出,A中元素对于这一运算构成群,且此群是一个交换群和循环群。为便于进一步讨论,我们称此群为角的精细群或直接称为精细群,并将它记为E,按群论的常例表示为:
E = {A, +}
又称此群中的每一个元素ti (注意ti∈A)为一个精细值,精细值的运算仍沿用正文中状态值的“+”运算。
记定义于集合A上的任一n维(魔方的角块有8个,所以应是8维)向量为:
并记所有这样的向量的集合为B:
B = { b|b是定义在集合A上的n维向量 }
从魔方直观看,任意一个b =表示由组装或转动而得到的所有魔方角块的一种方向组合图案, 其中编号为i的那个角块的状态为ti ,ti取值的范围为集合A={φ, T, -T}。
任取B中的两个向量元素b1, b2:
b1 =
b2 =
现给出这两个元素之间加运算的定义如下。
定义1 b1 + b2 = +
=
此定义的魔方直观意义是:取两个方向图案未必相同但角块编号相同的魔方,把第一个魔方与第二个魔方中所有序号对应相等的角块的精细值(在正文中叫“状态值”)分别相加,其结果是唯一确定的一个魔方图案,这种图案的魔方也可以通过组装或转动而得到。
显见定义1与普通代数中向量加法的定义完全一致。我们知道在一般向量加法的定义中,等号两端加号的意义并不一样。定义1也是如此,其前两个加号表示两个魔方的角块按一定规则的虚拟叠合,后边尖括号中的加号则表示叠合的规则:相同编号的角块状态值(或精细值)相加。
定理1 向量集合B与定义1所确定的加运算构成一个群。
证明 (1)运算的封闭性显然。又B中必有这样一个元素Φ:
Φ = <φ,φ,…,φ> (尖括号中有n个φ)
此元素显然符合群单位元的要求。
(2)对于任意的b=∈B,总有另一个属于B的元素b’=<-t1,-t2,…,-tn >,使得
b + b’=
= <φ,φ,…,φ> = Φ
所以任一元素的逆元存在。
(3)按定义,集合B中向量的加运算,其实仅仅是对两个向量的对应分量分别相加,而每一个分量又是一个精细值,在正文第四章(二)中已证明精细值的加运算满足结合律,故而B中向量的加运算也一定满足结合律。这样,定理1完全得证。
我们称定理1所说的向量群为角方向组合群,或简称为角方向群、方向群。记此群为Cd:
Cd={B,定义1所确定的运算“+”}
自然,群Cd是一向量加群。
下来讨论Cd的性质。
定理2 Cd是交换群。
欲证此定理,可比照定理1证明结合律的思路,此处从略。
定义2 对Cd中的任一元素b=,称
S(b)=t1+t2+ … +tn
为b的精细值的和,或简称为精细和。它也就是正文所说的状态和。
定理3 Cd中任意两个元素:
b1=
b2=
相加结果的精细和,等于b1的精细和与b2的精细和的和。即:
S(b1+b2) = S(b1) + S(b2)
证明 b1 + b2 = +
=
故而,
S(b1 + b2) = S()
=(t1 + t21 )+(t2 + t22 )+…+(tn+ t2n)
=(t1 + t2 + … + tn) + (t21 + t22 +… + t2n)
= S(b1) + S(b2)
证毕。
易知,Cd中任一元素b的精细和的可能的取值,仅为集合A中的所有的三个元素:φ, T, -T。据此可以把Cd的集合B划分为互不相交的三个子集:
B0 = { b|S(b)=φ}
B1 = { b|S(b)=T }
B2 = { b|S(b)=-T}
B0为正文所说的组装正确、符合跷跷板原理的魔方角块的图案集合;B1和B2为组装错误从而不符合跷跷板原理的魔方角块的图案集合。
定理4 集合B0对向量的加运算构成群。
证明 因为B0是群Cd的集合B的子集,其运算的结合性是自然的。我们只须证明单位元和逆元的存在以及加运算的封闭性。
(1)∵ S(Φ)= φ(显见) ∴Φ∈B0
即集合B0包含单位元。
(2)若b=∈B0,则S(b)=φ。其逆元b’∈B为<-t1,-t2,…,-tn >,
∵ b’= b’+ Φ
∴ S(b’) = S(b’+ Φ)
= S(b’) + S(Φ)
= [(-t1)+(-t2)+ … +(-tn)]+φ
已知S(b)=φ,所以又有:
S(b’) = [(-t1)+(-t2)+ … +(-tn)]+ S(b)
= [(-t1)+(-t2)+ … +(-tn)]+[t1 + t2 + … + tn]
= φ
所以b的逆元b’也属于B0。
(3)对属于B0的任意两个元素b1和b2有
S(b1)=φ, S(b2)=φ
按照定理3有
S(b1+b2)= S(b1)+ S(b2)=φ+φ=φ
所以b1+b2也属于B0,即B0对于向量加运算保持封闭性。至此定理完全得证。
出于显见的理由,我们把B0与向量加法所构成的这个群称为角方向的跷跷板群或直接称为跷跷板群,并记为Ss:
Ss = { B0 , + }
自然,Ss是 Cd={B,+}的一个子群。
定理5 若b0∈B0,b1∈B1, b2∈B2,则
(ⅰ) b0+b1∈B1, b0+b2∈B2 ;
(ⅱ) b1+b2∈B0 。
证明 (1) ∵ S(b0+b1)=S(b0)+S(b1)=φ+T=T
∴ b0+b1∈B1
同理b0+b2∈B2 。
(2) ∵ S(b1+b2)=S(b1)+S(b2)=T+(-T)=φ
∴ b1+b2∈B0 。
定理5证毕。
现记任意集合R的元素个数为|R|,我们有如下的定理:
定理6 集合B0,B1,B2的元素个数都相等。即:
|B0|=|B1|=|B2|。
证明 取任一元素b1∈B1,分别与B0中所有的元素相加,则得到|B0|个互异的元素,按定理5(ⅰ),这些互异的元素都属于B1,
∴ |B0|≤|B1| ①
又任取一元素b2∈B2,分别与B1的所有元素相加,则得到|B1|个互异的元素,按定理5(ⅱ),这些互异的元素都属于B0,
∴ |B1|≤|B0| ②
综合①,②可知|B0|=|B1|;同理可知|B0|=|B2|。
∴ |B0|=|B1|=|B2|
证毕。
定理6的一个自然的推论是:角方向的跷跷板群的阶是角方向组合群的阶的三分之一,也就是:
|B0| = |B|
熟知定义于m个元素上的n维向量共有mn个,本例中,
m =|A|=|{φ, T, -T }|=3
又因为角方向组合群Cd的集合B是定义在A上的n维向量的集合,
∴ |B|=3n
∴ |B0| = |B| = ·3n = 3n - 1
又知在鲁毕克魔方中n=8,故组装正确且已全部归位的魔方角块的图案共有38 - 1=37种。
可以把本文中精细群E的集合A={φ,T,-T }推广到任意m个元素的集合Am ={T0,T1,T2,…,Tm - 1}上。这样的推广至少有两个好处:第一,当m=2时,所得的方向群可用于描述边块的状态,这意味着边块和角块的状态在群论中可得到统一的描述;第二,如果存在某种异形魔方,其角块不止8个,角块的状态也不止3种,仍然可以用推广后的方向群来描述。不过本文已经不适合进行这样的推广了。
本书的初稿现仍挂于魔方吧(http://www.mf8.com.cn/)/魔方教室,署名为rongduo。主要由于技术原因,网页上多有文字和格式上的错误。
这次修订以自留的初稿底本为基础,除了改正笔误、调整版式外,在论述内容上有少量的添加,文字亦略有润色。
新增的附录此前亦已发表于魔方吧/论坛(术语略有不同),为方便有兴趣的读者阅读,特刊于此。
魔方吧的网友乌木先生曾指出了本书以前存在的几处文字错误和表述疏漏,特予致谢。
2007年2月19日
[ 注 ] 本书正文末尾一节稍微提到了群论,但只是把它作为一个例子。没有这个例子完全不影响本书的完整性,而例子本身也很容易读懂。
[ 注 ] 除了运用程序P10可开解以外,又可以令已归位的那个边块所在的竖直面为前平面,运用另一种程序:
P11(下边块定位程序又) R-, D-, R+, D+, L+, D+, L-, D2, R-, D+, R+, D+, L+, D-, L-
P11虽然较P10多了一次转动,但其转动的对称性极强,不像P10那样令人眼花缭乱。和P10一样,P11有时也需要连用两次。
[ 注 ] 需要注意:第一,相邻轮换无法进行这样的转化,不管魔方怎样放置,人眼所见的顺时针的轮换都不会变成逆时针;第二,本结论的前提是只考虑轮换路径的几何形状而不计参加轮换的方块的不同颜色,后文计算魔方的组合数时我们将会看到,本段所提及的所有“8”字轮换可能属于不同的组合,因为组合计算必须考虑方块的不同颜色。
[注1] 这种一一对应关系有两个。记边块当前的两个方向状态为x和y,则两个一一对应关系分别为:
f1: x←→φ, y←→T
f2: x←→T , y←→φ
[注2] 在选用一一对应关系时,可以结合魔方图案考虑一下所选用的一种是否比另一种更为熨贴自然,但这种考虑不是必需的。
[注1] 也可以仅仅是两个角块的对换,但为了和前面开解法的顺序一致,这里我们选择了边块。
[注2] 有时候,下边块至此尚未完全归位,这时可以运用第二章(五)(乙)所给的开解法使之完全归位。在第二章已知这并不影响下角块的既有状态。
[注] 也可以用排列知识来证明。
前言 - 1 -
第一章 预备知识 - 2 -
(一) 魔方的结构 - 2 -
(二) 术语记号 - 2 -
(三) 程序、对称程序与逆程序 - 3 -
第二章 开解法 - 5 -
(一) 上边块 - 5 -
(二) 上角块 - 5 -
(三) 中边块 - 6 -
(四) 下角块 - 7 -
(五) 下边块 - 9 -
第三章 开解法证明(Ⅰ) - 11 -
(一) 上层和中层开解法的完备性 - 11 -
(二) 置换概念初步 - 11 -
(三) 下角块定位开解法的完备性 - 13 -
第四章 开解法证明(Ⅱ) - 15 -
(一) 跷跷板原理 - 15 -
(二) 扭转代数 - 16 -
(三) 下角块定向开解法的完备性 - 17 -
第五章 开解法证明(Ⅲ) - 20 -
(一) 翻转代数与下边块定向开解法的完备性 - 20 -
(二)置换代数 - 20 -
(三)下边块定位开解法的完备性 - 21 -
第六章 方块的空间状态暨魔方表示定理 - 23 -
(一) 方块的空间状态 - 23 -
(二) 魔方表示定理 - 25 -
第七章 几个重要的计数公式 - 27 -
(一) 轮换的计数公式 - 27 -
(二) 方块平均分组 - 28 -
(三) 平均分组下的置换计数公式 - 29 -
(四) 表达式※的推导 - 30 -
第八章 魔方组合计数 - 32 -
(一) 方块的方向组合数 - 32 -
(二) 角块的置换组合数 - 33 -
(三) 边块的置换组合数 - 34 -
(四) 魔方方块的总组合数 - 36 -
(五) 总组合数的另外两种计算法 - 36 -
【附 录】魔方角块方向问题的群论模型 - 38 -
修订后记 - 43 -
前言
关于魔方的书并不很多,我所见到的极为有限的几种,其主题都是魔方的玩法或开解法。至于魔方的组合原理,在这些书中或者只有只言片语,或者只是一种雾里赏花式的漫谈。不过它们都说:要真正理解魔方,必须懂得一门高深的数学,叫作什么“群论”(怪怪的名字!)。
本书则不然。首先,它以魔方的组合原理为主题,所给的开解法(虽然可能特别适合于初学者)只是主题开展过程中的一个环节;其次,它尽可能追求系统性和严密性,而不满足于漫谈;最后但也可能最重要的是,它不需要“群论”[注]!凡是学习过中学数学中排列组合知识的人,都可以完全地读懂本书的正文部分。
跷跷板原理构成了本书的主线和理论基础。或许正是因为有了跷跷板原理,才使我们得以绕开一些过于抽象的代数知识,对魔方方块那令人眩晕、烦心的组合作出了澄明透彻的解释与刻划。我希望,这一原理能使本书有别于其它所有同类的书。
我还真诚地希望,每一个魔方玩家和中学生都能够赏玩这本书。
最后补充说明两点:一是现在魔方种类很多,本书所讨论的仅限于由三层共26个小方块构成的那一种,即最原始的鲁毕克魔方( 详见本书第一章(一) );此外,对目前一些魔方玩家热心探究的魔方中心块的方向问题,本书按既定体例不予涉及。
魔方是由其六个平面中央的6个方块(称为中心块)、每三个平面交会所成角位置上的8个方块(称为角块)以及各平面边缘位置上的12个方块(称为边块)计26个方块组成(图1)。转动任意一个平面(90°,-90°,180°,360°等),该平面的中心块保持不变,而4个角块和4个边块则发生旋转移动。通过选取适当的平面进行转动,可以使一个角块取代任意另一个角块的位置,一个边块也可以取代任意另一个边块的位置;在这一过程中,每一方块上各面(为一些小正方形)的朝向也随之发生变化。要复原一个混乱的魔方,则必须注意到任何一个可转动方块只适合于一个位置。例如,白绿色边块(每个边块有两种颜色)只能适合白色和绿色平面之间的边缘位置。而一个平面的颜色,是由那个平面上固定的中心块的颜色来决定的。再如,同时染着红色、蓝色和白色的角块(每个角块有三种颜色),其位置应在交会红色、蓝色和白色三个平面的那个角上。一个方块被安放在它应在的那个位置,可以称为位置正确或已归位。当一个方块不但位置正确,而且它的各面的颜色分别和所在平面的中心块的颜色相一致时,我们便说它位向正确或已归位定向。如果因位置不正确而导致一个方块仅有一个面的方向正确,则称此方块对该面已定向。一个被打乱的魔方当其每一个可动方块都已归位定向时,魔方的开解即告完成。
1.约定魔方六个平面的名称如下:
上(U):上平面(任意选一种你喜爱的颜色)
下(D):下平面
前(F):前平面 后(B):后平面
左(L):左平面 右(R):右平面
以后我们将用上面括号中的字母去代替括号前面的字。上平面是在开解前任意选定的,选定后在整个开解过程中必须保持不变,从而下平面也将保持不变。前平面根据被打乱魔方的图案在四个竖直面中临时选定,而在开解中又常常需要改选新的前平面,所以它可以是四种颜色之一。每选定或改选一次前平面,左平面、右平面和后平面也就随之而定。
2.对各平面进行转动的记法是:
U+:把上平面按顺时针方向转动90°
U-:把上平面按逆时针方向转动90°
U2:把上平面转动180°
D+:把下平面按顺时针方向转动90°
D-:把下平面按逆时针方向转动90°
D2:把下平面转动180°
F+:把前平面按顺时针方向转动90°
F-:把前平面按逆时针方向转动90°
F2:把前平面转动180°
B+:把后平面按顺时针方向转动90°
B-:把后平面按逆时针方向转动90°
B2:把后平面转动180°
L+:把左平面按顺时针方向转动90°
L-:把左平面按逆时针方向转动90°
L2:把左平面转动180°
R+:把右平面按顺时针方向转动90°
R-:把右平面按逆时针方向转动90°
R2:把右平面转动180°
3.称现在位于右平面和前平面之间的一个边块为右前;称现在位于右平面、前平面和上平面之间顶角上的那个角块为右前上。以此类推,十二个位置上的边块分别称为:
前下、后下、左下、右下、
左前、右前、左后、右后、
左上、右上、前上、后上。
八个位置上的角块分别称为:
左前下、右前下、左后下、右后下、
左前上、右前上、左后上、右后上。
在本书中,任何转动及其所涉及的的方块一律用上述术语或记号表示。此外,要使用本书的开解法,你必须按一定方向持握魔方,使将要予以变动的方块与文中所述的情形相一致。例如,你希望安放一个后上角块,但说明中提供的是一组安放一个前上角块的转动,那么,你就必须整体转动魔方使所考虑的后上变为前上。其余可类推。
为节省时间,你可以跳过本节径直去阅读后边的第二章,等在第二章学会了基本的开解方法以后,如有必要,再回头阅读本节。以下是本节的内容。
1.本书中所说程序是指可以运用于魔方的一组预定的(而不是随意的)转动。某些程序可能只包含一个转动,但更多的程序则包含有多个转动。
2.对如下的转动程序:
P0 L+,R-,F-,D2
可以构造另一个程序:
R-,L+,F+,D2
我们把程序 称为P0的对称程序,其代号“ ” 可以读作“对称P0”。此时,又可以把P0称为原程序。一般地,对于一个原程序Pi ,把它所包含的每一个转动都换成一个与之对称的转动,我们就得到了它的对称程序 。求一个转动的对称转动的规则是:
前后上下面不变,左右面互变;
数字2不变,正负号互变。
比如,按照上述规则的第二句和第四句,我们可以确定L+的对称转动是R-;按照规则第一句和第三句,可以确定U2的对称转动还是U2。此外,我们还可以确定R2的对称转动是L2,D+的对称转动是D-,如此等等。
3.像每一个程序都有它的对称程序一样,对每一个程序Pi,我们还可以构造出它的逆程序 (读作“逆Pi”)。构造的方法是:先由Pi求出 ,再把 中所有转动的先后顺序倒过来重新排列,即把 中的倒数第一个转动现在排为第一个转动,倒数第二个转动排为第二个转动,如此继续下去,直到把 中的第二个转动排为倒数第二个转动、第一个转动排为倒数第一个转动为止。这样所得的新程序即为原程序Pi的逆程序 (注意: 并不是 的逆程序)。以前面所给的程序P0为例,其逆程序为:
D2,F+,L+,R-
逆程序是相对于原程序而言的。在对魔方运用了一个程序以后,再运用一次这个程序的逆程序,就可以使魔方恢复原状。如果把原程序比喻为“向前走去”,那么逆程序就相当于“按原路倒退着走回”。
开解法
从直观上看,魔方的全部方块可以按上、中、下分为三层。上平面的方块构成上层,前、后、左、右四个平面上的中心块以及四个中边块构成中层,下平面的方块构成下层。本章所给开解法的总思路是由上到下,逐层给各个可转动方块归位定向。这一过程又可以依次分为六个较小的环节:①上边块的归位定向;②上角块的归位定向;③中边块的归位定向;④下角块的归位;⑤下角块的定向;⑥下边块的归位定向。
应归位于上平面的四个边块总称上边块。上边块的归位定向在六环节中是最容易的。本节将要介绍的方法主要是面向初次接触魔方的读者。它比较呆板,但却能有效地预防某些常见的错误。读者不妨依据这些提示进行最初的演练,但在稍微熟练后就不必再去理会那一大堆谨小慎微的玩意儿——你尽可以灵活地去选择那些合目的的转动。
动手开解前,先任意确定一个平面为上平面。在上一章已经指出,上平面一旦确定,在以后的整个开解过程中是不宜变动的。
⒈选定一个竖直面为前平面,使前上部位并无已经归位而且定向的方块(你可能必须在手中整个地转动魔方才能做到这一点,这样,必然地会使前平面发生变换)。接下来,在魔方中寻找出应属于这个前上部位的边块.
⒉这个边块也许恰巧就在前上,只是未曾定向,请作如下转动:F+, U-, R+, U+。
⒊如果所寻的边块在下平面,可以适当转动(有时不需要转动)下平面,使该边块位于前下。这时进行观察(而不是立即转动),看是否可以将前平面转动180°而使这一边块既归位又定向。如果可以,那么转动180°以后问题就得到了解决。如果察知转动180°以后还不能定向,可改作如下的转动(注意,此时所论的那个边块还位于前下):F-, U-, R+, U+。
⒋如果所寻的边块在前平面的中层,观察(而不是立即转动)是否可以把前平面转动90°或-90°使这一边块归位而且定向。如果可以,则转动后问题得到解决。如果察知仅仅能归位而不能定向,则选做如下的转动。
① 所寻方块位于右前时:U-, R+, U+。
② 所寻方块位于左前时,使用上一程序的对称程序:U+, L-, U-。
⒌所寻的方块位于后平面的中层时,可以选用如下的程序将该边块移至前下。
①所寻方块在右后:R+, D-, R-。
②所寻方块在左后,运用上一程序的对称程序: L-, D+, L+。
然后返回步骤3。
⒍所寻的方块在上平面前上以外的位置上,可将其所在的竖直面(左平面、右平面、或后平面)转动180°,使该边块移至下平面,然后返回步骤3。
由于四个上边块是逐一归位定向的,因此可能需要反复运用以上的六个步骤,直到四个上边块全部归位定向。
本节的目的是使属于上平面的四个角块——上角块归位定向。在后面所给的一系列的转动中,已安放好的四个上边块可能会被被暂时移动,但最终都会自动还原。
1.选定一个竖直面为前平面,在这个前平面的右前上位置并无已经归位而且定向的方块。接下来,在魔方中寻找应属于右前上位置的角块。
2.如果所寻的角块位于下平面,可适当转动(有时不需转动)下平面,使该角块位于右前下(与右前上在同一竖直线上),并注意观察构成该角块的三个小正方形染着(“着”读zhuó)的三种颜色。
①该角块染着上平面颜色的那个小正方形位于前平面时(见图2①),请选用下列程序(二者任选其一)。
P1 (上角块归位定向程序) F+, D+, F-
P1’ D-, R-, D+, R+
[插图说明] i ) 为了方便,本书在举例时总是假定:上平面红色、前平面蓝色、左平面白色、右平面黄色、后平面绿色、下平面土黄色(图④显示了后平面和下平面)。应注意实际开解不一定是这样。 ii ) 图中的灰色表示不确定的颜色。
②如果所论的角块染着上平面颜色的那个小正方形位于右平面(见图2②),可运用如下的程序:
P2(上角块归位定向程序又) R-, D-, R+
③如果所论角块染着上平面颜色的那个面位于下平面(见图2③),运用如下的程序:
P3(上角块归位定向程序又) F+, L+, D2, L-, F-
3.如果属于右前上位置的那个角块已经归位,但方向不对,此时可运用程序“R-, D-, R+”将其移到下平面,然后返回2。
4.如果属于右前上位置的角块现在位于左前上,或右后上,或左后上,可按照提示适当选用下列程序将其移至下平面:
① 所论角块在左前上:L+, D+, L-
② 所论角块在右后上:R+, D-, R-
③ 所论角块在左后上:L-, D2, L+
然后返回2。
和上边块的情形一样,四个上角块也是逐一进行归位和定向的,因此可能需要反复运用上述1至4所提供的方案。
中边块是指应属于魔方中层的四个边块。开解前,未归位和定向的那些中边块可能位于魔方的下平面,也可能位于中层。开解时,须依循以下的方案逐块进行。
1.考虑位于魔方下平面的一个中边块的归位和定向,先观察该边块竖直面的颜色,然后适当转动(有时不需要转动)下平面,使得该竖直面位于颜色相同的那个中层中心块的正下方,并定这一中心块所在的平面为前平面。接下来,对准备归位定向的中心块(现在位于前下),按其位于下平面的那个小正方形的颜色,判定其应归位于右前还是左前。
2.如果所论的中边块应归位于右前(见图3①),请运用如下程序:
P4(中边块归位定向程序)D-, R-, D+, R+, F-, R+, F+, R- (8次转动)
如果所论中边块应归位于左前(见图3②),请运用P4的对称程序:
D+, L+, D-, L-, F+, L-, F-, L+
3.如果未曾归位、或已经归位但未定向的中边块位于魔方的中层,则无论是中层的哪一个位置,都可以通过适当选择前平面,使该边块现在的位置为右前,进而运用以下程序将它移至下平面:
P5(右前至下平面换位程序) F+, D-, F-, D-, R-, D+,R+ (7次转动)
然后返回1。
下角块自然指应位于下平面的四个角块。流行的开解顺序是先定位,后定向。这种顺序比较合理(但仍然存在着相反的顺序和一次性定位定向的程序,此类“高级开解”问题本书不予讨论),本节将依循这一顺序给出具体的开解方案。
(甲)定位
1.中层开解完毕后,适当转动(有时不需要转动)下平面,就可以使至少两个、甚至是四个下角块全部归位。
2.如果两个位置不对的下角块相邻,可令二者所在的竖直面为左平面,然后运用以下程序:
P6(下角块定位程序) R-, D+, L+, D-, R+, D+, L-, D2
3.如果两个位置不对的下角块不相邻(即处于下平面的一对对角上),可选任意一个竖直面为前平面,运用如下的程序:
P7(下角块定位程序又) F+, D+, L+, D-, L-, F-
然后适当转动(有时不需要转动)下平面,就可以使四个下角块全部归位。
(乙)定向
归位后四个下角块的方向或者完全正确,或者在下平面形成如图4(①—⑦)中的某一个图案。下文将给出两套开解方案,读者可任选其一。
第一方案——
1.观察魔方的下平面,适当整体转动(有时不需要转动)魔方,使下平面与图4中的某一个图案相吻合。
2.如果魔方的下平面如图案①,可运用如下的程序:
P8(下角块定向程序) R-, D-, R+, D-, R-, D2, R+, D2 (8次转动)
3.如果魔方的下平面如图案②,可运用P8的对称程序:
L+,D+, L-, D+, L+, D2, L-, D2
4.我们把图案①和②称为标准化图案,图案③至⑦称为非标准化图案。魔方的下平面如果是一个非标准化的图案,那么对这图案运用一次P8,然后返回1。
第二方案——
第一方案需要反复进行图案的核对,而核对有时既不方便(比如你给别人表演开解时),又容易出错。为此,特提供第二方案。第二方案只要求记牢图4中的标准化图案①和②(包括二者对前平面的选择),魔方出现这两种图案时,仍按第一方案中的2或3处理。如果魔方出现的是非标准化图案(对应于图案③至⑦中的某一个),你可以随意选一个竖直面为前平面(不需要与图4核对),先运用一次程序P8,完毕观察下平面是否标准化(注意,标准化图案最显著的特征是:只有一个下角块方向正确);如果没有,则沿用上一步选定的前平面,再运用一次P8的对称程序 ,再观察下平面是否标准化……,如此交替运用P8和 ,直到下平面达到标准化为止。此后,按第一方案中的2或3去处理。比如,对于图案④,假如你无意中将图4规定的后平面取成了前平面,那么你只须如此运用P8和 共三次:
P8→ →P8
就可以使图案④标准化为图案①。
正确的位置在下平面的四个边块统称下边块。下边块的开解是魔方开解的最后一道工序。我们的开解思路是:先考虑四个边块对下平面的定向问题,待这一问题得到解决后再考虑定位问题。现分述如下。
(甲)对下平面定向
一个方块对一个平面的定向问题在第一章(一)的结尾已经提说过。现在所说的对下平面的定向,具体是指对已经位于下平面的四个下边块,不管其位置是否正确,先使它们居于下平面的那些小正方形的颜色与下平面中心块相一致。或者说,现在就是要让下平面只有一种颜色。
1.开解前,我们所希望的下平面颜色一致的情形或许已经自动形成。如果不是这样,那么和中心块颜色不一致的小正方形(下边块的一个面)或者是两个,或者是四个。
2.如果这样的小正方形是两个,那么下平面可能呈现的图案将如图5所示(也许需要适当整体转动魔方,才能使它与图5中的某一个图案相一致)。
3.如果魔方的图案如图5①,请运用如下程序:
P9(下边块定向程序) R-, D-, R+, D+, R+, L-, F-, R-, F+, L+ (10次转动)
如果如果魔方的图案如图5②,则可运用P9的逆程序:
L-, F-, R+, F+, L+, R-, D-, R-, D+, R+
4.如果下平面中与中心块颜色不一致的小正方形有四个,则可以令魔方的任意一个竖直面为前平面,运用3中的程序P9,将下平面的图案转化为图5②,然后返回3。
(乙) 定位
完成了对下平面的定向以后,四个下边块或者已经全部归位,或者仅有一个归位,或者全部没有归位。
1.如果四个下边块仅有一个归位,可令已归位的那个边块所在的竖直面为右平面,运用如下的程序:
P10(下边块定位程序) F+, D+, L+, D-, L-, F-, D2, F-, R-,D-, R+, D+, F+, D2 (共14次转动)
如果运用后仍有三个边块没有归位,那么再运用一次P10,必使魔方获得彻底的开解[注]。
2.如果四个下边块全部没有归位,可任选一个竖直面为前平面,运用一次1中的程序P10后,必有一个边块归位。然后返回1。
开解法证明(Ⅰ)
第二章介绍六步开解法时,对每一步骤我们都估计了所涉方块在开解前可能的状态,进而针对所估计的状态给出了行之有效的开解方案。现在的问题是:我们是否已经充分估计了所涉方块所有可能的状态?或者说,是否存在某些图案,使我们所给的开解方案显得文不对题?如果我们认为所作的估计是充分的,所给的开解方案在任何时候都不会失效,则必须给出证明。可以把需要给出的证明称为完备性证明,即证明所给的开解方案对于魔方中一切实际可能的图案来说是足够的,或者说是完备的。
先考察第二章(一)对上边块的开解。一个被打乱的魔方,其任意一个上边块在逻辑上只能属于如下三类状态中的一类:
(i )位向正确;(ii)位置正确而方向不正确;(iii)位置不正确(不论方向)。
类状态(i)不论。对于后两类状态,我们当时针对其在逻辑上可能的子类,分别给出了有效的开解法。如该章节开解步骤2所针对的就是这里的状态(ii)。关于类状态(iii),一个上边块的位置不正确,在逻辑上它只能出现在魔方上中下三层共11个位置的某一个位置上。如果出现在下层,按该章节步骤3可予开解;如果出现在中层(共有四个可能的位置),按步骤4,5可予开解;如果出现在上层(共有3个可能的位置),按步骤6可予开解。通过如此的的讨论,事实上我们就证明了如下的命题:
第二章(一)所给的魔方上边块的开解方案是完备的。
如本章开头所说,这里的“完备”一词与“足够”同义。
依照上述思考方法,读者不难自行证出如下两个命题:
第二章(二)所给的魔方上角块的开解方案是完备的。
第二章(三)所给的魔方中边块的开解方案是完备的。
如此就完成了魔方上中层开解法完备性的证明。
在上述证明中,我们从逻辑上穷尽了所涉方块可能有的位向状态,由此证明的完备性又可以称为逻辑的完备性。
一个方块取代另一个方块的位置,这在魔方上是常见的,我们把这种现象称为置换。如果通过某些转动,使魔方上的方块a从原位移到方块b的位置(此时b又被移到了其它位置),我们就说a置换了b,或b被a所置换。很显然,置换只能发生在同类方块之间。
最基本的置换是对换:如果在a置换b的同时,b也置换a,则称a和b发生了一次对换。简单一点说, a和b互换位置就构成一个对换。
另一类重要的置换是轮换。如果a置换b,b置换c,c又置换a,则称三个方块a,b,c发生了一次轮换,记为(abc)。如若这三个方块正好在魔方的同一平面上,则相应的轮换按方向又可以分为顺时针轮换和逆时针轮换两种。
四个或四个以上方块轮换的定义可仿照三个方块轮换的定义给出:设有n个方块a1,a2,…,an,若a1置换了a2,a2置换了a3,…,an-1置换了an,an又置换了 a1,则称这n个方块发生了一次轮换,记为(a1a2…an)。
魔方某一平面上四个方块的轮换可以分为两类。如果四个方块中的每一个都按一定的方向置换自己的相邻块,则称如此的轮换为为相邻轮换。相邻轮换又可以按方向分为顺时针轮换和逆时针轮换两种。
平面上四个方块的另一类轮换称为“8”字轮换。在这种轮换中,任意一个方块若置换它的相对块,则它自身被一个相邻块所置换;反之,如果这方块置换它的一个相邻块,则它自身被一个相对块所置换。由于这类轮换发生在四个角块时移动路径的图形为“ ”或“ ”,发生在四个边块时移动路径的图形为“ ”或“ ”,故因其形象而被我们命名为“8”字轮换。
对于下角块的“8”字轮换中平卧的图形“ ”,只须将魔方整体转动90°(以上下中心块的连线为轴),该图形即变为直立的“8”字图案“ ”。又方块沿“8”字“笔画”的运动似乎有两个方向,如图9所示。
不妨假定图9①所示的方向为正,图9② 所示的方向为负,然后请读者把这本书倒转过来(从而使这一页的字全部倒立),你会看到图9①的方向由正变成了负,图9②的方向由负变成了正。由此可见两个图形所以看似不同,是因为魔方放置的方向(或读者的视向)不同。调整放置方向,一个图形就会完全地变成另一个。它表明下角块的“8”字轮换在我们目前的的讨论中其实只有一种[ 注 ]。以后讨论这种轮换时,除非必要,我们将只采用图9①。(显然,以上结论原则上也适用于斜“8”字轮换,即在不计方块的颜色时,下边块的斜“8”字轮换其实也只有一种)。
下来我们引入魔方平面(下平面)方块置换的示意图。记魔方左前下位置为A,右前下位置为B,右后下位置为C,左后下位置为D;依次记应属于这四个位置的方块为a,b,c,d,且依次分别称A,B,C,D为a,b,c,d的本位。若四个方块的位置正确,则其置换(为零置换,即所有方块不动的那个“置换” )的示意图为图10①。
如果此时发生了轮换(bcd),则图10①转化为图10②。如若再对图10②施行相邻轮换(adbc),则可使图10②转化为图10③。
由图10③可看出,依次对图10①施行两个轮换(bcd)和(adbc),相当于对图10①施行了(abdc)这一个轮换。而后一轮换正是“8”字轮换。类似地,我们可以给出下平面四个边块的置换示意图。比如应属于前下A'和后下B'的两个位置的方块a'和b'由本位发生对换,其示意图为图11。
在第二章(四)(甲)中我们指出,魔方上中层开解完毕后,适当转动(有时不须转动)下平面,下角块的位置状况总可以归结为如下三类情形中的一种:
(i ) 四个下角块已全部归位;
(ii) 仅有两个相邻下角块相对于本位发生对换;
(iii) 仅有两个相对下角块相对于本位发生对换。
对于后两类待解情形,我们当时给出了有效的定位开解方法,现在证明所给开解方法的完备性。
证明的思路是,逻辑地考虑四个下角块每一种可能的位置状态,对于不属于上述情形(i ) (ii) (iii)中的那些状态,指出如何转动下平面,使之化归为(i ) (ii) (iii)中的某一类,从而证明所给开解法的完备性。
【证明】⒈四个下角块皆未归位,此类状态分为四种情况。
(1)四个角块相对于本位呈现顺时针(或逆时针)相邻轮换,此时只须将下平面逆时针(或顺时针)转动90°,则转化为前述的情形(i )。其过程显然。
(2)四个下角块相对于本位呈现“8”字轮换,只须将下平面转动180°,则转化为情形(ii)。如图12所示。
(3)相邻角块相对于本位两两对换,可将下平面不论方向转动90度,则转化为情形(iii)。如图13所示。
(4)相对角块相对于本位两两对换,可将下平面转动180°,则转化为情形(i)。置换示意图略。
⒉仅有一个下角块归位,则其余三个角块必相对于原位呈现顺时针或逆时针轮换,如将下平面逆时针(或顺时针)转动90°,可转化为情形(ii)。图14显示了三个角块呈顺时针轮换时转化的情景。
⒊仅有两个下角块归位,正好是情形(ii)或情形(iii)。
⒋逻辑上不存在三个下角块已经归位而一个下角块仍未归位这种状态。
至此,下角块定位开解法的完备性得证。事实上,这里的完备性也是一种逻辑的完备性。
开解法证明(Ⅱ)
魔方是高度对称的机械。三类方块——中心块、边块和角块中的每一个方块,都和任意一个同类方块形成一定的对称关系。这些对称关系或隐或显,但却始终地、必然地制约着魔方图案的变化。即使是一个被彻底打乱的魔方,其图案也存在着严整的对称性(虽然常常不易察觉)。对称性是把握魔方奥秘的钥匙。
在魔方众多的对称性中,有一种最值得注意,我们把它称为跷跷板原理,并作为以后证明的公设。
跷跷板原理 对呈现于魔方的每一基本状态,在同一魔方上必然同时呈现出另外一些可以与之相互抵消的状态。
原理中所说的基本状态包括:
(i)零状态。 指一个位置或方向正确的方块的状态。它分为位置的零状态和方向的零状态。方向的零状态又分指两种情形:一是位向正确的方块的方向状态;另一种是,在魔方的上、下平面,不管一个方块是否归位,只要这方块对上平面或下平面已定向(参见第一章(一)的结尾文字),我们也说这方块的方向状态为零状态。借用代数方法,我们规定所有的零状态具有相同的状态值,这个值记为φ。
至于强调“上、下平面”,其用意到第六章自明。
(ii)一个角块的扭转。
(iii)两个同类方块的对换。
(iv)一个边块的翻转。
跷跷板原理是从跷跷板的运动悟出来的。跷跷板运动的基本特点是,两端运动者的起落状态总是相互抵消,一个运动者上跷一尺,另一个运动者必然同时下落一尺,二者位移的和等于零。魔方的结构、转动与跷跷板很相似,只不过更为复杂,状态间相互抵消的性质不像跷跷板那样一目了然。所谓“相互抵消”,其直观的含义主要是指一个非零的基本状态不可能在魔方上单独出现,它必然与另一些非零的状态相伴生,共同体现和满足魔方的机械结构与性能。
为了精准地凸显状态间相互抵消的关系,需要借助于数学方法。拟采用的数学方法的大义可叙述如下:
第一,给每一基本状态作一个记号,把这记号看成是这一状态的值。比如我们已经把零状态的值记为φ。
第二,给出几种类似于加法的运算并采用加法符号“+”,将某些同时出现的基本状态的值相加;如果按运算的定义相加的和恰好等于零状态的值φ(即各状态相互抵消),则我们说由这些基本状态组成的图案符合跷跷板原理,否则说图案不符合跷跷板原理。
第三,用上一步运算和判别的结果为论据,证明第二章所给的下角块定向开解法以及下边块定位、定向开解法的完备性。
下来我们对以上的方法作些初步的例说。为叙述方便,我们把可与一种基本状态相互抵消的状态称为这种基本状态的逆状态。按跷跷板原理,零状态也应有自己的逆状态,规定零状态的逆状态是它自身;后文将证明:
φ+φ=φ
又设X为某一基本状态的值,我们将指出:
X+φ=X
此外,在一个已开解的魔方上,所有方块的位向状态的值均为φ,设共有n个φ值,由等式φ+φ=φ可得:
φ+φ+…+φ=φ (等号左边共有n个φ相加)
此式意味着已开解魔方的图案也符合跷跷板原理。
易知一个角块由三个两两相交的小正方形构成。如果角块的位置不变,而三个小正方形发生了一次轮换,即第一个小正方形置换第二个小正方形,第二个小正方形置换第三个小正方形,第三个小正方形又置换第一个小正方形,我们就称该角块发生了一次扭转。扭转的方向按小正方形轮换的方向可以分为顺时针和逆时针两种。一个扭转变换,顺时针时记其状态值为S,逆时针时记其状态值为-S。通过观察可知,一个零状态角块顺时针扭转两次所成的图案,相当于这角块逆时针扭转一次所成的图案,故可以定义如下的加法运算:
S+S=-S ①
同理又有:
-S+(-S)=S ②
又因为一个零状态角块顺时针扭转一次再逆时针扭转一次,则角块方向复原,故可以定义:
S+(-S)=φ ③
同理又可定义:
-S+S=φ ④
此外,在第三章(二)我们曾提及置换。置换、扭转及后文将要考察的翻转可以统称为变换。可以改变魔方当前图案的那些变换称为非零变换。但在对魔方进行数学描述时,还必须用到零变换这一概念。我们把保持魔方的当前图案不变也看成是一种变换,并称之为零变换。教师在教室里对学生发出的“不准调位”的指令,是零变换的另一个现实模型。虽然我们将在不同的场合把零变换分别称为零扭转、零置换或零翻转,但这后三种“具体化”的零变换彼此并无实质的不同:它们都不会改变魔方任意既有的图案。基于这一原因,我们把所有的零变换或零状态不加区别地统统记为φ。
上一节所说方块的状态(或基本状态)其实可以看成是对方块施行一个变换(包括零变换)的结果。
一个方块的状态X0是相对于某一静止时刻而言的。对X0施行一个动态的变换X1(通过某些转动)后,X0变成另一状态X2。这一过程可用加法表示为:
X0+ X1= X2
与通常加法不同的是,这里不是数值的加法而是方块图案的“加法”。普通加法中的加数、被加数与和只能属于同一类型的数(在计算机的算法中尤其注重这一点),类比之下,方块图案加法中的X0,X1,X2也应属于同一类型的“值”。虽然,我们把X0和X2称为“状态”,把X1称为“变换”,但它们却都是图案加法数域中的元素。在以后的讨论中,一般我们将忽略“状态”和“变换”二者之间的自然语义的差别,只是把它们看作同一类型的值,可以自由地对它们进行图案加法的运算。此外,我们还将把图案的加法径直称为加法。
现记一扭转(可以是顺时针、逆时针或零扭转)的值为X(X可以是S,-S或φ),如果在这一扭转发生之前或之后,角块“发生”了一次零扭转,则这一扭转与零扭转的变换值的和可以记为φ+X或X+φ。但按照零扭转的意义,一个角块在一个扭转之前或之后保持不动,一旦该扭转发生,则角块的状态仍然会是这一扭转所导致的结果,故有:
φ+X= X ⑤
X+φ= X ⑥
作为特例,我们有:
φ+φ=φ ⑦
代数式①至⑥是魔方实验的记录,现以此作为出发点,推导“+”运算的交换律和结合律。
(i)交换律
证明交换律,就是要证明S和-S、S和φ、-S和φ这三对元素关于“+”运算的可交换性。
事实上,③式和④式共同显示了S和-S的可交换性;⑤式与⑥式显示了φ与任意扭转值X的可交换性。运算的交换律于是得证。
(ii)结合律
可供我们运算的仅有的三个元素为S,-S和φ,我们可以三个三个地任意选取这三个元素并组成的连加式,比如如下的式子:
-S +S+φ
S +S+(-S)
S+(-S)+ S
根据排列论,诸如这样的式子共有33=27个,这27个式子是:
⑴φ+φ+φ
⑵φ+φ+(-S)
⑶φ+φ+S
⑷φ+(-S)+φ
⑸φ+(-S)+ (-S)
⑹φ+(-S) +S
⑺φ+S+φ
⑻φ+S+(-S)
⑼φ+S+S
⑽-S +φ+φ
⑾-S +φ+(-S)
⑿-S +φ+S
⒀-S+(-S) +φ
⒁-S +(-S) +(-S)
⒂-S +(-S) +S
⒃-S +S+φ
⒄-S +S+(-S)
⒅-S +S+S
⒆S+φ+φ
⒇S+φ+(-S)
(21)S+φ+S
(22)S+(-S) +φ
(23)S+(-S) +(-S)
(24)S+(-S) +S
(25)S+S+φ
(26)S+S+(-S)
(27)S+S+S
我们可以逐个地来证明这27个式子都满足结合律,比如⒃式:
∵-S+S+φ=φ+φ=φ
-S+(S+φ)=-S+S=φ
∴-S+S+φ=-S+(S+φ)
又比如(26)式:
∵S+ S+(-S)=-S+(-S)= S
S+( S+(-S))= S+φ=S
∴S +S+(-S)= S+( S+(-S))
对所有的式子都进行如上的检验将是冗长乏味的,但如果我们进行了这样的检验,就会发现运算的结合律确实成立。
以上所讨论的“+”运算共有S,-S,φ三个元素,这些元素连同算式①,②,③,④,⑤,⑥,我们称之为扭转代数。而此代数中交换律、结合律和⑤,⑥,⑦式在后续的置换代数和翻转代数中仍然对应成立,届时将径直运用而不再予以推导。
按本书第二章(四)(乙),在完成定位开解后,魔方四个下角块的方向或者完全正确,或者呈现如图4所示的图案。而那些图案皆可以采用扭转代数予以描述。
运用扭转代数,容易验证图4中各图案之未定向下角块的状态值的和皆等于零状态值φ,亦即这些图案全部符合跷跷板原理。以图4-1为例,魔方的三个未定向下角块的状态皆为顺时针扭转,其状态值的和(记为Σ)应为:
Σ=S+S+S=-S+S=φ
对其余各图案皆可以仿此进行验证。
从逻辑完备性的角度考虑,除过已开解状态,魔方四个下角块一切逻辑上可能(自然包括实际可能)的方向状态的组合、以及这些组合各自状态值的和可列示如表1。
(表1)
未定向下角块的组合表
总类
细类
具体状态
状态值
的和Σ
四个
下角块
皆未定
向
1
四个下角块逆时针扭转
-S
2
三个下角块逆时针扭转,一个反之
S
3
两个下角块逆时针扭转,另外两个反之
φ
4
一个下角块逆时针扭转,其余三个反之
-S
5
四个下角块顺时针扭转
S
仅有
三个下
角块未
定向
6
三个下角块逆时针扭转
φ
7
两个下角块逆时针扭转,一个反之
-S
8
一个下角块逆时针扭转,两个反之
S
9
三个下角块顺时针扭转
φ
仅有
两个下
角块未
定向
10
两个下角块逆时针扭转
S
11
一个下角块逆时针扭转,另一个反之
φ
12
两个下角块顺时针扭转
-S
仅有
一个下
角块未
定向
13
一个下角块逆时针扭转
-S
14
一个下角块顺时针扭转
S
【说 明】(1) 最右一栏中的Σ的值,系依据对应的具体状态,运用扭转代数计算而来的。如细类7,按具体状态其状态值的和可计算如下:
Σ=-S+(-S)+S=S+S=-S
(2) 有些细类在逻辑上还可以分出更小的类,但进一步的分类并不会改变Σ的值。
表中方块扭转状态的组合计四总类,十四细类。凡∑≠φ,亦即不符合跷跷板原理的那些组合所对应的魔方的“图案”,皆为逻辑上可能而实际不可能的图案;所有符合跷跷板原理,亦即∑=φ的那些组合所对应的魔方的图案,皆为实际可能(自然也是逻辑可能)的图案。从表上可以看到,符合跷跷板原理的只有3,6,9,11四个细类。而这四类刚好对应着第二章图4的七个图案,其详情如下。
细类3谓“两个下角块逆时针扭转,另外两个反之”,但在魔方的下平面上,两个同向扭转的下角块的位置可以是相邻的,也可以是相对的,故细类3实际可以再分为两个小类。此两个小类分别应着图4⑤(同向扭转的方块相邻)、图4③(同向扭转的方块相对)。
细类6对应图4②,细类9对应图4①。
细类11仅有两个下角块互为反向扭转,但它们在下平面的位置也可以是相对的或相邻的。位置相对的那一小类对应着图4⑥。而位置相邻的那一小类还可以进一步进行分类。为了便于叙述,我们把魔方下角块(以及以后还要论及的下边块)染着下平面颜色的那个小正方形称为下色面。这样,上述位置相邻的小类就可以按两个扭转下角块的下色面是否是在魔方的同一侧面,划分为两个更小的类。划分后一个更小的类对应图4④(两个下色面位于魔方的同一侧面),另一个更小的类对应图4⑦(两个下色面位于魔方的不同侧面)。
至此我们就可以断言,从逻辑上推定的所有符合跷跷板原理的未定向下角块的组合,正好对应着图4中的七个图案。于是第二章(四)(乙)所给的下角块定向开解法的完备性得证。
本章所证明的完备性可以称为相对于跷跷板原理的完备性。它与上一章所说的逻辑的完备性有深刻的差别,但对这些差别的讨论却不属于本书的任务。
开解法证明(Ⅲ)
为了证明下边块定向开解法的完备性,须要引入翻转(音zhuǎn)代数。
魔方中构成一个边块的两个小正方形交换方向,这一置换称为一个翻转,记为T。一个边块翻转一次再翻转一次,就恢复了原来的方向,据此可以定义翻转的基本运算:
T+T=φ
和扭转代数一样,在翻转代数中,加运算的交换律和结合律成立,并且:
T+φ=T, φ+φ=φ
第二章(五)(甲)在考虑下边块对下平面的定向时,认为在完成了该章步骤(一)至(四)所述的开解后,如果有下边块相对于下平面呈现翻转,则翻转的方块只能是2个或4个,并针对这两类情形给出了开解方法。
两个翻转状态的方块,无论其位置相对还是相邻,其状态和皆为:
∑=T+T=φ
四个翻转方块的状态和为:
∑=T+T+T+T=φ+T+T=T+T=φ
故该处所论的两类待解情形完全符合跷跷板原理。现在假设翻转的下边块为一个或三个,则其状态和分别为:
∑(1)=T≠φ
∑(3)=T+T+T=φ+T=T≠φ
∑≠φ意味着假设的1个或3个下边块翻转的图案不符合跷跷板原理,故而在正常的魔方上不会出现这两种图案。如此,我们就证明了第二章(五)(甲)所给的下平面定向开解法的完备性。
为了证明下边块定位开解法的完备性,须要引入置换代数。
对换是最简单最基本的置换。用C表示一个对换;一个对换总须涉及两个方块,两个方块对换一次再对换一次,二者又都回归到了各自原来的位置,据此可以定义对换的基本运算为:
C+C=φ
与翻转代数相类似,在对换代数中亦有:
C+φ=C, φ+φ=φ
且加运算的交换律和结合律成立。
为了便于讨论,有时又把a,b两个方块的对换记为(ab)。
轮换也可以看成是一种基本的置换。记a,b,c三个方块的轮换为(abc),原则上,三个方块的轮换总可以化归为两个对换。具体的化归过程是:先对换a,b,然后再对换b,c。用算式表达即为:
(abc) =(ab) + (bc)
仿此亦不难推出四个方块所形成的轮换总可以化归为三个对换。一般地,我们有如下的定理:
化归定理 大于2的n个方块的轮换可以化归为n-1个对换。
【证明】 运用构造法来证明,即构造出n-1个对换,使其等同于已知的n元轮换。
记n个方块a1,a2,…,an所成的一个轮换为(a1a2…an),又记方块ai在置换发生前的原初位置为Ai,对这n个方块做如下n-1个系列对换:
(a1a2) + (a2a3) + (a3a4) + … + (aiai+1) + … + (an-1an)
按上式,第1个对换发生后,a1到达A2,a2到达A1;第2个对换发生后,a2到达A3,a3到达A1,此时方块的排布是:
位置
A1
A2
A3
A4
…
Ai
Ai+1
方块
a3
a1
a2
a4
…
ai
ai+1
第i个对换发生后,ai到达Ai+1,ai+1到达A1。此时方块的排布是:
位置
A1
A2
A3
A4
…
Ai
Ai+1
方块
ai+1
a1
a2
a3
…
ai-1
ai
由上表可以看到,方块a1,a2,…, ai,ai+1正好形成了一个i+1元的轮换(a1a2…aiai+1)。
继续进行系列对换,当第n-1个对换(an-1an)完成后,其结果正好是轮换(a1a2…aiai+1…an)。
——证毕。
由化归定理不难得出如下两个推论:
推论1 奇数个方块的轮换可以化归为偶数个对换,偶数个方块的轮换可以化归为奇数个对换。
推论2 奇数个方块所成轮换的状态值为φ,偶数个方块所成轮换的状态值为C。
完成了下边块对下平面的定向以后,第二章(五)(乙)指出:如果此时下边块没有归位或没有全部归位,那么实际可能的情形是:或者仅有一个下边块已归位,或者四个下边块全部没有归位。现从逻辑完备性的角度出发,运用跷跷板原理和置换代数予以证明。
1. 仅有一个下边块未归位,这在逻辑上不可能。
2.仅有两个下边块未归位,则这两个方块只能形成一个位置对换,其图案的状态和为:
∑=C≠φ
这不符合跷跷板原理,故实际不会出现这种情形。
3.仅有三个下边块未归位,则这三个方块必构成一个轮换,由上节知三个方块的轮换可以化归为仅涉及这三个方块的两个对换,故此时下边块的状态和为:
∑=(a1a2a3)=C+C=φ
这符合跷跷板原理,而这正是第二章(五)(乙)1所估计的。
4.第二章(五)(乙)2给出了四个下边块皆未归位的开解方法,其实它所针对的只是如图15所示的两类对换情形:
在图15①中,本位为A的边块a与本位为B的边块b互占对方的本位,边块c与边块d也互占对方的本位,此为位置相对的边块两两对换;而图15②中所示的则是位置相邻的边块两两对换。两个图案各有两个对换,其各自的状态和皆为:
∑=C+C=φ
此与跷跷板原理相符。
此外,从逻辑上说,四个未归位方块还应有三种轮换的形式:顺时针相邻的轮换,逆时针相邻的轮换,斜“8”字轮换(参见第三章(二))。但无论哪种形式,依据置换代数,由四个方块构成的一个轮换总可以化归为三个对换的和,故而这三种图案的状态和皆为:
∑= C+C+C=φ+C=C≠φ
这与跷跷板原理不符,故而在所论的开解时刻(其它时刻未必),魔方的四个下边块不会呈现轮换图案。
至此,我们就证明了第二章(五)所给的下边块定位开解法的完备性。
现在让我们来概括地回顾一下第三章至本章主要的内容。针对第二章所给的魔方开解的顺序(共六个环节,见第二章引言),在第三章中,我们仅从逻辑完备性的角度出发,列举了所论的各开解步骤(包括子步骤)实施前所涉方块所有可能的图案;在第四章与本章中又同时依据跷跷板原理,指出所论的逻辑可能的图案哪些实际上不可能存在;而在这三章中我们还陆续指出了:一切实际且逻辑可能存在的图案,均在第二章开解方案所考虑的范围之内。
所以,第二章所给的开解方案是完备的。
方块的空间状态暨魔方表示定理
前边具体讨论魔方方块的状态时,主要是在一个层面内——下层面进行的。本节将转入魔方空间——三层、六个面的方块状态的讨论。
对于位置状态,即使在空间中,我们仍然可以仅凭观察就可以确定哪些方块相对于原位发生了对换,哪些方块相对于原位发生了轮换。
为了确定方块在魔方空间中的方向状态,我们必须事先约定魔方六个面的方向:你可以任意地指定前、后、左、右、上、下平面,然而一旦这种指定完成,就不能随意改换。这一点与前面开解法中的规定稍有不同。
此外,还需要以下术语:
上色面——一个方块上染着上平面颜色的那个小正方形。
下色面——一个方块上染着下平面颜色的那个小正方形。
前色面——一个方块上染着前平面颜色的那个小正方形。
后色面——一个方块上染着后平面颜色的那个小正方形。
完成了这些准备工作,就可以对方块在魔方空间中正确的方向状态(其方向状态值为φ)进行如下的约定:
上角块位于本层且其上色面位于上平面时,方向正确;位于下层而其上色面位于下平面时,方向正确(仅仅只是位置发生了变化)。
下角块位于本层且其下色面位于下平面时,方向正确;位于上层而其下色面位于上平面时,方向正确。
——以上两种方块在不同层面、不同位置上的顺时针和逆时针的扭转状态与前面章节的约定相同。
上边块位于本层且其上色面位于上平面时,方向正确;位于中层且其上色面位于左平面或右平面时,方向正确;位于下层且其上色面位于下平面时,方向正确。
下边块位于本层且其下色面位于下平面时,方向正确;位于中层且其下色面位于左平面或右平面时,方向正确;位于上层且其下色面位于上平面时,方向正确。
中边块位于本层且其前色面或后色面均位于前平面或后平面时,方向正确;位于上层且其前色面或后色面不在上平面时,方向正确;位于下层且其前色面或后色面不在下平面时,方向正确。
——所有边块不符合以上所说的情形时,其方向状态均为翻转状态。
为了便于读者在魔方空间上验证跷跷板原理,特将以上的约定集中列示为表2。
表2约定是基于如下一些考虑而做出的。
以边块为例,虽然当一个边块不在本位时,我们很难说它是否发生了翻转,但它依然像在本位时那样具有两个可能的方向。这两个方向与其在本位时的两个方向之间存在一一对应关系[注1],任选一种一一对应关系,把与值为φ的那个本位方向状态对应的非本位方向状态的值也记为φ,把另一个非本位方向状态的值记为T[注2]。这样,一个边块即使不在本位,我们仍然可以按它的方向状态的值称其为翻转(当值为φ时)或未翻转(当值为T时)。
(表2)
位 置
方向
状态值
说明
方 块
类 型
在上层
在中层
在下层
上角块
√
上色面位于上平面
φ
其它方向状态的值为S或-S
√
上色面位于下平面
下角块
√
下色面位于上平面
√
下色面位于下平面
上边块
√
上色面位于上平面
φ
其它方向状态的值为T
√
上色面位于左或右平面
√
上色面位于下平面
中边块
√
前或后色面不在上平面
√
前或后色面位于
前平面或后平面
√
前或后色面不在下平面
下边块
√
下色面位于上平面
√
下色面位于左或右平面
√
下色面位于下平面
不过仅用一一对应的思想作指导还不够。在约定方块在魔方空间中的方向状态时,还必须考虑魔方的对称性。对称性的约束从表2中可以很明显的看出。表中横栏“上边块”第二行约定:当一个上边块位于中层时,仅当“上色面位于左或右平面”,其方向状态值为φ。所谓“上色面位于左或右平面”又可以表述为:上边块的上色面不在前平面或后平面。而在横栏“中边块”第一行则有与此完全对称的表述:位于上层时,中边块的“前或后色面不在上平面”,其状态值为φ。整个表2其实正是用这样的对称表述架构而成。
最后的问题是,由对称性约束而得来的表2,是否仍然与跷跷板原理相合?答案是肯定的。因为跷跷板原理是对称性的集中表现,事实上我们也可以不刻意追求上面那种对称的语义表述,而直接运用跷跷板原理来约定方块在魔方空间中的方向状态,最终仍然可以得出与表2相同的内容。对此就不作详述了。
二) 魔方表示定理
在前几章中,我们多次提到了所谓“逻辑上可能而实际不可能”的图案,并强调此类图案不会出现在在一个正常的魔方上。不过,在一个组装错误的魔方上,这些图案却可能出现。下面所给的就是关于组装错误的魔方所遵循的一个定理。
魔方表示定理 把一个正常的魔方拆散后随意组装,不管在组装过程中发生了多少组装错误,组装完成后总可以使这些错误化归为魔方某一平面上不超过三个方块的错误。
【说明】从逻辑上看,在跷跷板原理的支配下,定理中所说的化归后的错误只能是如下11类错误中的一类:
当其它所有方块都正确时,在魔方的某一平面上——
(ⅰ) 一个角块顺时针扭转;
(ⅱ) 一个角块逆时针扭转;
(ⅲ) 一个边块翻转;
(ⅳ)两个边块对换[注1];
(ⅴ) 一个边块翻转且它同时与另一个边块对换;
(ⅵ) (i)和(ⅲ)的组合;
(ⅶ) (ⅱ)和(ⅲ)的组合;
(ⅷ) (i)和(iv)的组合;
(ⅸ) (ⅱ)和(iv)组合;
(x) (i)和(v)的组合;
(xi) (ⅱ)和(v)的组合。
以上11类错误再加上正确的一类,正好对应于所谓的魔方组装的12个族。
就思路而言,本定理的证明与前面开解法完备性的证明并无二致。为避免冗长,这里我们仅指出证明的思路。
在第三章,我们证明了第二章所给的下角块定位及其以前各步骤的开解法具有逻辑的完备性,故而一个魔方无论有多少组装错误,并不影响第二章所给的上边块、上角块和中边块的定位定向开解法的有效性和充足性,也不影响下角块定位开解法的有效性和充足性。故而按第二章的开解步骤,在完成了下角块的定位开解后,魔方的全部组装错误将表现于下平面。
如果组装确有错误,则下平面的图案必然不符合跷跷板原理。当我们逻辑地列出所有不符合跷跷板原理的图案时(麻烦和冗长就在这里),就会发现,我们总可以选择(有时不须选择)第二章中的某些转动程序,使这一图案化归为本节上文【说明】中所列的某一类图案。比如,假设一个组装错误的魔方此时其下平面呈现图案如图16①:
此图案不符合跷跷板原理。对此图案运用一次程序P8(见第二章),再以魔方上下中心块的连线为轴,将魔方整体转动180°,则呈现图案如图16②。对图案16②运用一次P8的对称程序 :
L+,D+, L-, D+, L+, D2, L-, D2
图案转化为图16③,这正是【说明】中所举的错误(i)。[注2]
对所有不符合跷跷板原理的图案,均可以通过类似于以上的步骤,使之转化为前面【说明】中所列的错误(i)至(xi)中的某一种。又所有符合跷跷板原理的图案与不符合跷跷板原理的图案可以构成一个全集——亦即魔方上一切逻辑可能(无论其正确与否)的图案的集合。至此魔方表示定理可以得证。
几个重要的计数公式
我们准备运用跷跷板原理和排列组合知识来计算魔方上所有图案的组合数。为此,需要先引入和证明几个重要的组合计数公式。本章的数学意味太浓且论证琐细,不感兴趣的读者可以只看结论而略去过程。
记n个连续自然数的集合{1,2,3,…,n}为N(n),并用这n个自然数来标记n个不同的方块,这样n个方块的任意一个轮换可以表示如图17。图中的每一个ni N(n),且i N(n),当i≠j时ni≠nj。
此图是以n个数为顶点、n个箭头为边的多边形。用这样的图形来表示轮换,可以使互为反向的轮换或魔方实际中更为复杂的轮换路径的图案(这些图案还可能是立体的)得到统一的、简单的表示。比如位于魔方同一平面的n1,n2,n3三个方块,其顺时针轮换可表示为图18①,逆时针轮换可表示为图18②。
图18中①和②所用箭头完全相同,不需要再使用相反的箭头把逆时针轮换表示为②a,也不须考虑这三个方块是否在同一平面。故而,在标准的轮换示意图18①和18②中,完全可以用直线来代替箭头。这样n个方块构成的任意一个轮换又可以由图17进一步简化表示为图19:
现另举一个例子来说明这种表示法的好处。按本书第三章(二),如果考虑方块的不同颜色,一个平面上四个角块n1,n2,n3,n4的“8”字轮换须分别表示为图20中的①和②,而采用标准示意图,则①简化为①a,②简化为②a。这样就避免了实际中“8”字图案所带来的困惑。
记n个方块(n.≥3)所成的轮换数为R(n),现在证明:
R(n)=(n-1)! (n.≥3) ………………A
【证明】 用数学归纳法[注]。
当n=3时,R(3)=(3-1)!=2,此时公式③成立(三个方块仅有的两个轮换见本节图18①和②)。
设n=k时R(k)=(k-1)!成立,考虑n=k+1。已知k个方块的任意一个轮换可用边数为k的多边形表示,任取这多边形的一条边,将其“切断”,在断点处插入一个新的方块l,就可以构成一个k+1元的轮换,如下图。
由于k元轮换多边形有k条边,故而可供l插入的位置有k个;而l每插入一个位置,就与原来轮换中的所有元素构成一个新的k+1元轮换,即在一个k元轮换中插入一个元素,可以生成k个互不相同的k+1元轮换。但由归纳假设,k个方块所成的k元轮换又有(k-1)!个,故而增加一个方块后生成的k+1元轮换总共应有k(k-1)!=k!个,即
R(k+1) =k!
——证毕。
计算魔方方块的组合数,常常需要把一些方块分成相等的几组。
中学数学课本中有类似于这样的习题:把6个方块平均分成两组,有几种分法?答案是:用6个元素中选取3个元素的组合数除以2,即
现在考虑把6个方块平均分成3组。先用连续自然数1至6给6个方块编号。通常的考虑是先从6个方块中选取2个为第一组(有 种选取法),再从剩下的4个方块选取2个为第二组(有 种选取法),最后剩下的2个作为第三组(有 =1种选取法),按照排列论,这样的分法的个数为:
……………… Δ
以下是这种分法的一个实例:
Ⅰ
第一组:{1,2}
第二组:{3,4}
第三组:{5,6}
Ⅱ
然而按这种分法至少还有以下的两个实例:
第一组:{3,4}
第二组:{1,2}
Ⅲ
第三组:{5,6}
第一组:{5,6}
第二组:{3,4}
第三组:{1,2}
但按我们的目的——只是把6个方块平均分成三组,并不需要考虑组的先后顺序,这样以上三个实例只能算是同一个分组。显然,Ⅰ、Ⅱ、Ⅲ属于既定的三个组集合的3种排列,按照排列论,这样的排列共有3!种。这意味着按Δ式所进行的计数有重复,每一个分组被计算成了3!个,去掉重复后符合我们目的的分组的个数应为:
从以上的特例可以过渡到一般情形。设k整除n,把n个方块平均分成k组,每一组的方块数为l,则如此分组的个数为:
(l≥2 ) ………………… ※
其推求的途径与上边的特例相仿,只是符号表述过于复杂,在本章最后一节给出其推导的全过程。
由表达式※立刻可以得出:设n为偶数,l = 2,从而 ,记这n个方块可以形成的对换个数为f(n),则
……………… B
当n=2时,f(2)=1 。
若l大于等于3,按本章(一)公式A,l个方块可以形成(l-1)!个轮换。当n个方块被平均分成k组且每一组为l个方块(l≥3)时,记这n个方块可形成的l元轮换的个数为g(n,k,l),则由表达式※及公式A可得:
※·[R(l)]k = ……………… ☆
即:
……………… C
注意在☆式中之所以取因式[R(l)]k而不是R(l),是因为 个分组中的每一个分组都有k个组,而k个组中的每一个组都可以独立地形成R( l )个不同的轮换。
公式A,B,C与组合数 的计算公式,是下一章计算方块置换数的主要公式。现预先举例说明如下。
【例1】6个活动角块,其中4个角块轮换,剩余2个角块对换,这样的置换的组合数为:
C ·R(4)· f(2)= C (4-1)! f(2)
= ·3! = 2520
【例2】9个活动边块形成三个3元轮换,轮换组合的总数为:
g(9,3,3) = 492800
【例3】8个角块,其中4个角块形成两个对换,另4个角块形成一个四元轮换,这样的置换的组合个数为:
f(4)· R(4) = f(4)·3! = 1260
在下一章表6和表7中,皆循以上诸例列式并计算。其中【例3】不符合跷跷板原理,故未被列入表6。
若k整除n,则n个方块被平均分成k组时,每组有l = 个方块。为推导表达式※,我们对这k个组用1至k共k个连续自然数进行编号,然后先让第1组从n个方块中选取l 个方块,再让第2组从n-l个中选取l个,组序递增,每一组均在前面各组选取后剩余的方块中选取l个方块;至第k组,从n-(k-1)l=l个方块选取l个方块。按照排列组合知识,如此选取所得的组合数为(注意n= k l):
… …
在这 个组合中,从不计先后顺序而分组的角度来看有些是重复的。用bij(i=1,2,…,k;j=1,2,…,l)表示n中的方块,考察这 个组合中的以下两个组合:
Ⅰ
第1组:{b11,b12,…,b1l}
第2组:{b21,b22,…,b2l}
………………………
第 i组: {bi1,bi2,…,bi l}
………………………
第k 组:{bk1,bk2,…,bkl}
Ⅱ
第1 组:{bi1,bi2,…,bi l}
第2 组:{b21,b22,…,b2l}
………………………
第i 组:{b11,b12,…,b1l}
………………………
第k 组:{bk1,bk2,…,bkl}
组合Ⅰ中的第1组与第i 组互换位置即为组合Ⅱ,可见Ⅰ和Ⅱ只是k个既定集合的两个不同排列。按我们的要求,以上两个排列只能算是同一个分组。依据排列论, k个元素的不同排列共有k!个,而所有这k!个排列在此都应视为同一分组,故而,符合我们目的的分组的个数应为:
(l≥2 )
——表达式※推导完毕。
魔方组合计数
用状态值来表示,则一个角块三种可能的方向状态是:φ,S,-S,而任意多个角块的方向状态的和也只能是这三个值。
现在先考察两个角块的情形。如果不考虑跷跷板原理,则对于第一个方块的三个方向状态中的每一个,第二个方块都有三个方向状态与之配对,故而此时两个方块的方向组合数为32=9(这些组合并不完全符合跷跷板原理),如下表所示。
(表5)
第一个角块的值
第二个角块的
对应值
状态和
φ
φ
φ
φ
S
S
φ
-S
-S
S
φ
S
S
S
-S
S
-S
φ
-S
φ
-S
-S
S
φ
-S
-S
S
现在过渡到3个方块。对于前两个方块9个方向组合中的每一个,第三个方块也都有三个方向状态分别与之配对(配对的结果不一定符合跷跷板原理),故而此时3个方块的方向组合数为33=27。
重复以上步骤可以推算出4,5,6,7个角块的方向组合数。其中7个方块的方向组合数为37=2187。
当我们考察8个方块的方向组合的时候,就必须考虑跷跷板原理了。这是因为跷跷板原理只能且必须体现在完整的魔方中,而少于8个角块的魔方是不完整的。
7个方块的37=2187个组合中的每一个,其状态值只能是集合{φ,S,-S }中的一个元素;在跷跷板原理的支配下,如若这37个组合中的某一个组合的状态值为φ,则第八个方块只能等于φ,而不能像上边那样随意地取S或-S;当有另外两个组合的状态值分别为S和-S时,第八个方块又只能分别对应地取-S和 S值。概括地说,对于7个方块的37个方向组合中的每一个,第八个方块只能有一种方向状态与之对应组合。所以,在跷跷板原理的支配下,魔方上8个角块的方向组合数应为:
37×1=37=2187
用同样的思路,我们可以算出12个边块的方向组合数。注意到一个边块只有两个方向状态,则12个边块的方向组合数应为:
211=2048。
在第三章(二)中,置换被划分成对换和轮换两种。现在我们把参与了非零置换的那些方块称为活动方块,而方块的置换组合数是由活动方块数决定的。在若干个活动方块中,一部分可能形成对换,另一部分则可能形成轮换。下面给出8个角块所有符合跷跷板原理(实际可能)的置换组合表:
(表6)
符合跷跷板原理的角块置换组合一览表
活动
方块数
细类
组合方案
组合算式
组合值
0
①
没有角块参与非零置换
1
3
①
3元轮换
112
4
①
两个对换
210
5
①
5元轮换
1344
6
①
4元轮换,1个对换
2520
②
两个3元轮换
1120
7
①
7元轮换
5760
②
两个对换,一个3元轮换
1680
8
①
6元轮换,一个对换
3360
②
5元轮换和3元轮换各一
2688
③
两个4元轮换
g(8,2,4)
1260
④
四个对换
f(8)
105
合计
20160
容易知道,8个角块所有的置换(无论是对换或轮换)都属于8个角块的全排列。依据排列知识,8个角块的全排列数为
8!= 40320
从中减去表6中“组合值”栏的“合计”数:
40320-20160 = 20160
所得的结果为不满足跷跷板原理的角块的组合数, 它正好与满足跷跷板原理的角块的组合数相等——这一现象绝非偶然,但我们不讨论这一问题。
现在来看表6中的组合方案是如何得来的。简单地说,它们是通过整数分拆得来的。整数分拆属于数论知识,本身比较复杂。所幸的是需要我们分拆的数很小:角块时最大为8,边块时最大为12;所以完全可以通过简单地思考得到全部符合条件的分拆。下边予以具体说明。
对于i个活动方块,把它们分拆为若干组,使各组分别形成对换或轮换,这首先要求i大于3,同时要求各组所含的方块数大于等于2——这些要求的正当性在逻辑上显然。此外按照数学惯例,i=0也是可以允许的;事实上,i=0表明没有方块发生置换,即所有的方块位置正确,这是一种符合跷跷板原理的合法的组合。现在以i=6为例来看看具体的分拆过程。先考察含有0个对换的分拆(注意这里与表6所列的顺序并不一致,但不影响考察的结果),此时方块只能分拆为一个6元轮换或两个3元轮换,后者因其状态和符合跷跷板原理而被列入表中;如果分拆仅含有1个对换,此时方块只能被分拆为一个对换与一个4元轮换这共存的两组,此两组的状态和也符合跷跷板原理,故而被列入表中;仅含有2个对换的分拆逻辑上不存在;含有3个对换的分拆因其状态和不符合跷跷板原理而未被列入表中。这样,我们就在表6中列出了6个活动角块符合跷跷板原理的全部置换组合方案。表6中其余的组合方案以及下一节表7中所列的活动边块的组合方案,其求取的思路与以上所说的完全一致。
12个边块符合跷跷板原理的置换组合值,当活动边块数k小于9时,可将表6中对应的k个活动角块的组合值除以 再乘以 即可得到,由此得k小于9时的12个组合值是:
1,440,1485,19008,83160,36960,570240,166320,1663200,1330560,
623700,51975
这12个值的和已填入表7“组合值”栏第一行。表7的最后给出了所有符合跷跷板原理的边块置换组合数的合计值为:239500800。
(表7)
符合跷跷板原理的边块置换组合一览表
活动
方块数
细类
组合方案
组合算式
组合值
小于9
合计
4547049
9
①
9元轮换
·8!
8870400
②
三个3元轮换
492800
③
一个对换,4元轮换和3元轮换各一
3326400
④
二个对换,一个五元轮换
1995840
10
①
7元轮换和3元轮换各一
11404800
②
6元轮换和4元轮换各一
9979200
③
两个五元轮换
4790016
④
一个对换,一个8元轮换
14968800
⑤
两个对换,两个3元轮换
1663200
⑥
三个对换,一个4元轮换
1247400
11
①
11元轮换
43545600
②
两个4元轮换,一个3元轮换
4989600
③
一个5元轮换,两个3元轮换
5322240
④
一个对换,6元轮换和3元轮换各一
13305600
⑤
一个对换,5元轮换和4元轮换各一
11975040
⑥
两个对换,一个7元轮换
8553600
⑦
四个对换,一个3元轮换
415800
12
①
9元轮换和3元轮换各一
17740800
②
8元轮换和4元轮换各一
14968800
③
7元轮换和5元轮换各一
13685760
④
两个6元轮换
g(12,2,6)
6652800
⑤
四个3元轮换
g(12,4,3)
246400
⑥
一个对换,一个10元轮换
23950080
⑦
一个对换,两个3元轮换,一个4元轮换
3326400
⑧
两个对换,5元轮换和3元轮换各一
3991680
⑨
两个对换,两个4元轮换
1871100
⑩
三个对换,一个6元轮换
1663200
⑾
六个对换
f(12)
10395
合计
239500800
(四) 魔方方块的总组合数
本章以上已分别计算了角块、边块各自符合跷跷板原理的方向组合数与置换组合数,现在汇总计算魔方方块的总组合数。为方便引用,我们把已算出的结果集中列示如表8。
(表8)
组合类型
组合数
计算所在的章节
角块方向组合
37=2187
本章(一)
边块方向组合
211=2048
本章(一)
角块置换组合
20160
本章(二)
边块置换组合
239500800
本章(三)
按表8,已经知道角块的方向组合数为2187,角块的置换组合数为20160,在不考虑边块时,符合跷跷板原理的角块的组合总数为:
2187×20160 ①
同样,在不考虑角块时,符合跷跷板原理的边块的组合总数为表8中边块的方向组合数与置换组合数的乘积:
2048×239500800 ②
此外,单独看角块,其不符合跷跷板原理的置换组合数为:
8!-20160=20160
单独看边块,其不符合跷跷板原理的置换组合数为:
12!-239500800=239500800
当边角两类方块的置换同时不符合跷跷板原理时,其各自的状态和皆为C,但这两个状态和的和为:
C+C=φ
这又符合跷跷板原理,故由这两类不符合跷跷板原理的置换相互搭配所成的组合,仍然是合法、正确的魔方图案,应计入组合总数中。此两类搭配所成的置换组合数为:
20160×239500800
再考虑到方向数,则这两类搭配所成的组合的总数应为:
20160×239500800×2187×2048 ③
现在,可以计算魔方方块的总组合数如下:
①×②+③=2187×20160×2048×239500800+20160×239500800×2187×2048
=2×20160×239500800×2187×2048
=43252003274489856000
≈4.3×1019
至上一节完成的魔方方块组合数的整个计算过程具有较强的直观性,它使读者能具体地了解到魔方的方块是如何组合、如何置换的。但表6和表7中繁复的数字计算却显得有些丑陋。为避免这种丑陋,以下给出另外两种算法。
(甲)引用魔方表示定理
按照排列组合知识,易知8个角块在魔方上的逻辑可能的置换组合可以看成是8个角块的全排列,其数值为8!;同理12个边块逻辑可能的置换组合数为12!。又易知8个角块逻辑可能的方向组合数为38,12个边块逻辑可能的方向组合数为212。这样魔方全部逻辑可能的图案数为:
8!×38 ×12!×212
这是所有组装正确和组装错误的魔方图案的总数。由魔方表示定理知道,这样的图案可分为12个族,其中仅有一个族的图案为组装正确的魔方的图案。各族的图案数应该相等——这是因为,一个组装错误的魔方与组装正确的魔方有着完全相同的物理构造和转动方式。不妨想象已知的组装错误的魔方只是对一个组装正确的魔方进行重“染色”而成的,“染色”行为显然不会改变这个魔方中方块的组合数。故而,任意一个既已组装的三阶魔方(无论其组装正确与错误)的图案的总数应为:
(乙)引用群论中的一个知识点
在本书结尾的这一部分,我们稍微提及群论。但我们的讨论只能是概要的、不甚严密的。
本书前面所说的符合跷跷板原理的置换,在群论中称为偶置换,不符合跷跷板原理的置换被称为奇置换。计算魔方方块的组合数,在不论方块的方向时,就是计算方块的偶置换数。
在群论中证明了: n个元素所成的n!个置换(即全排列)中,奇偶置换各占一半,即奇偶置换各为 n!,故而8个角块所成的偶置换数为 个,12个边块所成的偶置换数为 个。
角块、边块之间的偶置换与偶置换的组合是偶置换,这种组合共有 个。
角块、边块之间的奇置换与奇置换的组合也是偶置换,这后一类偶置换也有 个。
以上两类偶置换数的和为:
再考虑到角块和边块的方向,则魔方方块的总组合数为:
顺带指出,魔方中方块的扭转和翻转也可以转化为纯粹的群论问题去进行处理,但不能像处理置换这样简洁和直接。对此,后面的附录有详细论证。
2004年12月11日21时51分电子版初稿
2007年2月19日星期一下午2时23分重修订完毕
【附录】
本书正文初稿在网上挂出后,有读者问:既然在第八章的结尾引用了置换群的知识来简化方块置换组合数的计算,那么群论能够处理方块的方向问题吗?本文将解答这一疑问,不过这要求读者拥有群论和向量代数的初步知识。
以下论述凡提及处,皆指全部角块已经归位的鲁毕克魔方。
在正文第四章(二)中,为处理角块的方向组合问题,我们在集合A={φ, T, -T}上定义了一个运算“+”(直接称为“加”、“加运算”)。容易看出,A中元素对于这一运算构成群,且此群是一个交换群和循环群。为便于进一步讨论,我们称此群为角的精细群或直接称为精细群,并将它记为E,按群论的常例表示为:
E = {A, +}
又称此群中的每一个元素ti (注意ti∈A)为一个精细值,精细值的运算仍沿用正文中状态值的“+”运算。
记定义于集合A上的任一n维(魔方的角块有8个,所以应是8维)向量为:
并记所有这样的向量的集合为B:
B = { b|b是定义在集合A上的n维向量 }
从魔方直观看,任意一个b =
任取B中的两个向量元素b1, b2:
b1 =
b2 =
现给出这两个元素之间加运算的定义如下。
定义1 b1 + b2 =
=
此定义的魔方直观意义是:取两个方向图案未必相同但角块编号相同的魔方,把第一个魔方与第二个魔方中所有序号对应相等的角块的精细值(在正文中叫“状态值”)分别相加,其结果是唯一确定的一个魔方图案,这种图案的魔方也可以通过组装或转动而得到。
显见定义1与普通代数中向量加法的定义完全一致。我们知道在一般向量加法的定义中,等号两端加号的意义并不一样。定义1也是如此,其前两个加号表示两个魔方的角块按一定规则的虚拟叠合,后边尖括号中的加号则表示叠合的规则:相同编号的角块状态值(或精细值)相加。
定理1 向量集合B与定义1所确定的加运算构成一个群。
证明 (1)运算的封闭性显然。又B中必有这样一个元素Φ:
Φ = <φ,φ,…,φ> (尖括号中有n个φ)
此元素显然符合群单位元的要求。
(2)对于任意的b=
b + b’=
= <φ,φ,…,φ> = Φ
所以任一元素的逆元存在。
(3)按定义,集合B中向量的加运算,其实仅仅是对两个向量的对应分量分别相加,而每一个分量又是一个精细值,在正文第四章(二)中已证明精细值的加运算满足结合律,故而B中向量的加运算也一定满足结合律。这样,定理1完全得证。
我们称定理1所说的向量群为角方向组合群,或简称为角方向群、方向群。记此群为Cd:
Cd={B,定义1所确定的运算“+”}
自然,群Cd是一向量加群。
下来讨论Cd的性质。
定理2 Cd是交换群。
欲证此定理,可比照定理1证明结合律的思路,此处从略。
定义2 对Cd中的任一元素b=
S(b)=t1+t2+ … +tn
为b的精细值的和,或简称为精细和。它也就是正文所说的状态和。
定理3 Cd中任意两个元素:
b1=
b2=
相加结果的精细和,等于b1的精细和与b2的精细和的和。即:
S(b1+b2) = S(b1) + S(b2)
证明 b1 + b2 =
=
故而,
S(b1 + b2) = S(
=(t1 + t21 )+(t2 + t22 )+…+(tn+ t2n)
=(t1 + t2 + … + tn) + (t21 + t22 +… + t2n)
= S(b1) + S(b2)
证毕。
易知,Cd中任一元素b的精细和的可能的取值,仅为集合A中的所有的三个元素:φ, T, -T。据此可以把Cd的集合B划分为互不相交的三个子集:
B0 = { b|S(b)=φ}
B1 = { b|S(b)=T }
B2 = { b|S(b)=-T}
B0为正文所说的组装正确、符合跷跷板原理的魔方角块的图案集合;B1和B2为组装错误从而不符合跷跷板原理的魔方角块的图案集合。
定理4 集合B0对向量的加运算构成群。
证明 因为B0是群Cd的集合B的子集,其运算的结合性是自然的。我们只须证明单位元和逆元的存在以及加运算的封闭性。
(1)∵ S(Φ)= φ(显见) ∴Φ∈B0
即集合B0包含单位元。
(2)若b=
∵ b’= b’+ Φ
∴ S(b’) = S(b’+ Φ)
= S(b’) + S(Φ)
= [(-t1)+(-t2)+ … +(-tn)]+φ
已知S(b)=φ,所以又有:
S(b’) = [(-t1)+(-t2)+ … +(-tn)]+ S(b)
= [(-t1)+(-t2)+ … +(-tn)]+[t1 + t2 + … + tn]
= φ
所以b的逆元b’也属于B0。
(3)对属于B0的任意两个元素b1和b2有
S(b1)=φ, S(b2)=φ
按照定理3有
S(b1+b2)= S(b1)+ S(b2)=φ+φ=φ
所以b1+b2也属于B0,即B0对于向量加运算保持封闭性。至此定理完全得证。
出于显见的理由,我们把B0与向量加法所构成的这个群称为角方向的跷跷板群或直接称为跷跷板群,并记为Ss:
Ss = { B0 , + }
自然,Ss是 Cd={B,+}的一个子群。
定理5 若b0∈B0,b1∈B1, b2∈B2,则
(ⅰ) b0+b1∈B1, b0+b2∈B2 ;
(ⅱ) b1+b2∈B0 。
证明 (1) ∵ S(b0+b1)=S(b0)+S(b1)=φ+T=T
∴ b0+b1∈B1
同理b0+b2∈B2 。
(2) ∵ S(b1+b2)=S(b1)+S(b2)=T+(-T)=φ
∴ b1+b2∈B0 。
定理5证毕。
现记任意集合R的元素个数为|R|,我们有如下的定理:
定理6 集合B0,B1,B2的元素个数都相等。即:
|B0|=|B1|=|B2|。
证明 取任一元素b1∈B1,分别与B0中所有的元素相加,则得到|B0|个互异的元素,按定理5(ⅰ),这些互异的元素都属于B1,
∴ |B0|≤|B1| ①
又任取一元素b2∈B2,分别与B1的所有元素相加,则得到|B1|个互异的元素,按定理5(ⅱ),这些互异的元素都属于B0,
∴ |B1|≤|B0| ②
综合①,②可知|B0|=|B1|;同理可知|B0|=|B2|。
∴ |B0|=|B1|=|B2|
证毕。
定理6的一个自然的推论是:角方向的跷跷板群的阶是角方向组合群的阶的三分之一,也就是:
|B0| = |B|
熟知定义于m个元素上的n维向量共有mn个,本例中,
m =|A|=|{φ, T, -T }|=3
又因为角方向组合群Cd的集合B是定义在A上的n维向量的集合,
∴ |B|=3n
∴ |B0| = |B| = ·3n = 3n - 1
又知在鲁毕克魔方中n=8,故组装正确且已全部归位的魔方角块的图案共有38 - 1=37种。
可以把本文中精细群E的集合A={φ,T,-T }推广到任意m个元素的集合Am ={T0,T1,T2,…,Tm - 1}上。这样的推广至少有两个好处:第一,当m=2时,所得的方向群可用于描述边块的状态,这意味着边块和角块的状态在群论中可得到统一的描述;第二,如果存在某种异形魔方,其角块不止8个,角块的状态也不止3种,仍然可以用推广后的方向群来描述。不过本文已经不适合进行这样的推广了。
本书的初稿现仍挂于魔方吧(http://www.mf8.com.cn/)/魔方教室,署名为rongduo。主要由于技术原因,网页上多有文字和格式上的错误。
这次修订以自留的初稿底本为基础,除了改正笔误、调整版式外,在论述内容上有少量的添加,文字亦略有润色。
新增的附录此前亦已发表于魔方吧/论坛(术语略有不同),为方便有兴趣的读者阅读,特刊于此。
魔方吧的网友乌木先生曾指出了本书以前存在的几处文字错误和表述疏漏,特予致谢。
2007年2月19日
[ 注 ] 本书正文末尾一节稍微提到了群论,但只是把它作为一个例子。没有这个例子完全不影响本书的完整性,而例子本身也很容易读懂。
[ 注 ] 除了运用程序P10可开解以外,又可以令已归位的那个边块所在的竖直面为前平面,运用另一种程序:
P11(下边块定位程序又) R-, D-, R+, D+, L+, D+, L-, D2, R-, D+, R+, D+, L+, D-, L-
P11虽然较P10多了一次转动,但其转动的对称性极强,不像P10那样令人眼花缭乱。和P10一样,P11有时也需要连用两次。
[ 注 ] 需要注意:第一,相邻轮换无法进行这样的转化,不管魔方怎样放置,人眼所见的顺时针的轮换都不会变成逆时针;第二,本结论的前提是只考虑轮换路径的几何形状而不计参加轮换的方块的不同颜色,后文计算魔方的组合数时我们将会看到,本段所提及的所有“8”字轮换可能属于不同的组合,因为组合计算必须考虑方块的不同颜色。
[注1] 这种一一对应关系有两个。记边块当前的两个方向状态为x和y,则两个一一对应关系分别为:
f1: x←→φ, y←→T
f2: x←→T , y←→φ
[注2] 在选用一一对应关系时,可以结合魔方图案考虑一下所选用的一种是否比另一种更为熨贴自然,但这种考虑不是必需的。
[注1] 也可以仅仅是两个角块的对换,但为了和前面开解法的顺序一致,这里我们选择了边块。
[注2] 有时候,下边块至此尚未完全归位,这时可以运用第二章(五)(乙)所给的开解法使之完全归位。在第二章已知这并不影响下角块的既有状态。
[注] 也可以用排列知识来证明。
魔方的游戏原理是什么?
谁知道魔方的原理是什么??
魔方的原理、规律与技巧
魔方!!!!!!!!
!!!!!!魔方!!!!!!
!!!!!魔方!!!!!
“排列与组合”的原理及概念?
图中是用1至九的数字组合的魔方阵,其中特征是
爱情魔方
魔方秘籍
关于魔方。
魔方秘籍
爱情魔方
魔方大厦
爱情魔方
成语魔方!!!!!!
爱情魔方
用于分集接收的中频组合器的原理框图 简述其工作原理 这种中频组合器具有什么特点
魔方高手教教我怎么玩魔方?
有谁知道通信专业里面的T接线器,S接线器的工作原理以及T和S组合的工作原理
谁知道玩魔方?
哪有郑渊洁《魔方大厦》动画片?
哪有郑渊洁《魔方大厦》动画片?
哪有郑渊洁《魔方大厦》动画片????