群論で解き明かす ルービックキューブの数理(1)

群論で解き明かす
ルービックキューブの数理 (1)
川辺治之
2010 年 9 月１日
群の定義
集合 G が次の条件を満たすとき、G を群という．
(G1)
(G2)
(G3)
(G4)
演算 · : G × G → G が定義されている．
結合則 ∀f, g, h ∈ G, (f · g) · h = f · (g · h) が成り立つ．
単位元 ∃g ∈ G, ∀f ∈ G, gf = f g = f が存在する．
この g を 1 と表記する．
逆元 ∀f ∈ G, ∃g ∈ G, f · g = g · f = 1 が存在する．
この g を f −1 と表記する．
2 / 36
一人ゲーム
■
■
■
■
■
それぞれの局面では，有限個の許される手がある．
有限の手の並び (手順) で解に到達できる．
偶然に左右されたり，無作為に選ばれる手はない．
それぞれの手を行うことの効果はすべてわかっている．
それぞれの手が許されるかど うかは，現在のゲームの状態にだけ依存し
ていて，それまでの手がど うであったかに依存しない．
3 / 36
置換パズル
置換パズルとは，小片の有限集合 T を使った次の四つの条件を満たす一人
ゲームのこと．
■
■
■
■
パズルのそれぞれの手は， Zn = {1, 2, . . . , n} の元の置換に対応してい
る．(n > 1 は，パズルの構成によって決まる整数)
一つの置換に対応する手が複数ある場合，それぞれの手を行った結果の
状態は区別できない．
それぞれの手 M は「可逆」，つまり M に対して，M を行った結果の状
態から M を行う前の状態に戻す手が存在する．
T の置換 f1 に対応する手を M1 とし，T の置換 f2 に対応する手を M2 と
すると，M1 ∗ M2 (M1 に引き続いて M2 を行う) は次のど ちらかとなる．
◆
◆
ゲームの規則では許されない手
置換 f1 ∗ f2 に対応する手
4 / 36
置換パズルの例
15 パズル
■ ルービックキューブ
■ ライツアウト
■ ...
■
5 / 36
群の例
■
■
■
Cn : 位数 n の巡回群 {0, 1, . . . , n − 1}
Sn : n 次の対称群 (n 個の対象の置換全体からなる群)
An : n 次の交代群 (n 個の対象の偶置換全体からなる群)
An は Sn の指数 2 の部分群
6 / 36
ルービックキューブの単位操作
■
■
■
■
■
■
U : ルービックキューブの上面を (上から見て) 時計回りに 90 度回転さ
せる操作
D : ルービックキューブの下面を (下から見て) 時計回りに 90 度回転さ
せる操作
L : ルービックキューブの左面を時計回りに 90 度回転させる操作
R : ルービックキューブの右面を時計回りに 90 度回転させる操作
F : ルービックキューブの前面を時計回りに 90 度回転させる操作
B : ルービックキューブの後面を時計回りに 90 度回転させる操作
この略記法をシングマスター記法という．
7 / 36
部分群
群 G の部分集合 H で，G から引き継いだ演算 ∗ が群の条件 (G1)-(G4)(のす
べての G を H で置き換えたもの) を満たすものを，G の部分群といい，
H ⊂ G と表記する．
8 / 36
群の準同型写像
G1 , G2 を群とし，∗1 を G1 の群の演算とし，∗2 を G2 の群の演算とする．
関数 f : G1 → G2 は，任意の a, b ∈ G1 に対して
f (a ∗1 b) = f (a) ∗2 f (b)
が成り立つとき，準同型写像という．
9 / 36
群の同型
準同型写像 f : G1 → G2 は，それが (集合の間の関数として) 全単射となる
とき，同型写像という．
このとき，G1 と G2 は同型といい，G1 ∼
= G2 と表記する．
群 G から自分自身への同型写像を自己同型写像という．
G の自己同型写像全体の群を Aut(G) と表記する．
10 / 36
準同型写像の核
f : G1 → G2 を二つの群の間の準同型写像とする．e2 を G2 の単位元とする
とき，集合
ker(f ) = {g ∈ G1 | f (g) = e2 }
を f の核という．
ker(f ) は G1 の部分群となる．
11 / 36
ルービックキューブ群
3 × 3 × 3 ルービックキューブ群:
G = hR, L, U, D, F, Bi
H :ルービックキューブの規則に従ったすべての手順だけでなく，規則に従
わない手順もすべて含めた規則を無視したルービックキューブ群．
ルービックキューブをいったん 3 面体や 2 面体に分解して，組み立て直して
もよい．(しかし，小方体に貼られたシールをはがして貼り直すことはでき
ない．)
12 / 36
2 面体の向きと辺の番号付け
3
4
U
+
+
+
7
R
5
F
+
+
+
10
9
残りの面については，2 面体の dl ，db，lf ，lu，bl および bu 面に基準参照
印 (‘+’ 印) をつける．
13 / 36
3 面体の向きと辺の番号付け
3 面体の向きについては，下側のすべての小面と，上側のすべての小面に基
準参照印 (‘+’ 印) をつける．
5
3
F
8
+
+
R
4
D
+
7
+
2
14 / 36
キューブ理論の第 1 基本定理
次の決定過程によって，ルービックキューブの配置は決定される．
(a)
(b)
(c)
(d)
どのように 2 面体が置換されたか．
どのように 3 面体が置換されたか．
(基準参照印に対して) どの 2 面体の印が反転したか．
(基準参照印に対して) どの 3 面体の印がどれだけ (時計回りに 120 度ま
たは 240 度) 回転したか．
15 / 36
3 面体の向き
それぞれの 3 面体の 120 度単位の捻りを位数 3 の巡回群 C3 と同一視する．
v : H → C38
それぞれの手順 g ∈ H に対してその手順の結果における 3 面体の向きを対
応付ける関数
捻る角度が時計回りに 120 度の何倍かで向きを表す．
X
~v (X)
F (2,0,1,0,1,0,0,2)
U (0,0,0,0,0,0,0,0)
D (0,0,0,0,0,0,0,0)
B (0,1,0,2,0,2,1,0)
R (1,2,2,1,0,0,0,0)
L (0,0,0,0,1,2,1,2)
16 / 36
2 面体の向き
それぞれの 2 面体の反転を位数 2 の巡回群 C2 と同一視する．
w : H → C212
それぞれの手順 g ∈ H に対してその手順の結果における 2 面体の向きを対応
付ける関数
反転させる角度が 180 度の何倍かで向きを表す．
X
w(X)
~
F
(1,0,0,0,0,0,0,0,1,0,0,0)
U
(1,0,1,0,0,0,0,0,0,0,0,0)
F · U (1,0,1,0,1,0,0,0,1,0,0,0)
U · F (1,1,1,0,0,0,0,0,1,0,0,0)
B
(0,0,0,0,0,0,1,1,0,0,0,0)
D
(0,0,0,0,0,0,0,0,0,1,0,1)
R
(0,1,0,0,0,0,0,0,0,1,0,0)
L
(0,0,0,0,1,0,0,0,1,0,0,0)
17 / 36
補題:向き付けの合成
~v (h) = ρ(g)(~v(gh) − ~v (g))
より
~v (gh) = ~v (g) + ρ(g)−1 (~v (h))
w(gh)
~
についても同様．
18 / 36
(内部) 半直積
群 G の部分群 H1 および H2 が次の条件を満たすとき，G を H1 と H2 の 半
直積といい，
G = H1 ⋊ H2
と表記する．
(a) G = H1 · H2 = {h1 · h2 | h1 ∈ H1 , h2 ∈ H2 }
(b) H1 および H2 に共通の元は G の単位元 1 のみ．
(c) H1 は G の正規部分群
19 / 36
(外部) 半直積
準同型写像
φ : H2 → Aut(H1 )
が与えられたとき，集合 H1 × H2 に対する乗法を
(x1 , y1 ) · (x2 , y2 ) = (x1 · φ(y1 )(x2 ), y1 · y2 )
と定義すると，この演算により H1 × H2 は群となる．この群を (外部) 半直
積といい，H1 ⋊φ H2 と表記する．
20 / 36
H と同型な半直積
SV : 8 個の 3 面体の置換全体の集合
SE : 12 個の 2 面体の置換全体の集合
H ′ = (C38 ⋊ SV ) × (C212 ⋊ SE )
H の二つの元 h および h′ を
h = (v, r, w, s), h′ = (v ′ , r′ , w′ , s′ ) ∈ C38 × SV × C38 × SV とし，H の演算を
h · h′ = (v, r, w, s) · (v ′ , r′ , w′ , s′ ) = (v + P (r)(v ′ ), rr′ , w + P (s)(w′ ), ss′ ) と
する.
ι : H → (C38 ⋊ SV ) × (C212 ⋊ SE )
g
7−→ (v(g), ρ(g), w(g), σ(g))
は準同型写像となり，群の同型 H ∼
= H ′ を与える．
21 / 36
ルービックキューブの手順の表現
それぞれの g ∈ G を四つ組
(~v (g), ρ(g), w(g),
~
σ(g))
と同一視する．ここで
■
■
■
ρ(g) は，g によるキューブの 3 面体の集合 V の置換
σ(g) は，g によるキューブの 2 面体の集合 E の置換
v(g) および w(g) は，それぞれ 3 面体および 2 面体の向き
22 / 36
キューブ理論の第 2 基本定理
次の条件を満たすとき，そしてそのときに限り，ルービックキューブは，四
つ組 (~v , r, w,
~ s) (r ∈ S8 , s ∈ S12 , ~v ∈ C38 , w
~ ∈ C212 ) に対応する配置となるこ
とができる．
(a) sgn(r) = sgn(s) (「置換の奇偶性一致」)
(b) v1 + . . . + v8 ≡ 0 (mod 3) (3 面体の「総捻り量保存」)
(c) w1 + . . . + w12 ≡ 0 (mod 2) (2 面体の「総反転量保存」)
23 / 36
証明の概略 (=⇒)
(a) 単位操作が条件を満たすこと、および sgn が準同型であることより．
(b) 手順の長さによる帰納法
(c) 手順の長さによる帰納法
24 / 36
証明の概略 (⇐=)
■
■
■
((0, 0, 1, 0, 0, 0, −1, 0), 1, ~0, 1) の場合
g = (R−1 D 2 RB −1 U 2 B)2
(~0, 1, (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1) の場合
g = LF R−1 F −1 L−1 U 2 RU RU −1 R2 U 2 R
(~0, r, ~0, s) の場合
次の 3 種類の手順が存在すること
◆
◆
◆
任意の三つの 2 面体の巡換だけで，それ以外の小方体の向きおよび
位置を変えない手順
任意の三つの 3 面体の巡換だけで，それ以外の向きおよび位置を変
えない手順
任意の二つの 2 面体の互換および任意の二つの 3 面体の互換だけで，
それ以外の向きおよび位置を変えない手順
これらから (a) を満たす SE × SV の指数 2 の部分群が生成できる
25 / 36
第 2 基本定理からの帰結
G0 = { (~v , r, w,
~ s) | r ∈ S8 , s ∈ S12 ,
~v = (v1 , v2 , . . . , v8 ), vi ∈ {0, 1, 2}, v1 + . . . + v8 ≡ 0 (mod 3),
w
~ = (w1 , w2 , . . . , w12 ), wi ∈ {0, 1}, w1 + . . . + w12 ≡ 0 (mod 2)}
とする．G0 には，3 面体の総捻り量保存および 2 面体の総反転量保存の条
件はあるが，置換の奇偶性一致条件はない．2 項演算 · : G0 × G0 → G0 を次
のように定義する．
(~v , r, w,
~ s) · (~v ′ , r′ , w
~ ′ , s′ ) = (~v + P (r)(~v ′ ), r · r′ , w
~ + P (s)(w
~ ′ ), s · s′ )
この 2 項演算により，G0 は群となる．
[H : G0 ] = |H|/|G0 | = 6
26 / 36
ルービックキューブ群 G
次の同型写像が存在する．
G0 ∼
= (C37 ⋊ S8 ) × (C211 ⋊ S12 )
ルービックキューブ群 G は，次の準同型写像の核となる．
φ : G0
→
{1, −1}
(~v , r, w,
~ s) 7−→ sgn(r)sgn(s)
また，G は G0 の指数 2 の正規部分群で
|G| = 8! · 12! · 210 · 37
となる．
27 / 36
剰余類
G を群とし， H を G の部分群とする．群の演算を乗法 ∗ で表記して，g を
G の元とするとき，G の部分集合 g ∗ H = {g ∗ h|h ∈ H} を G における H
の左剰余類といい，G の部分集合 H ∗ g = {h ∗ g|h ∈ H} を G における H
の右剰余類という．
G が可換群の場合には，左剰余類と右剰余類は一致する．
28 / 36
完全代表系
H を G の部分群とし， C を G における H の左剰余類とする．G の元 g に
対して，C = g ∗ H が成り立つとき，g を剰余類 C の代表という．G の部分
集合 {x1 , x2 , . . . , xm } で重複なしに (すなわち，すべての xi ∗ H は互いに素
となる)
G/H = {x1 ∗ H, . . . , xm ∗ H}
となるものを完全代表系という．
29 / 36
部分群法
G = hR, L, F, B, U, Di をルービックキューブ群とし，部分群の系列
Gn = {1} ⊂ Gn−1 ⊂ · · · ⊂ G1 ⊂ G0 = G
を用いて次の処理を実行する．
■
■
与えられたルービックキューブの配置を元 g0 ∈ G とする．
すべての 0 ≤ k < n について，Gk /Gk+1 の完全代表系
Gk /Gk+1 =
rk
[
gk+1,i Gk+1
(rk > 1)
i=1
を決めておく．
30 / 36
部分群法
(初期処理) (ある i ∈ {1, . . . , r1 } について) g0 ∈ g1,i G1 となるとき，
g1 = g1,i および g1′ = g1−1 g0 とする．(g1′ ∈ G1 となる．)
■ (再帰的処理) gk′ ∈ Gk がすでに定義されていて，(ある j ∈ {1, . . . , rk }
について) gk′ ∈ gk+1,j Gk+1 となるとき，gk+1 = gk+1,j および
−1 ′
′
′
∈ Gk+1 となる．)
= gk+1
gk とする．(gk+1
gk+1
−1 g −1 g −1 . . . g −1 g となり，
■ 得られた値をすべてまとめると 1 = gn
0
n−1 n−2
1
■
g0 = g1 g2 . . . gn−1 gn
がえられる．
31 / 36
コーナー/エッジ法
G4 = {1} ⊂ G3 ⊂ G2 ⊂ G1 ⊂ G0 = G
G1 : どの 3 面体の位置を変えない部分群
■ G2 : どの 3 面体および 2 面体の位置も変えない部分群
■ G3 : どの 3 面体および 2 面体の位置も変えず，どの 3 面体の向きも変え
ない部分群
■ G4 = {1}
■
32 / 36
コーナー/エッジ法
1. g0 ∈ G を与えられたルービックキューブの配置とする．
2. g1 を，すべての 3 面体を正しい位置に移す (すなわち，捻られていても
よいが，置換によってすべての 3 面体を揃った位置にあわせる) 手順と
する．すると g1−1 g0 ∈ G1 となる．ここで g1′ = g1−1 g0 とする．
3. g2 を，すべての 2 面体を正しい位置に移し (すなわち，3 面体や 2 面体
の向きが変わってもよいが，置換によってすべての 2 面体を揃った位置
にあわせる)，3 面体の位置は変えない手順とする．すると g2−1 g1′ ∈ G2
となる．ここで g2′ = g2−1 g1′ とする．
4. g3 を，どの小方体の位置も変えずに，すべての 3 面体を「揃える」(すな
わち，2 面体を反転させてもよいが，3 面体を捻って正しい向きにする)
手順とする．すると g3−1 g2′ ∈ G3 となる．ここで g3′ = g3−1 g2′ とする．
5. g4 を，すべての 2 面体を「揃え」て (すなわち，2 面体を反転させて正
しい向きにする)，それ以外のどの小方体の位置も向きも変えない手順
とする．
6. 最終的な解は g0 = g1 g2 g3 g4 となる．
33 / 36
シスルスゥエイト 法
G1 = hR, L, F, B, U 2 , D2 i,
G2 = hR, L, F 2 , B 2 , U 2 , D2 i,
G3 = hR2 , L2 , F 2 , B 2 , U 2 , D2 i,
G4 = {1}
G2 は 3 × 3 × 2 のルービックド ミノの群と同型で，位数は (8!)2 · 12 です．
G3 は，
「 平方」群で，その位数は 213 · 34 です．
34 / 36
シスルスウェイト 法
G/G1 の完全代表系 {g1,i | 1 ≤ i ≤ n1 } で，すべての手順 g1,i が高々 7
手となるものがある．(n1 = 2048) この完全代表系に含まれる手順は，2
面体の向きを変えるだけ
■ G1 /G2 の完全代表系 {g2,i | 1 ≤ i ≤ n2 } で，すべての手順 g2,i が高々 13
手となるものがある．(n2 = 1082565) この完全代表系に含まれる手順
は，3 面体の向きを変えるだけ
■ G2 /G3 の完全代表系 {g3,i | 1 ≤ i ≤ n3 } で，すべての手順 g3,i が高々 15
手となるものがある．(n3 = 29400) この完全代表系に含まれる手順は，
すべての 3 面体および 2 面体を正しい位置に移す．
■ G3 /G4 の完全代表系 {g4,i | 1 ≤ i ≤ n4 } で，すべての手順 g4,i が高々 17
手となるものがある．(n4 = 663552)
■
これより，ルービックキューブのどんな配置も，高々 7 + 13 + 15 + 17 = 52
手で解くことができる．
35 / 36
コシエンバ法
「 2 段階アルゴ リズム」部分群の系列の群を二つに減らした．
G0 = hL, R, F, B, U, Di
G1 = hL, R, F 2 , B 2 , U 2 , D2 i
G2 = 1
第 1 段階 : 撹乱された配置を G1 の元に移す手順を探します．G1 は，3 面体
および 2 面体の向きに制約を課し，上下方向の中間層にある 2 面体を同じ中
間層に移す元からなります．この目的の状態を見つけるために，プログラム
は反復深化 A*(IDA*) 法と呼ばれる探索アルゴ リズムを使用する．(探索する
手順の長さを延ばしながら表を引いてすべての手順上を反復する．)
第 2 段階 : 部分群 G1 に含まれる配置に対して，この部分群に含まれる手順
だけを使って，すべての面が揃った状態にする．この段階では，8 個の 3 面
体の置換，上面および下面にある 8 個の 2 面体の置換，および上下方向の中
間層にある 4 個の 2 面体の置換を行う．
36 / 36