Ｐ２３ 神の数字
さて。教科書では【円順列】について学んでいるところですが……
今宵は【円順列】にからんで、【神の数字】についてのお話をします。
皆さんは【ルービック・キューブ】をご存じでしょうか？
おもちゃと言いましょうか、パズルと言いましょうか……
【おもちゃパズル】とでも言っておきましょう。ちなみにウィキペディアで調べたら【立方体パズル】と書かれていました。
ハンガリーのルービック博士が発明したキューブ（立方体）という事で、１９８０年代に日本でも大ブームを巻き起こしました。
３×３×３＝２７
２７個の小さな立方体を【キュービー】と言います。正確には中心の１個は操作不可能なので、【操作出来るキュービー】は２６個となります。
各【キュービー】は表に見える部分に色が塗り分けられ、特定の操作をほどこし、６つの面全てを３×３の同一色に埋めることが出来れば完全クリアとなるパズルです。
私も子供の頃、かなりハマった【ルービックキューブ】ですが、１面を同色完成させるのに精一杯でした。笑
ルービックキューブから派生したおもちゃパズルに、スネークキューブやマジックキューブなどがあり、私はそのほとんどに手を出していましたね。笑
ルービックキューブの操作は各【キュービー】を動かし再配置する、いわゆる数学の世界の言葉で【置換】という操作になります。ルービックキューブの操作は、数学の世界における【置換群】の構造を用いて解析することが出来ます。
【置換群】とは代数学の基礎で学ぶ【群論】における【群】の一種。この原稿の下書きでは、【群論】の具体例を書いていたんですが、難しい事は書かないと誓ったので、削除しておきました。笑
……。
ルービックキューブの話の前に、次のような操作を考えてみましょう。
今、ここに３つの数字の列（１，２，３）があったとします。この中の２つの数字の配置を交換するという操作を考えます。リアルな試験で出てきそうな問題ですね～。
考えられる操作は
１，２番目の数字を交換 （１，２，３） → （２，１，３）
１，３番目の数字を交換 （１，２，３） → （３，２，１）
２，３番目の数字を交換 （１，２，３） → （１，３，２）
の３つです。この操作に名前をつけて、上から順に 操作ａ，ｂ，ｃ と置く事にします。
操作ａ （１，２，３） → （２，１，３）
操作ｂ （１，２，３） → （３，２，１）
操作ｃ （１，２，３） → （１，３，２）
※
全く動かさない （１，２，３） → （１，２，３） という操作（群論で言う単位元）も考えたいところですが、今回は省略します。
また、３つの数字 １，２，３ の配置としては
（１，２，３） （１，３，２）
（２，１，３） （２，３，１）
（３，１，２） （３，２，１）
この６通りが考えられます。この６つの配置と上にあげた操作を考える事にします（これで１つの【置換群】を考える事が出来ます）。
そうするとこの６つの配置、どれからスタートしても必ず２回以内の操作で任意の配置にする事が出来るのです。
では具体的に（３，２，１）をゴールとしましょう。
（１，２，３）から始めたら、１番目と３番目を交替する操作ｂ
（１，２，３） →（操作ｂ）→ （３，２，１）
この１手でゴールです。
（１，３，２）から始めたら、まず１番目と２番目を交替する操作ａ、次に２番目と３番目を交替する操作ｃを施せばＯＫです。
（１，３，２） →（操作ａ）→ （３，１，２） →（操作ｃ）→ （３，２，１）
以下
（２，１，３） →（操作ｂ）→ （３，１，２） →（操作ｃ）→ （３，２，１）
２手でゴール。
（２，３，１） →（操作ａ）→ （３，２，１）
１手でゴール。
（３，１，２） →（操作ｃ）→ （３，２，１）
１手でゴール。
（３，２，１） 動かさず
０手でゴール。
このようにどの要素から初めても２手以下で、ゴール（３，２，１）へ到達できるわけです。
これは３つの数字の例だから簡単ですが、４つの数字となると結構難しくなります。それを拡張してルービックキューブの話につなげます。
ルービックキューブの【キュービー】の配置の仕方は、数珠順列（Ｐ２４ではネックレス順列で紹介されています）の計算などを使い……
実に
４３２５京２００３兆２７４４億８９８５万６０００通り ①
となります。
超余談ですが、私は「一、十、百、万、億、兆、京、……、無量大数」まで３秒以内で言える特技を持っています。はい、どうでもいいですね。
（人前でこの特技を披露すると、１００％どん引きされます）
この４３００京もの配置に対し、ルービックキューブで可能な操作を考える事になります。
その前に１つ。いわゆるルービックキューブの操作では３×３の面を回転させるわけです。（１／４）回転は１手となりますが、同じ方向に回すのであれば半回転も１手とする流儀と、例え同じ方向に半回転させたとしても、それは（１／４）回転を２度施したという事で２手とする流儀があります。
今回は半回転も１手と数える流儀で話を進めます。
ルービックキューブ、最初の操作の仕方は１８通りあります。次以降の操作に関しては同じ面を回すという無駄な操作を省いて（これが３つありますので）、１５通りとなります。従ってｎ手で考えられる操作の数は
だけあります。
さて、ここからですよ。ルービックキューブがどんな配置であれ、ある特定の数以内で６面を同色で完成させる事ができるはずです。ルービックキューブ発売当初から「その数は何だ！？」と噂になっておりました。
計算機や数学者の手にかかれば簡単にその数が求められる……
と思いきや、これがなかなかどうして。先にバラしますが、その数字を求めるのに実に３０年以上の時間を費やすことになるのです。いつしか人はその数字を
【神の数字】
と呼ぶようになりました。
では。その【神の数字】が暴かれるまでの歴史を見てみましょう。
ルービックキューブにおいて、ｎ手で考えられる操作法は
でした。そしてルービックキューブの【キュービー】の配置の仕方
４３２５京２００３兆２７４４億８９８５万６０００通り ①
について
この不等式から最低でもｎ－１は１６以上、すなわち【神の数字】は１７以上と導かれます。いわゆる【神の数字】の下限ですね。この【１７】は数学の専門家でなくとも割と簡単に出せる数字です。
【神の数字】の歴史を覗いてみましょう。
ルービック博士の地元・ハンガリーでルービックキューブが販売されたのが１９７７年（日本では１９８０年販売）。
まずは１９８１年、アメリカの学者ダグラス（父ロバート・ホフスタッターはノーベル物理学賞受賞者）が、【神の数】は５２手以下と示します。この時点で
１７ ≦ 神の数字 ≦ ５２
となりますね。
時代は過ぎて１９９５年、レイドという人物により【神の数字】は２０手以上であると同時に、２９手以下である事が証明されます。
２０ ≦ 神の数字 ≦ ２９
２１世紀に入っても【神の数字】の探求は続きます。２００５年には２８手以下、２００６年には２７手以下である事が判明し、２００７年には実に７テラバイトのＲＡＭを搭載したスパコンにより２６手以下である事が示されました。
２０ ≦ 神の数字 ≦ ２６
ちなみにこの２６。もう少しくわしく言いますと……
①の４３００京通りの配置全てに対し、キューブ１回の操作で考えられる新しい配置を１秒で１億回チェックするという恐ろしい速度で計算して導き出したそうです。結果、どんな配置からでも２６回キューブを操作すれば６面完成させる事を示したのです。
ちなみにこれで【神の数字】が２６と示されたような気もしますが、必ずしもそうではないのです。２６手の手順であっても、他の手順の組合せでもっと早く６面を完成できる可能性があるからです。
というわけで、１秒に１億パターンをチェックするスパコンをもってしてもまだ【神の数字】は得られていないのです。
２００８年３月、スタンフォード大学のトマスが【神の数字】は２５手以下である事を示し、同年４月には２３手以下、同年８月に２２手以下である事をトマス自身が突きとめています。
２０ ≦ 神の数字 ≦ ２２
あと１歩で【神の数字】を割り出せるところまで来ましたが、ここからさらに高い壁を攻略せねばなりません。
【神の数字】解明に向けてラストスパートをかけるため……
先のトマスを含め、ＧｏｏＧｌｅ社のエンジニアやプログラマー４名による研究チームが結成されました。
チームはスパコンに計算させる負担を軽減させるためのアルゴリズムを打ち出しますが、従来のデスクトップコンピューターでは１０億秒以上（約３５年）かかると試算。そこで研究チームはGoogleから借りた高性能のコンピュータ（そのコンピュータがどんなスペックなのかは明らかにされていないとのこと）を用い、実質全パターンを網羅しました。
ちなみに実際Ｇｏｏｇｌｅ社に出向いて、空き時間を利用してコンピュータを使わせてもらったそうです。
かくしてルービックキューブがどんな状態からでも、２０手以下で６面完成できることを示したのです。
２０ ≦ 神の数字 ≦ ２０
ルービックキューブ発売から実に３０年以上の２０１０年８月１５日。
【神の数字】は２０
だと証明されたわけです。
チームの一員であるモーリー・デビッドソン助教授（ケント州立大学）。７歳の時誕生日に買ってもらったルービックキューブ手にした時から、その謎を解明してやると心に誓っていたそうです。フェルマーの最終定理に似たエピソードですね。
ちなみにＧｏｏＧｌｅ社の高性能コンピュータを持ってしても、ルービックキューブ全ての操作の仕方を網羅するには数週間の時間を要したそうです（もっとも空き時間に使わせてもらっていたそうですが）。
いっけんするとコンピュータでちょちょいと計算出来そうですが、思ったより簡単にできるものではないんですね。今後はそういう話もしていく予定です。
もし……
コンピュータの性能が１０年前のレベルなら、まだ【神の数字】の探求は続いていたでしょう。
というわけで今宵は【神の数字】の話でした。
