タイトルなっっっっっっが！
これはISer Advent Calendar 2019 - Adventarの9日目の記事として書かれました。
タイトル通り、ルービックキューブに関する"証明"をします。
副作用として、この記事を読むとルービックキューブが揃えられるようになります。
長すぎて前後編になりました。揃える話は後編です。

まえがき(ISer向け,分からん人はすっ飛ばせください)

こんにちは。IS 20erの496です(と言っても「誰だお前」でしょうが)。
自己紹介で「ルービックキューブ好きです」とボソッと言ったまま布教活動をしていないので、この機会に張り切って(?)布教記事を書こう！と思ったはいいんですが、去年のAdvent Carendarとかを眺めるとりじょーらしいガチ勢の記事が多数派でうわーーーーーってなった結果ある程度学問ある程度趣味みたいな感じでこれに落ち着きました。
途中の説明は分かりやすさをそれなりに大事にしたので、頭の回転が速いISの人々にはもっさり感があるかもしれませんがご容赦ください。

なにはともあれ、ゆっくりしていってね。

注. ごめんなさい、長すぎて半分くらいしか終わってないです！後編をお楽しみに*1

Introduction

ルービックキューブとは何か、を知らない人はいないと想定している*2のでさくさく本題に入ります。
何の予備知識もなくルービックキューブを揃えるのは難しいです。何も見ずに解けたら本当に天才だと思います(努力家的なものか謎の閃きかは差し置いて)。昔の(?)ルービックキューブにはよくこんな感じの宣伝文句が付いていました。

あり得る状態は4000京通り以上！君の頭脳はこれを解けるか！？

理系の心がある人ならすぐに気になるでしょう。実際にはあり得る状態は何通りなのか？？
先に答えを書いておくと(既にタイトルに書かれているが)、
4325京2003兆2744億8985万6000通り*3、ということになっています。この記事では、この数字が如何にして導出されるのかをできる限り厳密に考えていきたいと思います。

単純な総数の考察

注. 簡単のため、以降ルービックキューブのことを単にキューブと呼ぶことがあります*4。

組合せ論的に考えれば、各パーツの配置のしかたの総数をカウントすれば良さそうな気がしますね。そのためにはまず

ルービックキューブにはどんなパーツがいくつあるのか？？

ということを考える必要があります。キューブを手にとったり分解したりしたことがない人にとっては意外かもしれませんが、ルービックキューブのパーツは $3 \times 3 \times 3 = 27$ 個ではなく、 $21$ 個しかありません。その内訳は、

立方体の頂点に位置するパーツ8個(以降コーナーと呼びます)
立方体の辺(の中心)に位置するパーツ12個(以降エッジと呼びます)
立方体の6つの面の中心を張り合わせたパーツ1個(以降コアと呼びます)

となっています。コアの向きを固定して考えると、結局キューブのパーツ配置の総数とは固定したコアに対して20個のパーツ(コーナーとエッジ)を配置する方法の総数であるといえます。最初からこの結論を述べても議論は進められるのですが、キューブの構造に対して実感を持つと分かりやすくなるかなーと思います。

では分解したキューブを手元に置い(たと想像し)て、20個のパーツを配置することを考えましょう。
コーナーの位置にエッジを置いたりエッジの位置にコーナーを置いたりすることはできないので、これらを別々に自由に配置すると

コーナーは8個あるので、その配置は $8! = 8\times 7 \times \cdots \times 2 \times 1 = 40,320$ 通り
エッジは12個あるので、その配置は $12! = 12 \times 11 \times \cdots \times 2 \times 1 = 479,001,600$ 通り
それらを掛けて $40,320 \times 479,001,600 = 19,313,344,512,000$ 通り

の配置があることになりそうです。もうこの時点でその辺の電卓では表示できない桁数になっています*5が、これで終わりではありません。キューブのパーツ配置には位置だけでなく向きの情報が含まれます。同じ位置でもコーナーには3通りの向きが、エッジには2通りの向きがあるので、向き込みでの配置を全て自由に選ぶ方法は

コーナー8個について $3 ^ 8 = 3 \times 3 \times \cdots (計8個) \cdots \times 3 = 6561$ 通り
エッジ12個について $2 ^ {12} = 2 \times 2 \times \cdots (計12個) \cdots \times 2 = 4096$ 通り
それらを先ほどの総数に掛けて $19,313,344,512,000 \times 6561 \times 4096 = 519,024,039,293,878,272,000$ 通り

