群論與魔方:高階魔方的性質與公式


在上一章,筆者介紹了「高階魔方」的結構和操作;在本章,筆者將介紹「高階魔方」的一些重要性質和公式,這些性質和公式對還原「高階魔方」起很重要的作用。為了使這些性質和公式能適用於任意「n階魔方」(n > 3),本章會使用較概括和較抽象的數式,讀者如有需要,可把具體的數字代入某些數式中的變項,以幫助理解。

群作用和軌道

要理解「高階魔方」各部件的移動位置,必須先了解「群作用」和「軌道」的概念。「群作用」(Group Action)表達一個群與一個集合之間的關係。設有一個群(G, •)和一個集合X,如果對應於G中的每個元素g,都有X上的一個函數g*,並且滿足以下條件,我們便說G「作用」於X,或者說G與X構成一個「群作用」:

  1. 對G中任何兩個元素g和h以及X中任何元素x而言,(g • h)*(x) = g*(h*(x))。
  2. 對X中任何元素x而言,e*(x) = x (其中e代表G上的「單位元」)。

對於X中任一元素x,其在G的「作用」下的「軌道」(Orbit)為

Orb(x) = {y ∈ X: y = g*(x),其中g ∈ G}

請注意從集合論的角度看,「軌道」實質上是集合X上的「等價類」(equivalence class)。換句話說,一個「軌道」中的成員就是那些在G的「作用」下可互相映射到對方的成員。

把上述概念套用於魔方,那麼容易看到魔方的各種操作構成一個群,而魔方的各部件則構成一個集合,而且這個群和這個集合滿足上述「群作用」定義中的兩個條件,只要我們把g*理解為魔方某個操作g對魔方各部件的影響,並把e理解為「恆等變換」。此外,魔方任意一個部件的「軌道」就是指那些在魔方操作下可互相移到對方位置的部件。以3 × 3 × 3魔方為例,由於任何一個角塊都可以移到另一個角塊的位置,所以8個角塊構成一個軌道,用上式表達就是(請注意Orb(fru)也可以寫成Orb(bru)、Orb(flu)等):

Orb(fru) = {fru, bru, flu, blu, frd, brd, fld, bld}

同理,容易看到12個邊塊和6個中心塊也各自構成一個軌道。

對於「高階魔方」來說,情況就沒有那麼簡單。以7 × 7 × 7魔方為例,顯然並非任何中心塊都可移至另一個中心塊的位置。取一個魔方作一番試驗,便不難看到「f12」中心塊永不能移到「f14」位置,但可移到「f41」位置,因此「f12」與「f41」中心塊同屬一個軌道,但與「f14」中心塊分屬不同軌道。除了拿著魔方作試驗外,其實有一個較簡便的方法可幫助確定魔方各中心塊的軌道。這個方法是寫出某中心塊所在小面的上、下、左、右四邊小面的個數(可以是零),以下把這四個數字組成的序列稱為該小面的「特徵數列」。為方便比較,以下我們規定按順時針方向把這四個數字列出,寫成一個循環式,並使循環式的開首數字盡量小。舉例說,下圖顯示,「f12」、「f41」和「f14」這三個中心塊所在小面的「特徵數列」分別為(1, 2, 5, 4)、(1, 2, 5, 4)和(1, 4, 5, 2):

從以上例子我們觀察到一個現象:同屬一個軌道的「f12」與「f41」中心塊所在的小面有相同的「特徵數列」,而分屬不同軌道的「f12」與「f14」中心塊所在的小面則各有不同的「特徵數列」。我們可以把上述現象推廣為下列定理:

定理8:兩個小面屬於同一個軌道當且僅當它們有相同的「特徵數列」。

