置換群とゲーム

応用代数講義ウェッブ付録Ｂ
置換群とゲーム
Ten Billion の解法解説
以下，次のような図表示を用います．左がゲームの模式図で，その図中の cut と書かれた線で切って円柱を
展開した図が右です．
cut
U+
L+
ここで，U+ は上の段を図の矢印の向きに回す操作，U− はその逆回しの操作を，L+ は下の段を図の矢印の向
きに回す操作，L− はその逆回しの操作を表します．また，↑ は三つのコラムを上に押し上げる操作を，↓ は
下に下げる操作を表します．従って ↑ U+ ↓ は，三つのコラムを上に押し上げたまま上の段を右に回し，その
後で三つのコラムを下に戻すことを意味します．
種々の基本操作
上 :=↑ U+ ↓ U−
下 :=↑ L+ ↓ L−
1
A := 上下上−1 下−1 =↑ U+ ↓ U− ↑ L+ ↓ L− U+ ↑ U− ↓ L+ ↑ L− ↓
B := A0 =↑ U− ↓ U+ ↑ L− ↓ L+ U− ↑ U+ ↓ L− ↑ L+ ↓
(A0 は A の中の回転の向きをすべて逆にする操作を意味します.)
A2
B2
U− A2 U+ により, ５個のコラムの真中の３個に巡回置換を施すことができます. A, B, A−1 , B−1 , A2 , B2 を
うまく組み合わせて, まず黒い珠を三つとも下に納めてしまい, 上の方を揃えて行くのが一番早い解法のよう
です.
Rubik キューブについて
以下の説明では次の操作を使います．これらは教科書に書かれている S48 の部分群としての表現とは後で説
明するような違いがありますが，実際にキューブを操作するにはこの方が便利で，かつキューブのすべての状
態を忠実に表現できます．座標軸の位置が普通の数学書の挿絵で使われているものと異なっていますが，右手
系を保ち，かつ右効きの人が回しやすいように選ばれています．慣れないうちは x 軸と y 軸を間違えますが，
慣れるとこの方が回しやすいと思います．
キューブが下図のように見える位置で手の平の上に置くとき，
x 回転
図のように一つのスライスだけを x 軸を中心に
正の向きに 90◦ 回転させるものを，順に x1 , x2 ,
x3 で表します．
x2 は教科書の表現と異なり，中心のブロックを
移動させてしまうことに注意しましょう．
x21 は x1 を続けて２回行うことを意味します．
従って 180◦ の回転です．x31 は x−1
1 ，すなわち，
x 軸を中心に負の向きに 90◦ 回転させるのと同
等です．
z
x
X3 X2 X1
y
2
z
Y1
Y2
y 回転
図のように一つのスライスだけを y 軸を中心に
正の向きに 90◦ 回転させるものを，順に y1 , y2 ,
y3 で表します．
y2 も中心のブロックを移動させます．
x
Y3
y
z
z 回転
x
Z3
図のように一つのスライスだけを z 軸を中心に
◦
正の向きに 90 回転させるものを，順に z1 , z2 ,
Z2
y
z3 で表します．
Z1
z2 も中心のブロックを移動させます．
以下，これらの結合操作を x1 y22 z3−1 のように記しますが，::::::::::::
左から右へ, すなわち，x1 をまず行って，次に
y2 を２回，最後に z3 の逆向きを１回，実行するものとします．置換群の作用を写像の記法と見ると右から左
の方が正統的ですが，実際の操作としては左から右の方がやりやすいのです．
また，途中でキューブを持ち変えたりすると，変換の意味は全く変わってしまうので，一連の合成変換を行っ
ている間は，キューブの方向が常に一定になるように持たねばなりません．
しかし，合成変換を始める前は，適当にキューブを回して必要なブロックがこの変換で臨むように動くよう
な位置に持ってゆくのです．それにより，覚える (習熟する) 変換の種類をなるべく少なくするのが速く解く
コツです．
【角から始める３×３ rubik キューブの解法】 rubik キューブにはいろんな解法がありますが，以下の方法
はかなり群論好みのものです．
1 まず，１面の４隅をそろえる．次の操作で適当なブロックを適当な位置の適当な向きに持って来ます．ど
⃝
れが適当なブロックかの判定は各面の中心の色を見て判断します．
z
x
z
x
y
A = y1 x1 y1−1
z
x
y
y
B = x3 y3 x−1
3
2
C = y3−1 z1−1 y3 x−1
1 z1 x1
必要なブロックが真下になければ，もちろん，下面を回転させて上のような位置に持って来てから操作を行い
ます．これらの操作は簡単ですが，:::::::::::::::::::::::::::::::::
上面の角以外は動かしてしまうので，完成しかかったキューブに対して適
用してはいけません．
2 ４隅の揃った面を下にし，上面の４隅を，まず位置だけ正しいものにする．(向きは後で直します.) (向き
⃝
は考えず) 位置がすべて合っているか，一組みだけ位置が入れ替わっているか, 交差してしまっているかのい
ずれかなので，次図の変換を１回または２回用いて位置を入れ替えます．
3
z
x
y
2
D = z32 y3−1 z3−1 y3 z3 x−1
1 y3 x1 z3
3 角を回して向きも合わせる．次の変換のいずれかを適当に選んだ角の組に対して適用することを繰り返す
⃝
と, 必ず上面のすべての角が合う．
z
z
x
x
y
y
E = (y3−1 z3 )3 (y3 z3−1 )3
E −1 = (z3 y3−1 )3 (z3−1 y3 )3
ここで，例えば (y3−1 z3 )3 は y3−1 z3 を３回繰り返す意味です．二つ目の変換は最初の変換の逆変換ですが, 暗
算で計算するとよく間違えるので具体的に書いておきました.
以上で８個の角が向きも込めて揃いました．２×２キューブの場合はこれで完成です．
4 次の変換で上面の辺を揃える．これらの変換は下面の辺を動かしてしまうので，上面の辺を揃えるのにし
⃝
か使えません．実用的にはどれか一つだけを記憶し，他の場合は適当に動かしてその形にしてからそれを適用
して元に戻すのが良いようです．
z
x
z
z
x
y
x
y
−1
F = x1 y2 x−1
1 y2
x
y
H = z1 y2−1 z1−1 y2
−1
G = x−1
1 y2 x1 y2
z
y
J = x21 y2 x21 y2−1
移動する辺が上面に含まれてしまっている場合は，最後の辺の調整のための変換を使うのは複雑すぎるので，
次の変換で一旦それを下面に移動させてから上の変換を使う方が速いでしょう．
z
x
y
K = y2−1 z1 y2 z1−1
以上で１面と反対側の面の角が揃いました．揃った面を下にして作業を続けます．
5 次の変換およびその逆変換で中段の辺を揃える．
⃝
4
z
x
y
−1 2
−1
L = y1−1 x−1
1 y2 x1 y2 x1 y1
逆変換は上を右から左に，個々の変換を逆変換で置き換えながら読めばよろしい．
6 次の二つの変換およびそれらの逆変換で上段の辺を揃える．どうしてもうまく行かないときは，最後の変
⃝
換も使ってみてください．
z
z
x
x
y
y
M = x21 z3−1 y2 z32 y2−1 z3−1 x21
z
N = y2−1 z3 y2 z32 y2−1 z3 y2
z
x
x
y
y
2 −1
2 −1
2 −1
P = y2 x23 y2−1 x−1
3 z3 y2 x3 y2 x3 y2 x3 y2 z3 x3
MN
これで３×３キューブは完成です．
おまけ途中で手順を間違えて，折角そろっていた角だけが狂ってしまった場合，最初からやり直すのは悲し
いですね．そういうときは，次の変換も利用しましょう．
z
z
x
x
y
−1 −1
−1
−1
Q = x−1
1 x3 z3 x1 z3 x3 z3 x1 z3 x1
y
−1 2
2 −1 −1 2
2
2 −1
R = [x−1
1 z3 x1 z3 x1 z3 x1 z3 ][x1 z3 y2 z3 y2 z3 x1 ]
【４×４キューブの解法】以下の記述では，次の記号を使います：
5
z
x 回転
図のように一つのスライスだけを x 軸を中心に
正の向きに 90◦ 回転させるものを，順に x1 , x2 ,
x3 , x4 で表します．真中の二つのスライスをま
とめて動かすことにすると，x1 , x2 x3 , x4 が３
×３キューブのときの x1 , x2 , x3 に相当します．
x
X4 X3 X2 X1
y
z
y 回転
図のように一つのスライスだけを y 軸を中心に
正の向きに 90◦ 回転させるものを，順に y1 , y2 ,
y3 , y4 で表します．３×３キューブの動きとの
対応も同様です．
x
Y4
Y3
Y1
Y2
y
z
z 回転
図のように一つのスライスだけを z 軸を中心に
正の向きに 90◦ 回転させるものを，順に z1 , z2 ,
z3 , z4 で表します．
x
y
Z4
Z3
Z2
Z1
以下，３×３キューブの解法を拡張する形で４×４キューブの解法を述べます．
1 まず，いろんな向きに置いたキューブに対し，次の操作を繰り返すことにより，各面の中心の４個を正し
⃝
い色に揃えます．３×３と異なり，４×４ではここが自由に動くので，後で３×３の手順を使うためにとりあ
えず中心を揃えるのです．下の操作は単純ですが，角を動かしてしまうので，真っ先に行う必要があります．
どの色をどこに集めればよいかは，角のブロックをよく見れば分かります．また，中央の４個のブロックの他
の位置のものを交換したければ，これらの面を適当に回転してからこの操作を施します．
z
x
y
S = (z1 z2 )x1 (z1−1 z2−1 )
ここで，例えば (z1 z2 ) のように括弧で括ったところは，二つのスライスを同じ方向に同じ角度だけ同時に回
転する操作を表します．もちろん，スライス毎に独立に動かしても結果は同じで，かつ可換なのでどちらを先
にしてもよいのですが，非能率です．なお，最後に体面同士で一つのブロックだけが入れ替わった状態になっ
た場合も，途中の揃っている面を一度中継して上の変換で入れ替えるのが簡単です．
6
2 次に，下の変換を用いて辺を二つずつペアとなるようにします．これらの変換も角を壊してしまうので，
⃝
先にやっておきます．角だけでなく，下の変換はそれぞれ図の網掛けした辺ブロックもペアで動かしてしまい
ますが，この段階ではそれは気にしないことにします．動かしたくない辺は予め適当な回転でどかしてからこ
の操作を行い，終わった後で回転を戻すとよいでしょう．
z
z
x
x
y
y
−1 −1
T = (z1 z2 )x1 z4−1 x−1
1 (z1 z2 )
−1
U = z3 x1 z4−1 x−1
1 z3
最後に，ペアになっていない辺が二つだけになったら，次図左の変換で一気にペアにします．もし右のように
なっていたら，例えばそこに示されたような３×３の簡単な変換で左の形に帰着できます．
z
z
x
x
y
y
2 −1 −1 −1
V = (z1 z2 )x1 z4 x−1
1 y4 z4 y4 (z1 z2 )
x21 y1−1 z1−1 x1
3 ３×３の場合の解法を使って揃えます．もしここまで来てから中央の４ブロックの色が正しく無かったら，
⃝
次の変換で辺のペアを壊さずに隣同士の中央４ブロックを交換できます．(ただし，この変換で辺はペアで，ま
た角も動くので，後にせず今修正しておきましょう．)
z
x
y
S 2 x21 y42 S 2 x21 y1 T
さて，３×３キューブに対する変換，例えば A から，４×４キューブの対応する変換 A0 を作るには，A の
手順中で，






 z1 −→ z1 ,
 y1 −→ y1 ,
 x1 −→ x1 ,