あることになります。組合せ爆発の何たるかを痛感する結果ですね*6。
さて、よく見るとこの数字、冒頭に挙げた"正解"よりもかなり大きい数字になってしまっています。勘のいい方はお気づきかと思いますが、実はいま求めたキューブのパーツ配置たちの中には、正当な方法*7で揃えることができない、言わば"あり得ない"状態が大量に存在するのです。というわけで、ルービックキューブにおいて"あり得る"状態の数を知るためには、"あり得ない"状態がどれくらいあるのかを考える必要が出てきます。

注.以降、"あり得る"状態、"あり得ない"状態という言葉を上の文章で定義されたものとして頻繁に使います。

用語導入

ここからの話を円滑に進めるために、キューブの面、パーツ、操作などの呼称を書いておきます*8。
なお、書いた後で分かったのですが位置と回転に関する用語を使う場面は少ないので、適当に見ておいて定義が分からなくなったら戻ってくるくらいでも良さそうです。

面、色

キューブ全体の向き(コアの向き)を固定したとき、

上にある面をU面(Up)
下にある面をD面(Down)
右にある面をR面(Right)
左にある面をL面(Left)
手前にある面をF面(Front)
奥にある面をB面(Back)

と呼びます。
また、X面の中心にある色をX面色と呼びます。キューブ全体の向きを変えない限り、各面を回転しても各面の色は変わりません。

パーツ位置

コーナーおよびエッジパーツの位置を、面の名前を並べて表現します。微妙に分かりづらいので例として図を作りました*9。

f:id:goldenfalcon496:20191208010215p:plain — 図1

図1において、赤いパーツ(コーナー)の位置をUFR、青いパーツ(エッジ)の位置をUFと呼ぶことになります。

回転記号

ある $X$ 面を時計回りに回転させる操作を $X$ 、反時計回りに回転させる操作を $X'$ 、180度回転させる操作を $X2$ と書きます。U,R,F面の回転は直感的に分かりやすいですが、反対側の面はやや分かりにくいです。いい感じの図解はこれなどがあります*10。
とは言いましたが、この記事では回転記号をそこまで多用しないのでのんびり見てください。

(参考).より一般に、回転記号の羅列で表される一連の操作 $X$ の"逆再生"を $X'$ 、操作 $X$ を2回行うことを $X2$ などと書くことも多いです。例えば、以下のようになります。

$(RUR'U')' = URU'R'$
$(RUR'U')2 = RUR'U'RUR'U'$

"あり得ない"状態の条件〜パーツ配置の制約

さて、本題に戻ってキューブの"あり得ない"状態について考えましょう。
この手の証明にありがちな手法ですが、キューブの操作に対する状態の"不変量"を見つけることで、一部のパーツ配置が"あり得ない"ことを証明できます。具体的にはこんな感じですね。

キューブの各状態(パーツ配置) $x$ に対して必ず1つ定められる値 $P(x)$ が存在する
状態 $x$ からどのような操作(回転)をしても $P(x)$ の値は変化しない(不変量である)
ある状態 $x$ と完成状態 $x _ 0$ に対し、 $P(x) \ne P(x _ 0)$ とする。
$P$ は不変量であるので、 $x$ からどのような操作をしても $x _ 0$ には到達できない！

この節ではキューブの状態に3つの不変量が存在することを示し、それを用いて「あり得ない状態が少なくともこれくらい存在する」ということを証明します。といっても、いきなり無から不変量を見つけるのは天才的閃きを要するので、少しばかり経験知に頼ることにして、

このような状態は"あり得ない"状態であることが経験的に知られている
その背景にはある種の不変量があることを証明する

といった感じで進めていきます。

パーツの位置に関する不変量

経験知1：完成状態に対してある二つのパーツの位置のみが入れ替わっている状態は"あり得ない"状態であることが知られている。

こう書くと少しあからさまな感じがしてしまいますが、今からするのは置換の符号の話です。しばらくパーツの向きのことは忘れて、位置だけについて考えることにしましょう。キューブの各面を回転させると、パーツたちの位置が変化しますね。これは一種の置換になっています。具体的には

ある面を90度回転させる操作において、
その面に属する4つのコーナーが巡回置換*11され、
その面に属する4つのエッジも巡回置換される
他のパーツの位置は変わらない

