ルービックキューブをスクランブルするのはどれくらい難しいですか?

ルービックキューブは、40年間、世界で人気のパズルの一つとなっています。 無数の本で説明されているように、それを解決するためのいくつかの異なる方法が考案されています。 専門家”speedcubers”は数秒でそれを解決することができます。

驚異的な器用さのような偉業に加えて、ルービックキューブに関連する多くの魅力的な数学的な質問があります。 立方体の移動は、6つの面のうちの1つを90度、180度、または270度回転させることで構成されます。 驚異的な43,252,003,274,489,856,000可能な状態は、解かれた状態に移動のシーケンスを適用することによって得ることができます。

この複雑さにもかかわらず、2010年には、初期状態に関係なく、ルービックキューブは常に20移動以下で解くことができることが示されました。 人間が使用するすべての既知の解法は、通常、この最適値よりもはるかに多くの動きを使用するため、この数は「神の数」と呼ばれます。p>

解決された状態のルービックキューブ。 Mike Gonzalez(TheCoffee)

しかし、反対の質問はどうですか:解決されたキューブをスクランブルするために必要な動きはいくつですか? 一見すると、これは神の数を計算するよりもはるかに簡単な質問のように聞こえます。 結局のところ、キューブを解くのとは異なり、スクランブルは全くスキルを取りません。

同様の質問は、カードシャッフルのために正常に回答されています。 有名な例は、1990年の数学者Dave BayerとPerci Diaconisによる「riffle shuffle」の研究です。 カードのデッキは、その順序がランダムであり、それぞれの可能な順序が出現する確率が同じである場合、”混合”と定義されます。 バイエルとディアコニスは、七つのリフルシャッフルが標準的なトランプのデッキを約混ぜるのに必要かつ十分であることを示した。

昨年、数学者は15のスライドタイルと1つの空きスペースで満たされた4×4の正方形で構成される15のパズルの同様の研究を発表しました。キューブがスクランブルされるのはどういう意味ですか?

ルービックキューブをスクランブルしようとする典型的な人は、その上でランダムな動きを繰り返し実行します。

ルービックキューブをスクランブルしようとする典型的な人 結果として得られるランダムな状態列は、数学者がマルコフ連鎖と呼ぶ特別な場合です。 キープロパティは、現在の状態が与えられた場合、次の状態が何になるかの確率は、以前の状態のいずれにも依存しないということです。

マルコフ連鎖の理論をキューブスクランブルに適用すると、ランダムな移動の数が増えるにつれて、可能な状態のいずれかの特定の状態にある確率1/43,252,003,274,489,856,000. それぞれの可能な状態が同じ確率で起こるので、数学者はこれを「一様確率分布」と呼んでいます。

任意の数のランダムな移動の後、立方体の状態はランダムになりますが、その確率分布は正確に一様ではなく、いくつかの状態は他の状態よりも起

d(t)は、tランダム移動後の確率分布が一様確率分布とどのくらい異なるかを記述します。 ランダムな移動の数(t)が増加すると、d(t)の値は減少します。 スクランブルされている立方体は、d(t)が小さいことに対応します。

マルコフ連鎖モンテカルロ

マルコフ連鎖の理論では、このd(t)の減少は”混合”と呼ばれています。 カードシャッフルやパズルスクランブルのほかに、マルコフ連鎖混合の理論も非常に深刻な実用化を持っています。 現代の科学と工学における最も重要な計算ツールの一つは、モンテカルロ法です。 この方法は、それが命名された有名なカジノのように、基本的にチャンスに依存しています。 本質的には、複数のランダムな推測を使用して、ハード数学的な問題を近似的に解決しようとします。 実際には、マルコフ連鎖は、多くの場合、これらのランダムな状態を生成するために使用されます。

これらのマルコフ連鎖モンテカルロ法の精度を理解するために、重要なタスクは、tが増加するにつれてd(t)がどれだけ速く減少するかを推定するこp>

ポケットキューブ

スクランブル状態のポケットキューブ。 Mike Gonzalez(TheCoffee)

標準の3x3x3Rubik’s Cubeのスクランブル問題を研究することは、現在、魅力的な未解決の課題です。 しかし、ポケットキューブと呼ばれる小さな2x2x2バージョンに注意を向けると、それはかなり管理しやすくなります。

この立方体では、エッジと中央の部分は存在せず、コーナーの部分だけが残ります。

この立方体では、エッジと中央の部分は存在しません。 ポケットキューブには3,674,160の可能な状態しかなく、その神の数はわずか11です。 下のグラフでは、ポケットキューブのd(t)をプロットします。 11回移動した後、d(t)はまだ0.695で非常に大きいです。 0.25未満のd(t)値を生成するtの最初の値(マルコフ連鎖理論ではしばしば”混合時間”と呼ばれる)は19である。 25回移動した後、d(t)は0.092であり、50回移動した後は0.0012である; そして、100の動きの後、それは0.00000017です。 p>

tが移動した後のユニフォームからのポケットキューブ分布の距離。 Eric Zhou

ポケットキューブを完全にスクランブルするためにどのように多くの動きを使用する必要がありますか? 答えは、d(t)をどれだけ小さくしたいかによって異なります。 しかし、神の動きの数が不足していることは確かです。 最低限、1つは19未満の動きを使用してはなりません。 D(t)を計算するコードを含む詳細は、ここで入手できます。

もちろん、キューブをスクランブルしたら、それをもう一度解くだけです。

もちろん、キューブをスクランブルしたら、もう一度解くだけです。

もちろん、キューブをスクランブルしたら、もう一度解くだけです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です