以下讓我們證明上述定理。首先,某個小面若發生移位,它要麼移至同一個面上的另一位置,要麼移至另一個面上的對應位置。如屬前者,這個移位必然是由該小面所在外表面的旋轉所致。由於在外表面旋轉下,位於該小面四周的其他小面必然伴隨這個小面一起旋轉,所以在旋轉前後其「特徵數列」必然保持不變;如屬後者,由於該小面移至另一個面的對應位置,所以在旋轉前後其「特徵數列」也必然保持不變。上述討論顯示,兩個小面如屬同一個軌道,它們必有相同的「特徵數列」。其次,兩個小面如屬不同軌道,它們的「特徵數列」必各不相同,這一點可以用7 × 7 × 7魔方某個面上的小面來說明,請看下圖:

上圖左面用13個兩位數(「00」至「12」)標示了13個軌道(凡屬同一個軌道的小面都用同一個兩位數來標示),這13個軌道可以用白色虛線框著的那13個小面為代表;上圖右面列出這13個軌道的名稱和「特徵數列」(註1),容易看到這13個小面的「特徵數列」各不相同。我們可以把7 × 7 × 7魔方的情況推廣到任意「n階魔方」(n > 3)。若魔方的階是奇數,即設n = 2m + 1 (m > 1),各小面的軌道為(0, 2m − 1, 2m, 1), (0, 2m − 2, 2m, 2), … (0, 0, 2m, 2m), (1, 2m − 2, 2m − 1, 2), (1, 2m − 3, 2m − 1, 3), … (1, 1, 2m − 1, 2m − 1), (2, 2m − 3, 2m − 2, 3), (2, 2m − 4, 2m − 2, 4), … (2, 2, 2m − 2, 2m − 2), … (m, m, m, m)。若魔方的階是偶數,即設n = 2m (m > 1),各小面的軌道則為(0, 2m − 2, 2m − 1, 1), (0, 2m − 3, 2m − 1, 2), … (0, 0, 2m − 1, 2m − 1), (1, 2m − 3, 2m − 2, 2), (1, 2m − 4, 2m − 2, 3), … (1, 1, 2m − 2, 2m − 2), (2, 2m − 4, 2m − 3, 3), (2, 2m − 5, 2m − 3, 4), … (2, 2, 2m − 3, 2m − 3), … (m − 1, m − 1, m, m)。容易看到,不論魔方的階是奇數還是偶數,各小面軌道的「特徵數列」各不相同。由於魔方六個面的軌道結構完全相同,所以兩個小面如屬不同軌道,不論它們是位於同一個面上,還是位於不同的面上,它們的「特徵數列」必各不相同,「定理8」證畢。

由於每個中心塊都是由單個小面組成,由此有以下定理:

定理9:兩個中心塊屬於同一個軌道當且僅當它們所在的小面有相同的「特徵數列」。

接著考慮邊塊的情況。由於每個邊塊由兩個小面組成,而且在移動邊塊的過程中,這兩個小面必然一起移動,所以我們有以下定理:

定理10兩個邊塊a和b屬於同一個軌道當且僅當a的某個小面與b的某個小面有相同的「特徵數列」,並且a的另一個小面與b的另一個小面也有相同的「特徵數列」。

上述定理的一個重要推論是,「高階魔方」任何一條邊上的兩個「對稱」邊塊(即與該條邊的中點有相同距離的兩個邊塊)都屬於同一個軌道。舉例說,在下圖中,「fu1」邊塊不僅與「fr5」邊塊同屬一個軌道,而且也與「fu5」邊塊同屬一個軌道,這是因為「fu1」和「fu5」邊塊都各自包含兩個「特徵數列」分別為(0, 5, 6, 1)和(0, 1, 5, 6)的小面。

接著考慮角塊的情況。由於每個角塊由三個小面組成,而且這三個小面的「特徵數列」全都是(0, 0, n − 1, n − 1),我們有以下定理:

定理11:全部八個角塊屬於同一個軌道。

對魔方配置的限制

本節介紹對「高階魔方」配置的一些限制,請先看其中兩條定理:

定理12設某一角塊和某一邊塊在初始狀態時的顏色標示分別為「XYZ」和「VW」,經任意扭動(包括外表面及夾心層旋轉)魔方後,該角塊的顏色標示只有以下三種可能:「XYZ」、「ZXY」和「YZX」,該邊塊的顏色標示則只有以下兩種可能:「VW」和「WV」。
定理13對一個處於初始狀態的魔方任意扭動(包括外表面及夾心層旋轉)後,各個角塊的「扭轉數總和」在「模3加法」下等於0,屬於同一個軌道的各個邊塊的「翻轉數總和」在「模2加法」下等於0。

「定理12」和「定理13」是對《群論與魔方:魔方操作的表示與運算》中「定理1」和「定理2」的修改,請特別注意「定理13」跟「定理2」的差異。在「定理2」中,我們是一次過計算所有邊塊的「翻轉數總和」,而在「定理13」中,我們要逐個軌道計算「翻轉數總和」(以下稱為「邊塊軌道翻轉數總和」),這是因為在「三階魔方」下,所有邊塊同屬一個軌道,但在「高階魔方」下,各個邊塊可能分屬不同的軌道。回顧上述網頁,「定理1」和「定理2」的證明主要依賴於3 × 3 × 3魔方各種操作對角塊和邊塊的影響以及魔方複合操作的一般特性,因此「定理1」和「定理2」的證明大致可應用於「定理12」和「定理13」的證明,唯一不同之處是「定理2」的證明曾提到3 × 3 × 3魔方六種操作的「翻轉數總和」在「模2加法」下等於0,現在我們要檢查「高階魔方」各種操作的各個「邊塊軌道翻轉數總和」是否在「模2加法」下等於0。回顧《群論與魔方:高階魔方的結構與操作》中的表4,容易看到「高階魔方」各種操作的各個「邊塊軌道翻轉數總和」要麼等於0,要麼等於4,由於0和4在「模2加法」下都等於0,上述定理得證。

接下來考慮「高階魔方」各種操作的奇偶性,為此,我們以F和Fi分別作為外表面旋轉和夾心層旋轉的代表,以計算這兩大類操作的「循環式」所含括弧的數目。以下是表4所載F和Fi的「循環式」(在下式中,j' = n − 1 − j; k' = n − 1 − k):

