Докажите, что в игре "15"невозможно из исходной расстановки получить расстановку, в которой квадратики 14 и 15 поменялись местами, а остальные остались на прежних местах.

Будем считать, что на пустом месте стоит квадратик с номером 16. В начальный момент у нас ноль инверсий, то есть перестановка четная. Сдвигая квадратик на пустое место, мы как бы меняем местами этот квадратик с квадратиком 16, при этом четность перестановки меняется. Поскольку 16-й квадратик в результате всех перемещений должен вернуться на старое место, то число перемещений по вертикали четно, как и число перемещений по горизонтали. В результате первоначальная четная перестановка обязана остаться четной. Однако перестановка, в которой 14 и 15 поменялись местами, а остальные остались на месте, нечетна. Следовательно, такой перестановки достичь невозможно.