15 パズルの証明

15 パズルは必ず任意の並びにすることができる、という命題を証明できるのか考えていたが、この命題は偽だった。Wikipedia から抜粋。

15 パズルで一つの駒のスライドという動作は数学的には空いたマス目との互換と考えられる。この操作に関して、任意の 2 つの駒のみを入れ替える (他のものは変えない) ためには、空いたマス目が偶数回の操作を経て元の場所に戻らなければならない。二つの駒を入れ替えることは一つの互換、つまり奇置換で表され、空いたマス目に対する操作は偶置換で表されるため、15 パズルで単に二つの駒を入れ替えるという操作は不可能である。したがってランダムな配置から指定された配置への変換はできないことがある。

この例として、サム・ロイドの提示した「14 と 15 を入れ替えた状態を元に戻す」という問題がある。ロイドは (絶対に解けることのない) この問題に 1000 ドルの賞金をかけて出題した。

パズルとして実体化される際には、このような問題が起きないように、15 個の駒をケースから外せないように工夫されているものが多い。例えば 15個の駒の上辺と左辺の側面を凹、下辺と右辺の側面を凸にして、スライドできかつケースから取り外されないように (ケースの内側の 4 辺にも凸凹が施される) 工夫がなされている。