15パズルの謎を解く

そろった状態は 1, 2, …, 15, 16 の順です。14 と 15 を入れ替えた配置は …, 13, 15, 14, 16 で、そろった状態に互換 (14 15) を1回した置換です。転倒数は 1 で、奇置換です。

空白、つまり 16 番のタイルと、となりのタイルとの入れ替えなので、互換1回です。

1手ごとに空白はとなりのマスに動くので、空白のいるマスの色は必ず変わります。右下から出発して右下に戻ってくるには、色がもとに戻らないといけないので、動かした回数は偶数です。

空白が右下にある配置は、どれも、そろった状態に偶数個の互換を掛けたもの、つまり偶置換です。でも 14 と 15 を入れ替えた配置は、空白が右下にあるのに奇置換です。前のステージで、偶置換と奇置換の両方になる置換はないと分かっています。だから、どう動かしても 14 と 15 を入れ替えた配置にはたどり着けません！

1手ごとに互換が1つ加わるので、転倒数の偶奇が変わります。空白は1マス動くので、d は 1 増えるか 1 減って、やはり偶奇が変わります。2つが同時に変わるので、転倒数＋d の偶奇は、どう動かしても変わりません。そろった状態では 0＋0＝0 で偶数なので、和が奇数の配置にはたどり着けません。

空白の 16 番が先頭にあって、残りの 15 枚全部より左にあるので、転倒数は 15 です。空白は右下から横に 3、縦に 3 離れているので d＝6。和は 21 で奇数なので、この配置もそろえられません。

右下の 2×2 には 11, 12, 15 と空白があります。空白が上へ行くと 12 が下へ、左へ行くと 11 が右へ、下へ行くと 15 が上へ、右へ行くと 12 が左へ動きます。1周すると、11 があった場所に 15、12 があった場所に 11、15 があった場所に 12 が来ます。3枚が回りました。4手で空白も戻っているので、偶置換です。

偶置換は互換が偶数個なので、2個ずつ組にできます。(a b)(a c) のように番号を共有する組は、前のステージの (1 2)(1 3)＝(1 2 3) と同じ形で3巡回です。(a b)(c d) のように共有しない組は、間に (b c)(b c) を入れても変わらないので、(a b)(b c) と (b c)(c d) の2つの組に分けられて、どちらも番号を共有するので3巡回です。

すると、15パズルの 16! 通りの配置は、たどり着ける配置とたどり着けない配置の、同じ個数ずつの2つに、ちょうど分かれるんですね。たどり着ける配置は 16! の半分です。

操作を積として計算できるので、k 手の動きを k 個の互換の積と書けました。互換の個数の偶奇が書き方によらないことは、転倒数で証明しました。市松模様の色で、空白が戻るには偶数手かかることが分かりました。偶置換が全体のちょうど半分で、3巡回で全部作れることから、たどり着ける配置がちょうど半分だと分かりました。

方程式の解の入れ替えも置換なら、15パズルのように「どう入れ替えても変わらない性質」を使って、できないことを言い切るんですか？