15パズルの状態空間を2つの別々の部分に分割できるのはなぜですか？

Question

私は理解しようとしています ここで証明してください 15パズルの状態空間が2つの別々の部分に分割される理由の理由は、説明が複雑です。

誰かが簡単に説明してもらえますか？私はこれに何日も苦労してきました:(

Answer 1

おそらく、証拠を理解する最も簡単な方法は、 保存量 ：構成から派生できる量を見つけ、すべての動きがその量を保持することを示します。アイデアの静的バージョンは、次の古いパズルにあります。

標準の8x8チェッカーボードから北東と南西の角の正方形を取り外します。 31のドミノを使用して、残りの62四角をタイル張りにすることはできますか？

ここでは、パリティの原則は単純です。各ドミノは、チェッカーボード上で正確に1つの黒と白い正方形を占有するため、ドミノがタイルできる形状は、黒と同じくらい多くの白い正方形を持たなければなりません。 62平方形の形状には、1つの色の32平方、もう1つの色の30四角があるため、タイリングする方法はありません。

15パズルの保全の原則はもう少し複雑ですが、これにかなり近いものです。また、パリティの原則でもあります。当面の間、空白の正方形「16」を数え、それが埋められていると想像しましょう。それから私たちはパズルの状態について話すことができます 順列 数字の（1 ... 16）。これで、数字（1 ... $ n $）の任意の順列を考えると、すべての数値を「元の場所」に返すために交換する必要がある数のペア数を数えることができます。多くの異なる可能なスワップのセットがあります - たとえば、順列（3、2、1）がある場合、1番目と3番目の位置（3）を交換することで（1、2、3）に戻ることができます（3） 1）または1番目と2番目のポジション（2で3）を交換することにより、2番目と3番目のポジション（1で3）、次に第1位と2番目のポジション（1で1）を交換します。 （作成する必要があるスワップの最小数は、 反転 順列の、そしてそれはそれ自体が興味深い量ですが、それはここでは重要ではありません）。ただし、数字を交換しますが、スワップの総数は常に奇妙になります（（3、2、1）のように）か、常に均等です。この番号と呼びます パリティ 順列の。

さて、15のパズルに戻ります。すべての動きは、空白の正方形の正方形の1つのユニットと一緒に、空白の正方形（「16」とラベル付けしたもの）を交換することです。つまり、スワップには常に1つの正方形の動きが付属していることを意味します。したがって、「私が行ったスワップの総数」 +」の数量を考慮すると、16がホームスクエアから離れています」と考えると、この量は常に均等になります。特に、16が自宅の広場に戻った場合（0回離れて）、実行されるスワップの総数は均等でなければなりません。これは、 パリティ 結果の位置に対応する数値（1..16）の順列の均一です。しかし今、14と15が場所を交換した元のパズルの位置を想像してください。 16は自宅にいますが、「スワップ」が1つしか作られていません。これは偶数ではなく奇数のスワップであるため、ベース構成から到達できる可能性があります。

もう1つのマイナーなキャッチがあります：これはにあることを示しています 少しでも 15パズルの位置が陥る可能性がある2つのカテゴリですが、それはあることを示していません それだけ 2。そのためには、やや複雑な結果が必要です。つまり、均一な均一な均一なものは、として知られているものの積として分解できることです。 3サイクル （つまり、$ a rightArrow b rightArrow c rightArrow a $を交換します）。ここでこれを証明しようとはしませんが、最も単純な証明はアルゴリズム的に機能します - バブルソートと同様に、すべての順列が隣接する要素のみを交換することで生成できることを示しています。ただし、この結果を手にしてください。ただし、均一な順列を簡単に取得できます。3つの要素をパズルの位置11、12、および15に移動することで、任意の3サイクルを取得できます（空白の正方形は位置16、コース）、そして空白の正方形を上に移動し、左、下、右に移動します - このモーションが3つの要素を循環することを自分自身に納得させることができます。これを完了したら、私たちはちょうど 元に戻します 3つの要素をそれらの位置に導いた同じ動きで、他のすべての要素の最終的な位置を開始位置から変えません。任意の3サイクルを取得するこの方法と、3サイクルで均一な順列を表現できるようにする定理を取得し、すべての到達可能な（すなわち、均一な順列に対応する）位置を得る方法を与えます。