496の落書き帳

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

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

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

もくじ

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

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

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

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

Introduction

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

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

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

単純な総数の考察

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

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

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

ということを考える必要があります。キューブを手にとったり分解したりしたことがない人にとっては意外かもしれませんが、ルービックキューブのパーツは 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通り

の配置があることになりそうです。もうこの時点でその辺の電卓では表示できない桁数になっています*4が、これで終わりではありません。キューブのパーツ配置には位置だけでなく向きの情報が含まれます。同じ位置でもコーナーには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通り

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

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

用語導入

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

面、色

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

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

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

パーツ位置

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

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

回転記号

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

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

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

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

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

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

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

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

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

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

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

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

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

といったところです。置換の符号を観察すると、4つの要素の巡回置換は奇置換(3回の入れ替えで実現できる)なので、コーナーもエッジも奇置換されていますが、ここで重要なのはコーナーとエッジの置換を合わせて20個の要素の置換として見ると、偶置換になっているということです。
すると、状態xに対して、(完成状態 x _ 0から見たときの)パーツ位置の置換の符号を sgn(x)とおけば*11sgn(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つのコーナー位置のいずれかに属する。
・以上から、XLにおける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)の増減は相殺するので、Mpivot(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 )
しかし、基準の向きの定義がコーナーのとき以上に厄介です。前節が長すぎたのでサクサク行きましょう。
(前節と同じ記号が出ますがご容赦ください)

エッジに対する基準の向きの定義*12:エッジ(パーツ) 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)というものを定義してしまいます。

エッジのフリップ値*13の定義:状態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はあり得る状態である(揃えられる)

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

後編に続く!!!!()

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

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

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

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

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

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

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

*8:これ思ったよりかなりめんどくさかったです(´・ω・`)ショボーン

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

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

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

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

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

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