496の落書き帳スマートフォン用の表示で見る496の落書き帳496がなんか思ったことを書いたり書かなかったりする場所です。Adventarの9日目の記事として書かれました。タイトル通り、ルービックキューブに関する"証明"をします。副作用として、この記事を読むとルービックキューブが揃えられるようになります。長すぎて前後編になりました。十分性の証明まえがき(ISer向け,分からん人はすっ飛ばせください)こんにちは。20erの496です(と言っても「誰だお前」でしょうが)。Carendarとかを眺めるとりじょーらしいガチ勢の記事が多数派でうわーーーーーってなった結果ある程度学問ある程度趣味みたいな感じでこれに落ち着きました。途中の説明は分かりやすさをそれなりに大事にしたので、頭の回転が速いISの人々にはもっさり感があるかもしれませんがご容赦ください。なにはともあれ、ゆっくりしていってね。ごめんなさい、長すぎて半分くらいしか終わってないです!後編をお楽しみにIntroductionルービックキューブとは何か、を知らない人はいないと想定している*1のでさくさく本題に入ります。何の予備知識もなくルービックキューブを揃えるのは難しいです。何も見ずに解けたら本当に天才だと思います(努力家的なものか謎の閃きかは差し置いて)。昔の(?)ルービックキューブにはよくこんな感じの宣伝文句が付いていました。あり得る状態は4000京通り以上!君の頭脳はこれを解けるか!?理系の心がある人ならすぐに気になるでしょう。実際にはあり得る状態は何通りなのか??先に答えを書いておくと(既にタイトルに書かれているが)、4325京2003兆2744億8985万6000通り*2、ということになっています。この記事では、この数字が如何にして導出されるのかをできる限り厳密に考えていきたいと思います。簡単のため、以降ルービックキューブのことを単にキューブと呼ぶことがあります*3。組合せ論的に考えれば、各パーツの配置のしかたの総数をカウントすれば良さそうな気がしますね。そのためにはまずルービックキューブにはどんなパーツがいくつあるのか??ということを考える必要があります。立方体の頂点に位置するパーツ8個(以降コーナーと呼びます)立方体の辺(の中心)に位置するパーツ12個(以降エッジと呼びます)立方体の6つの面の中心を張り合わせたパーツ1個(以降コアと呼びます)となっています。コアの向きを固定して考えると、結局キューブのパーツ配置の総数とは固定したコアに対して20個のパーツ(コーナーとエッジ)を配置する方法の総数であるといえます。最初からこの結論を述べても議論は進められるのですが、キューブの構造に対して実感を持つと分かりやすくなるかなーと思います。分解したキューブを手元に置い(たと想像し)て、20個のパーツを配置することを考えましょう。通りの配置があることになりそうです。この時点でその辺の電卓では表示できない桁数になっています*4が、これで終わりではありません。キューブのパーツ配置には位置だけでなく向きの情報が含まれます。通りあることになります。組合せ爆発の何たるかを痛感する結果ですね*5。見るとこの数字、冒頭に挙げた"正解"よりもかなり大きい数字になってしまっています。勘のいい方はお気づきかと思いますが、実はいま求めたキューブのパーツ配置たちの中には、正当な方法*6で揃えることができない、言わば"あり得ない"状態が大量に存在するのです。いうわけで、ルービックキューブにおいて"あり得る"状態の数を知るためには、"あり得ない"状態がどれくらいあるのかを考える必要が出てきます。注.以降、"あり得る"状態、"あり得ない"状態という言葉を上の文章で定義されたものとして頻繁に使います。用語導入ここからの話を円滑に進めるために、キューブの面、パーツ、操作などの呼称を書いておきます*7。書いた後で分かったのですが位置と回転に関する用語を使う場面は少ないので、適当に見ておいて定義が分からなくなったら戻ってくるくらいでも良さそうです。上にある面をU面(Up)下にある面をD面(Down)右にある面をR面(Right)左にある面をL面(Left)手前にある面をF面(Front)奥にある面をB面(Back)と呼びます。X面の中心にある色をX面色と呼びます。キューブ全体の向きを変えない限り、各面を回転しても各面の色は変わりません。パーツ位置コーナーおよびエッジパーツの位置を、面の名前を並べて表現します。微妙に分かりづらいので例として図を作りました*8。図1図1において、赤いパーツ(コーナー)の位置をUFR、青いパーツ(エッジ)の位置をUFと呼ぶことになります。U,R,F面の回転は直感的に分かりやすいですが、反対側の面はやや分かりにくいです。いい感じの図解はこれなどがあります*9。言いましたが、この記事では回転記号をそこまで多用しないのでのんびり見てください。以下のようになります。"あり得ない"状態の条件〜パーツ配置の制約さて、本題に戻ってキューブの"あり得ない"状態について考えましょう。この手の証明にありがちな手法ですが、キューブの操作に対する状態の"不変量"を見つけることで、一部のパーツ配置が"あり得ない"ことを証明できます。具体的にはこんな感じですね。到達できない!この節ではキューブの状態に3つの不変量が存在することを示し、それを用いて「あり得ない状態が少なくともこれくらい存在する」ということを証明します。いっても、いきなり無から不変量を見つけるのは天才的閃きを要するので、少しばかり経験知に頼ることにして、このような状態は"あり得ない"状態であることが経験的に知られているその背景にはある種の不変量があることを証明するといった感じで進めていきます。経験知1:完成状態に対してある二つのパーツの位置のみが入れ替わっている状態は"あり得ない"状態であることが知られている。書くと少しあからさまな感じがしてしまいますが、今からするのは置換の符号の話です。パーツの向きのことは忘れて、位置だけについて考えることにしましょう。キューブの各面を回転させると、パーツたちの位置が変化しますね。これは一種の置換になっています。具体的にはある面を90度回転させる操作において、その面に属する4つのコーナーが巡回置換*10され、その面に属する4つのエッジも巡回置換される他のパーツの位置は変わらないといったところです。置換の符号を観察すると、4つの要素の巡回置換は奇置換(3回の入れ替えで実現できる)なので、コーナーもエッジも奇置換されていますが、ここで重要なのはコーナーとエッジの置換を合わせて20個の要素の置換として見ると、偶置換になっているということです。各面の90度回転操作に対して不変量です。いかなる操作に対しても不変量です。"あり得ない"状態である。注.コーナーやエッジの置換だけを見ると奇置換なので、ここから不変量を作り出すことはできません。実際、コーナーの位置だけみると奇置換でエッジの位置だけみても奇置換であるような"あり得る"状態は存在します。筆者にとってはこれは若干の違和感を伴う事実なのですが、そう思わない人もいるかもしれません。経験知2:完成状態から1つのコーナーの向きのみを変えた状態は"あり得ない"状態であることが知られている。これはキューブ界隈では理論にあまり興味がない人も含めて大半が知っている有名な話で、なぜかというと実際に起きてしまう確率が高いからです。最近のキューブは柔軟なので乱暴に扱うとコーナーの向きがポロっと変わってしまうこと(これをピボットといいます。この言葉は便利なので以下でちょいちょい使われます)があり、そうすると永久に揃わないという事態が発生し得るので注意が必要です。実はキューブの早解き競技の正式なルールには、競技中にコーナーの向きが変わってしまった場合の規定がちゃんと書かれていたりします。上記の経験知2から、コーナーの向きについて何か不変量がありそうな気がしてきます。これを正確に定義して、不変量であることを示すのは少々厄介です。何が問題なのかというと、各コーナーの向きのことだけを考えたいのに位置がどんどん変わってしまうということです。向きを表す量というのは"本来の向き"に対してどれくらい差異があるかによって定義したいものですが、あるパーツが元々あった位置に存在しない場合、そのパーツには"本来の向き"などというものがなく、定義に困ってしまうのです。そこで全コーナーの全位置について、勝手に"本来の向き"(というか"基準の向き")を決めてしまいます。これは簡潔であればあるほど後々の議論が楽になります。今回はU面色とD面色に注目して定義を作ってみます。U面色の面またはD面色の面(これは1×1マスのこと)を1つだけ持つ。U面の4つのコーナー位置か、D面の4つのコーナー位置のいずれかに属する。U面またはD面を向くような向きが1つだけ存在する。コーナーの基準面の向き文章にするともにょもにょしますが、定義自体は簡潔だと思います(多分)。(1×1マス)が現在も黄色い部分にあればその位置を問わず基準の向きであるとみなすイメージです。これを使って、目論見通り各コーナーの向きを示す量を基準の向きからのズレで表現し、さらにそれらの合計として状態全体としてのコーナーの向きに関する量の定義をします。以下のように定義する。左に回転しているならば。しますが素直な定義を文章に起こそうとするとこうなってしまうんですよね・・・。あとはこれがうまく不変量になってくれればいいのですが、その証明も逐一やろうとすると大変です。いうか本当に正しいのかわからなくなってきます。変化しない、ということを真っ向から示すのはもはや全探索的な何かになってしまっています。そこで、簡潔な証明にするため以下の事実を念頭におきます。位置と向きに注目する。行った場合の結果と変わらない。これは割と当たり前なことです。要はピボットというズルをして、後でそれを元に戻しているだけです。して、さっきズルをした分を全部元に戻すということが考えられます。変化しなければOKです。強い仮定が使えるのですぐに示せます。前節同様90度回転についてだけ示せれば十分です。