といったところです。置換の符号を観察すると、4つの要素の巡回置換は奇置換(3回の入れ替えで実現できる)なので、コーナーもエッジも奇置換されていますが、ここで重要なのはコーナーとエッジの置換を合わせて20個の要素の置換として見ると、偶置換になっているということです。
すると、状態 $x$ に対して、(完成状態 $x _ 0$ から見たときの)パーツ位置の置換の符号を $sgn(x)$ とおけば*12、 $sgn(x)$ は各面の90度回転操作に対して不変量です。さらに言えば全ての回転操作は90度回転操作の羅列で表現できるので、 $sgn(x)$ はいかなる操作に対しても不変量です。これを不変量論法に当てはめれば、 $sgn(x _ 0) = 1$ (何もしない置換は偶置換)なので、

$sgn(x) = -1$ であるような状態 $x$ は"あり得ない"状態である。

ということができます。

注.コーナーやエッジの置換だけを見ると奇置換なので、ここから不変量を作り出すことはできません。実際、コーナーの位置だけみると奇置換でエッジの位置だけみても奇置換であるような"あり得る"状態は存在します。筆者にとってはこれは若干の違和感を伴う事実なのですが、そう思わない人もいるかもしれません。

コーナーの向きに関する不変量

経験知2：完成状態から1つのコーナーの向きのみを変えた状態は"あり得ない"状態であることが知られている。

余談. これはキューブ界隈では理論にあまり興味がない人も含めて大半が知っている有名な話で、なぜかというと実際に起きてしまう確率が高いからです。最近のキューブは柔軟なので乱暴に扱うとコーナーの向きがポロっと変わってしまうこと(これをピボットといいます。この言葉は便利なので以下でちょいちょい使われます)があり、そうすると永久に揃わないという事態が発生し得るので注意が必要です。実はキューブの早解き競技の正式なルールには、競技中にコーナーの向きが変わってしまった場合の規定がちゃんと書かれていたりします。

閑話休題。上記の経験知2から、コーナーの向きについて何か不変量がありそうな気がしてきます。これを正確に定義して、不変量であることを示すのは少々厄介です。何が問題なのかというと、各コーナーの向きのことだけを考えたいのに位置がどんどん変わってしまうということです。向きを表す量というのは"本来の向き"に対してどれくらい差異があるかによって定義したいものですが、あるパーツが元々あった位置に存在しない場合、そのパーツには"本来の向き"などというものがなく、定義に困ってしまうのです。

そこで全コーナーの全位置について、勝手に"本来の向き"(というか"基準の向き")を決めてしまいます。これは簡潔であればあるほど後々の議論が楽になります。今回はU面色とD面色に注目して定義を作ってみます。

コーナーに対する基準の向きの定義：コーナー(パーツ) $X$ と位置 $L$ に対して、
・ $X$ は必ずU面色の面またはD面色の面(これは1×1マスのこと)を1つだけ持つ。この面を $X _ {UD}$ とする。
・ $L$ は必ずU面の4つのコーナー位置か、D面の4つのコーナー位置のいずれかに属する。
・以上から、 $X$ の $L$ における3通りの向きのうち、 $X _ {UD}$ がU面またはD面を向くような向きが1つだけ存在する。
この向きをパーツ $X$ の位置 $L$ における基準の向き $B(X,L)$ とする。

f:id:goldenfalcon496:20191209111441p:plain — コーナーの基準面の向き

文章にするともにょもにょしますが、定義自体は簡潔だと思います(多分)。あまり参考にならないかもしれませんが、完成時に図の黄色い部分にあった面 $X _ {UD}$ (1×1マス)が現在も黄色い部分にあればその位置を問わず基準の向きであるとみなすイメージです。
これを使って、目論見通り各コーナーの向きを示す量を基準の向きからのズレで表現し、さらにそれらの合計として状態全体としてのコーナーの向きに関する量の定義をします。コーナーの向きは3通りであり、3回同じ向きにピボットすると元に戻るので $mod \, 3$ で考えるのが妥当です。

コーナーの回転値の定義：コーナー $X$ が位置 $L$ にあるとき、 $X$ の回転値 $P(X,L)$ を以下のように定義する。
基準の向き $B(X,L)$ に対して $X$ が同じ向きならば $P(X,L)=0$ 、右に回転しているならば $P(X,L)=1$ 、左に回転しているならば $P(X,L)=2$ 。
状態のピボット値の定義：状態 $x$ に対して、各コーナー $X$ とその位置 $L _ X$ の組(8つ存在)全ての $P(X,L _ X)$ の総和を3で割った余りを $pivot(x)$ とおく。

