TPP Mark 2013


September 19, 2013

今年はサム・ロイドの 14-15 パズルの不可能問題について出題します。
1.概要
サム・ロイドの 14-15 パズルというのは、15 パズル(別名:15 ゲーム)において、14 番目と 15 番目の駒を入れ替えた状態からでは、どのような駒の移動を行っても、本来の 15 パズルの完成形にすることができないというものです。
参考: Wikipedia による解説
2.問題
お好みの定理証明系で、14-15 パズルは完成不可能であることを証明してください。
※注意
・与えられるパズルの盤面は 14 番目と 15 番目の駒のみが入れ替えられたものです。
・パズルの移動は{1, 2, ..., 16}(16 は空マス)の内の 2 つの駒の互換の合成で表されるので、以上を形式化定義してください。
※追記
・15 パズルではなく 8 パズルを考慮していただいても結構です。(力技での証明、大歓迎です)
3.参考
’15 パズルの数理’



Source code: sketch_130905a

Built with Processing