Я только что пытался вспомнить в уме, не подглядывая, почему пятнашки нельзя собрать, если поменять местами 14 и 15. Я помнил, что доказательство там как-то связано с четностью перестановок, но не помнил, как. Рассуждал так: какой самый простой способ связать положение доски с перестановкой, чтобы конечное положение было тождественной перестановкой? Назовем пустую клетку 16-й, пронумеруем поля доски от 1 до 16 очевидным способом, и тогда любое положение определяет перестановку: номер поля переходит в номер костяшки, к-я на самом деле стоит на этом поле.
Но: если теперь посмотреть, что происходит, когда двигается любая костяшка, то это соответствует транспозиции, т.е. четность перестановки наоборот меняется после каждого шага, а не сохраняется. Вот это "наоборот" должно было мне сразу подсказать правильное решение (но не подсказало, потому что я тормоз). Если "наоборот" меняется после каждого шага, от этого легко придти к чему-то, что сохраняется после каждого шага; например, надо добавить что-то еще, что тоже меняется после каждого шага. А это, например, четность положения пустой клетки. Вот и все. [1]
[1] Поправка благодаря анониму в комментах: не "четность положения пустой клетки", к-я двигается напр. с 4 на 8, а скажем "четность сумм координат пустой клетки", которая действительно меняется после каждого шага.