F =(fru1, frd2, fld1, flu21 ≤ j ≤ n-2(frj0, fdj0, flj'0, fuj'01 ≤ j ≤ floor((n-2)/2)Πj ≤ k ≤ j'-1(fjk, fk'j, fj'k', fkj')(1)
Fi =(rui1, rdi1, ldi1, lui11 ≤ j ≤ n-2(rij, dij, lj'i, uj'i)(2)

首先處理F,根據(1),F的「循環式」是三類括弧的連乘積,其中第一、二類括弧分別代表角塊和邊塊,分別有1個和n − 2個。第三類括弧則代表中心塊,為計算這類括弧的數目,我們要分別考慮兩種情況。首先考慮「偶數階魔方」的情況,設n = 2m (m > 1),根據(1)中的雙重「Π」連乘積,可知第三類括弧應共有(2m − 3) + (2m − 5) + … 1個。利用等差數列的求和公式(註2),可以求得上述數列的和等於(m − 1)2。因此對「2m階魔方」而言,F的「循環式」所含括弧的總數是1 + 2m − 2 + (m − 1)2 = m2。其次考慮「奇數階魔方」的情況,設魔方的階是2m + 1 (m > 1),則第三類括弧應共有(2m − 2) + (2m − 4) + … 2 = m(m − 1)個。因此對「2m + 1階魔方」而言,F的「循環式」所含括弧的總數是1 + 2m − 1 + m(m − 1) = m(m + 1)。

其次處理Fi,根據(2),容易看到,不論n是偶數還是奇數,Fi的「循環式」所含括弧的總數都是1 + n − 2 = n − 1。我們把以上計算結果總結為以下定理:

定理14:若魔方的階是2m (m > 1),其外表面和夾心層旋轉的「循環式」分別有m2和2m − 1個括弧;若魔方的階是2m + 1 (m > 1),則其外表面和夾心層旋轉的「循環式」分別有m(m + 1)和2m個括弧。

從以上計算結果,我們可以推算不同「高階魔方」各種操作的奇偶性。由於各種操作的「循環式」中的每個括弧都包含4個元素,這些括弧可以改寫成3個「對換」的乘積,因此只要把各種操作的「循環式」的括弧總數乘以3,便可得知這些操作的奇偶性。對「奇數階魔方」而言,其外表面和夾心層旋轉的「循環式」分別有m(m + 1)和2m個括弧,由於3m(m + 1)和3 × 2m都必然是偶數(因為m和m + 1這兩者之中必有一個是偶數),所有「奇數階魔方」的各種操作都必是偶排列。對「偶數階魔方」而言,其外表面和夾心層旋轉的「循環式」分別有m2和2m − 1個括弧,由於3m2既可以是奇數,又可以是偶數,而3(2m − 1)必然是奇數,「偶數階魔方」的各種操作有時是奇排列,有時是偶排列。由此我們有以下定理:

定理15:對「奇數階魔方」進行任意外表面旋轉及夾心層旋轉的複合結果都是偶排列。

「定理15」是對《群論與魔方:魔方操作的表示與運算》中「定理3」的修改。回顧上述網頁,「定理3」的證明依賴於以下事實:3 × 3 × 3魔方的六種外表面旋轉都是偶排列。根據上段的討論,所有「奇數階魔方」的各種外表面及夾心層旋轉都是偶排列,所以「定理3」的證明適用於所有「奇數階魔方」,從而證得「定理15」成立。此外,由於「偶數階魔方」的各種外表面及夾心層旋轉並非全是偶排列,所以「定理15」對「偶數階魔方」不成立。請注意由於「定理15」的作用,「奇數階魔方」和「偶數階魔方」的還原攻略存在一些差別,讀者在以後各章中會看到這一點。

利用上述各定理,我們可以斷定某些魔方配置是不可能的。舉例說,在下圖所示的魔方中,只有一個「fu3」邊塊發生翻轉(下圖假設除了所示方向錯誤的部件外,魔方的其他部件都處於正確的位置和朝向正確的方向):

但這是不可能的,因為根據「定理13」,Orb(fu3)的「翻轉數總和」在「模2加法」下必須等於0,而上圖所示Orb(fu3)的「翻轉數總和」是1。

接著看另一個例子。在下圖的魔方中,五個「紅藍」邊塊全部齊集於「fu」邊上,其中四個邊塊均以紅色小面向前,藍色小面朝上;只有「fu4」邊塊以藍色小面向前,紅色小面朝上:

由於上圖只顯示魔方的局部情況,無法計算各「邊塊軌道翻轉數總和」,但我們仍可根據這些邊塊所在小面的「特徵數列」斷定上圖的魔方配置是不可能的。在初始狀態時,「fu4」邊塊的紅色和藍色小面本來分別位於標有「09」和「01」的位置,其「特徵數列」分別為(0, 4, 6, 2)和(0, 2, 6, 4)。根據「定理8」,這即是說這兩個小面分屬不同軌道。但現在紅色小面位於「01」位置,藍色小面則位於「09」位置。由於在上圖中,其餘四個「紅藍」邊塊均已出現,上圖的配置只可能是「fu4」邊塊的兩個小面對調了位置,但這是不可能的,因為分屬不同軌道的小面不可能對調位置。換句話說,上圖違反了「定理8」。

跟上圖的情況不同,在下圖的魔方中,「fu」邊上的五個「紅藍」邊塊沒有違反「定理8」:

上圖的配置是本來位於「09」位置的兩個小面對調了位置,本來位於「01」位置的兩個小面也對調了位置。由於這些小面在移動前後的位置有相同的「特徵數列」,所以沒有違反「定理8」。

從以上兩圖的情況,我們可以總結出以下定理(在以下定理中,「同類邊塊」是指小面顏色相同的邊塊,例如所有「紅藍」邊塊便構成一類「同類邊塊」;「對稱狀態」則是指處於對稱位置的兩個邊塊的小面顏色朝向相同的方向,例如在上圖中,「fu4」和「fu2」邊塊便處於對稱位置,它們都以藍色小面向前,紅色小面朝上,所以處於「對稱狀態」):

定理16對一個處於初始狀態的「n階魔方」任意扭動(包括外表面及夾心層旋轉)後,若某組(共n − 2個)同類邊塊全部齊集於某條邊上,則這些邊塊必然全都處於對稱狀態。

五條重要公式

在本節筆者將介紹五條重要公式,在討論這些公式的作用時,我們將要用到上一章表4和表5中的資訊和以下等式:Bi = Fi'−1,Li = Ri'−1,Di = Ui'−1,其中1 ≤ i ≤ n − 2並且i' = n − 1 − i。在頭四條公式中,x的取值範圍一律為:1 ≤ x ≤ n − 2,但當n為奇數時,x不可以floor(n / 2)為值。另請注意,x' = n − 1 − x。

第一條公式稱為「單邊換位公式」,其「循環式」如下:

Lx−1 U2 Lx−1 U2 F2 Lx−1 F2 Rx U2 Rx−1 U2 Lx2 = (fux1, bux1)(ux*, ux'*)     (3)

從上述「循環式」可見,上述複合操作的結果是把處於對行的「fux」和「bux」邊塊對調位置並同時把它們翻轉。此外,上述操作還會把「ux*」和「ux'*」中心行對調位置。

第二條公式稱為「雙邊換位公式」,其「循環式」如下:

F2 Lx−1 F B−1 R2 F−1 B Rx Lx F B−1 R2 F−1 B Rx−1 F2 = (fux1, bux1)(fux'1, bux'1)     (4)

從上述「循環式」可見,上述複合操作的結果是把處於對行的「fux」和「bux」邊塊對調位置並同時把它們翻轉,以及把處於對行的「fux'」和「bux'」邊塊對調位置並同時把它們翻轉。

第三條公式稱為「單邊翻轉公式」,其「循環式」如下:

Rx2 B2 U2 Lx U2 Rx−1 U2 Rx U2 F2 Rx F2 Lx−1 B2 Rx2 = (fux1, fux'1)(ux*, ux'*)     (5)

從上述「循環式」可見,上述複合操作的結果是把處於同行的「fux」和「fux'」邊塊對調位置並同時把它們翻轉。此外,上述操作還會把「ux*」和「ux'*」中心行對調位置。

第四條公式稱為「雙邊翻轉公式」,其「循環式」如下:

U−1 F R−1 U F−1 Rx−1 Lx F U−1 R F−1 U Rx Lx−1 = (fux1, fux'1)(bux1, bux'1)     (6)

從上述「循環式」可見,上述複合操作的結果是把處於同行的「fux」和「fux'」邊塊對調位置並同時把它們翻轉,以及把處於同行的「bux」和「bux'」邊塊對調位置並同時把它們翻轉。

以上四條公式中的x都不可以floor(n / 2)為值(當n為奇數時),換句話說,以上四條公式不能應用於「奇數階魔方」每條邊上位於正中位置的邊塊。為彌補這方面的不足,以下提供一條可應用於正中邊塊(簡稱「中邊」)的「中邊翻轉公式」(以下公式用m代表floor(n / 2)):

F U−1 R Fm R−1 U F−1 R U−1 Fm−1 U R−1 = (fum1)(bum1)     (7)

從上述「循環式」可見,上述複合操作的結果是把處於對行的「fum」和「bum」邊塊各自翻轉,但不改變它們的位置。

綜合以上結果,上述五條公式能夠使同行或對行的一對或兩對邊塊對調位置或發生翻轉,並且不影響其他邊塊和角塊,對中心塊的影響也很輕微。讀者將會看到,這五條公式在還原「高階魔方」方面將會發揮很重要的作用。

註1:軌道的名稱可以隨意定,這裡採用Fun with Rubik's Cube網站上的軌道名稱。

註2:該公式是n(a1 + an) / 2,其中n代表數列的項數,a1和an分別代表數列的首項和尾項。



返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898593" alt="setstats" border="0" width="1" height="1"></noscript><script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>