z2 −→ (z2 z3 ),
y2 −→ (y2 y3 ),
x2 −→ (x2 x3 ),



 z −→ z
 y −→ y
 x −→ x
3
4
3
4
3
4
等々という置き換えをします．これで，隣り合っているペアの辺を二つ一緒に動かすことができます．
7
4 ４×４の場合は，ここで３×３では有り得ないようなことが起こることがあります．下左のように，一つ
⃝
の面の相対する辺ブロックだけが入れ替わっており，他は全部揃ったところです．同様に下右は，一つの辺ブ
ロックだけが位置は同じで逆転しているものです．この他に，両方を合成した状態が有ります．(これらはクラ
インの四元群として含まれている訳です．) いずれも３×３のときは，このようなことは起こりません．これ
らはそれぞれ示されたようなややこしい変換で修正できます．左の変換では，実際には二つの辺ブロックはま
とめて移動されるのではなく，お互いに入れ替わるのです．
z
z
x
x
y
y
W = y32 z42 y32 (z3 z4 )2 y32 z32
α
−1
−1
2
2
2
α = βx1 Y AZBX z4 Dz4 Dz4 Ez4 GZJZz1 z2 z3 GX −1 y4 Z
−1 N −1 y 2 Z −1 P x x−1 M −1 x X −1 M Z
M Z 2 M −1 Y M x−1
4 1
1
4
1 Z
ここで β は下の変換を表します．最後の変換は非常にややこしくて，最後まで間違えずに遂行するのはほと
んど絶望的なので，このような状態にならないように作戦を立てるのが賢明です．それには，上面下面の辺が
揃ったときに，側柱の稜の状態を見て，x1 面の二つの辺対が同じ色に揃っているか，または揃ったときに対
面同士になるはずの色ならば 0, もし，揃ったときの隣の面の色同士なら 1 とし，x4 面についても同様の値を
出して，それらの総計が偶数なら大丈夫です．もし奇数だと，このまま３×３の操作を続けてゆくと上のよう
になってしまうので，一旦次の変換で隅奇を入れ替えてから続けます：
β = z1 z2 y12 z1 z2 y12 x24 z1 z2 y12 z1 z2 y12 z12 z22 x24 z1−1 z2−1 x1 z1 z2 y4−1 z4−1 y4 z1−1 z2−1
４×４キューブは３×３に比べて動きが悪いので，y32 などをやるのは大変です．２乗の操作は 180◦ の回転な
ので，どちらに回しても同じ結果になるので，動きやすい方に回しましょう．ひっかかっているのを無理に回す
と分解します．(数学と工学の違いが体験できます. (^^;) 壊さないようにブロックを微調整していると，最初
に持っていた方向を見失うことがあります．そんなときのために，一連の操作を開始するときに予備のキュー
ブを同じ向きにして参照用に置いておくとよいでしょう．
【補遺】キューブの難しさは，同じ色のものが動いても区別できないことからも来ています．面に番号を書き
込んでしまうと，そのからくりが見えて来ます．３×３キューブでも色だけを見ていては分からないような変
換が存在します．この変換は４×４に適用すれば，中心の４個のブロックを回転させる効果がありますが，３
×３キューブでも，百円ショップなどで売っている面に模様の描かれた変種のキューブだと，実際にこの動き
が分かります．純正品でも白い面の中央に描かれた Rubik のサインをこの変換で 90◦ 回転させることができ
ます．
8
z
x
y
−1
−1 −1
γ = x−1
2 y2 x2 y2 z2 y2 z2 y2
これを次のように組み合わせると，一つの対面だけの中央４ブロックを 180◦ 回転させることができます．こ
こで，X, Y はそれぞれキューブ全体を正の向きに 90◦ 回転させる操作を表し，３×３キューブでは x1 x2 x3
と一致します．４×４キューブの場合は，これに対応する変換は一つの対面だけの中央４ブロックを図のよう
に入れ替えてくれます．
z
x
y
γY γ −1 X −1 γXY −1
しかし，４×４キューブのときは，実は一つの面の中央４ブロックだけを 180◦ 回転させることができます：
−1 −1 2
δ = y42 z4−1 x2 x3 z42 x−1
2 x3 z4 y4
という変換を定義したとき，
z
x
y
δZM −1 Z −1
追加参考文献
３×３キューブの解法については下記を参考にしました：
[1] 小倉式「謎の六面体の最短組み立て方」，小倉清治，週間文春, 1984 年 12 月?, pp. 144 – 148.
週刊誌の一般向け記事ですが，群論の専門家，近藤武先生が，
“ この人は群論を知っているのか ”と感心
するほど，群論から見て合理的な解法だそうです．
４×４キューブの解法については下記を参考にしました：
9
[2] “Rubik’s Cube の解法”, ３年角刀牛虫, カーマトーラス Vol.17, 1984, pp.84 – 131.
カーマトーラスは数学科学生の同人誌で，数学的な随筆が沢山載っています．同期生の京大教授小林俊行
さんのお話では，この著者名は星野明雄さんのペンネームだそうです．この論文は一般のｎ×ｎキュー
ブの帰納法による解法を記した最初の文献かもしれません．その他にもキューブに関する面白い考察が
沢山載っています．
10

Download Report