やっぱりもにょもにょしますが素直な定義を文章に起こそうとするとこうなってしまうんですよね・・・。あとはこれがうまく不変量になってくれればいいのですが、その証明も逐一やろうとすると大変です。というか本当に正しいのかわからなくなってきます。いかなる回転値の組合せを持つ状態 $x$ にいかなる回転を加えても $pivot(x)$ は変化しない、ということを真っ向から示すのはもはや全探索的な何かになってしまっています。そこで、簡潔な証明にするため以下の事実を念頭におきます。

適当な回転操作 $M$ の前後におけるコーナー $X$ の位置と向きに注目する。
$X$ を右(左)にピボットさせる→ $M$ を行う→ $X$ を左(右)にピボットさせる、という操作全体の結果は $M$ のみを行った場合の結果と変わらない。
また、 $X$ を左右に1回ずつピボットさせると、合計で $pivot(x)$ の増減は相殺される。

これは割と当たり前なことです。要はピボットというズルをして、後でそれを元に戻しているだけです。これを用いると、単に $M$ を実行するのではなく、とりあえず全コーナーの回転値が0になるようにピボットしておいて、本命の $M$ をして、さっきズルをした分を全部元に戻すということが考えられます。前後に挿入したピボット操作による $pivot(x)$ の増減は相殺するので、 $M$ で $pivot(x)$ が変化しなければOKです。つまり、示すべきは以下です：

状態 $x$ において全てのコーナーの回転値が0であるとき、いかなる回転をしても $pivot(x)$ は変化しない。

とても強い仮定が使えるのですぐに示せます。しかも前節同様90度回転についてだけ示せれば十分です。

U,D面の回転では各コーナーの回転値は0を保ち、 $pivot(x)$ もそのままです。
U,D面以外の回転では巻き込まれたコーナー4つの回転値が1,1,2,2という組み合わせになり、 $pivot(x)=0$ は変化しません。

おわりです。すごいズルをした気分ですね。

やたらと長くなりましたがコーナーの向きに関して $pivot(x)$ という不変量が存在することが分かりました。不変量論法を使えば、

$pivot(x)=1 or \, 2$ であるような状態 $x$ は"あり得ない"状態である。

といえます $\left( \because pivot(x _ 0) = 0 \right)$ 。

エッジの向きに関する不変量

経験知3：完成状態からあるエッジの向きだけを反転させた状態は"あり得ない"状態であることが知られている。

今度はエッジの向きを見ます。コーナーと要領はほぼ同じです。基準の向きを決め、状態に対する量を定義し、不変量であることを証明します。向きが2つしかないので、基準の向きを定義するとほぼ即座に向きを示す量の定義が出ます。(当然 $mod \, 2$ )
しかし、基準の向きの定義がコーナーのとき以上に厄介です。前節が長すぎたのでサクサク行きましょう。
(前節と同じ記号が出ますがご容赦ください)

エッジに対する基準の向きの定義*13：エッジ(パーツ) $X$ と位置 $L$ に対して、
・ $X$ がUorD面色の面を含むならそれを $X _ {UD}$ とおく。
・そうでない場合、 $X$ のForB面色の面を $X _ {UD}$ とおく。これで $X _ {UD}$ は定まる。
・ $L$ がUorD面上に存在している場合、 $X _ {UD}$ がUorD面を向いているような向きが基準の向き $B(X,L)$ 。
・そうでない場合、 $X _ {UD}$ がForB面を向いているような向きが基準の向き $B(X,L)$ 。

f:id:goldenfalcon496:20191209112707p:plain — エッジの基準面の向き

全てのエッジがUorD面に属してはいないので定義が長くなります。完成時に図の黄色い部分にあった面が $X _ {UD}$ です。
続いて一気に全体の向きの量の合計として $flip(x)$ というものを定義してしまいます。

エッジのフリップ値*14の定義：状態 $x$ に対して、エッジ $X$ とその位置 $L _ X$ の組(12個存在)のうち、 $X$ の向きが基準 $B(X,L)$ と異なっているもの個数を2で割った余りを $flip(x)$ とおく。

不変量である証明にもコーナーのときと同様のアイデアが流用できます。同じエッジの反転を操作の前後に挿入しても結果は変わらないので、エッジを全部基準の向きにするよう反転→本命操作→再び反転の流れを考えることにより、エッジは全て基準の向きだと仮定して構わないことになります。エッジが全て基準の向きになっているような状態から各面の90度回転をすると、

R,L,U,D面の回転では全エッジが基準の向きを保ち、 $flip(x) = 0$ が保たれます。
F,B面の回転では巻き込まれた4つのエッジが全て基準と逆向きになり、 $flip(x) = 0$ は変化しません。

以上から $flip(x)$ は任意の回転操作に対して不変量です。不変量論法から、

$flip(x)=1$ であるような状態 $x$ は"あり得ない"状態である。

といえます $\left( \because flip(x _ 0) = 0 \right)$ 。

"あり得る"状態の必要条件

3つの不変量について分かったことをまとめると、以下のようになります。

パーツの位置に関して $sgn(x) \in \{ 1, -1 \}$ という不変量があり、 $sgn(x) \ne 1 \Rightarrow x$ は"あり得ない"状態
コーナーの向きに関して $pivot(x) \in \{ 0,1,2 \}$ という不変量があり、 $pivot(x) \ne 0 \Rightarrow x$ は"あり得ない"状態
エッジの向きについて $flip(x) \in \{ 0,1 \}$ という不変量があり、 $flip(x) \ne 0 \Rightarrow x$ は"あり得ない"状態

これらは状態 $x$ が"あり得る"状態であるための必要条件 $sgn(x) = 1 , pivot(x) = flip(x) = 0$ を与えています。ここで分解したキューブの全パーツを配置していく過程を思い出すと、パーツの位置を決める際に $sgn(x)$ が決まり、コーナーの向きを決める際に $pivot(x)$ が決まり、エッジの向きを決める際に $flip(x)$ が決まるので、各不変量 $sgn,pivot,flip$ は全て独立に決定できるということが分かります。言い換えると、かなり上の方で求めた大量の状態 $x$ に対して、 $(sgn(x),pivot(x),flip(x))$ の値の組み合わせは $2 \times 3 \times 2 = 12$ 通り全て存在し、しかも同数ずつです。したがって、

全状態のうち $sgn(x) = 1 , pivot(x) = flip(x) = 0$ を満たすものの総数は $519,024,039,293,878,272,000÷12=43,252,003,274,489,856,000$ 通りである

ことが分かります。やっとタイトル通りの数字になりましたね！

十分性の証明

しかし、これで $Q.E.D.$ というわけにはいきません。今示されたのは、"あり得る"状態であるための必要条件 $sgn(x)=1,pivot(x)=flip(x)=0$ を満たしている状態が43,252,003,274,489,856,000通り存在する、つまり"あり得る"状態の数が43,252,003,274,489,856,000以下であることだけです。この証明を完成させるためには、 $sgn(x)=1,pivot(x)=flip(x)=0$ という条件が、状態 $x$ があり得る状態であるための十分条件でもあること、すなわち

$sgn(x)=1,pivot(x)=flip(x)=0$ ならば、 $x$ はあり得る状態である(揃えられる)

ことを示さなければなりません。そして揃えられることの証明法はただ一つ*15、実際に揃える方法を示すのみです。

後編に続く！！！！()

goldenfalcon496.hatenablog.com

*1:遅くなりました。すいませんでした。

*2:そういう暗黙の仮定は危ないと学校で教わらなかったのか？？

*3:出典うぃきぺでぃあだからまちがってないはず。たぶん。

*4:実際、その界隈の人々は単にキューブと呼びます。

*5:嘘でした。iPhoneの電卓横画面モードではしっかり14桁表示されています

*6:今度こそその辺の電卓では表示できません

*7:当然、これは6つの面の回転の組み合わせのことを指します

*8:これらの呼称はキューブ界隈で標準的に用いられています

*9:これ思ったよりかなりめんどくさかったです(´・ω・｀)ｼｮﾎﾞｰﾝ

*10:図を描くのが面倒になっています

*11:1234→2341という感じの置換だな、というくらいの認識でよいです

*12:符号の定義に自信がなくなってきたので一応置換の符号 - Wikipediaを参照しました

*13:参考.この定義はキューブのZZ methodという解法で提案されたもので、"RLUD面の回転だけで揃えられる向き"として特徴付けられます

*14:エッジの反転は一応フリップと呼ばれるのですが、ピボットに対して使われる機会が少ないです

*15:他にもありそうな気がしてきました。天才の皆さん考えてください(投げやり)。

496の落書き帳

496がなんか思ったことを書いたり書かなかったりする場所です。

ルービックキューブの状態の総数が43,252,003,274,489,856,000通りであることの証明(ルービックキューブが1時間で揃えられるようになる方法付き)(前編)

もくじ