Игру пятнашки (или "пятнадцать"), как говорят, придумал в конце XIX века американец Сэмюэль Ллойд — автор множества интеллектуальных задач и головоломок. Игровое поле для игры в пятнашки представляет собой квадрат 4x4, состоящий из 16 равных квадратиков меньшего размера. Пятнадцать квадратиков заняты фишками с номерами от 1 до 15, а последний, 16-й маленький квадрат всегда должен оставаться пустым, но может менять своё местоположение на доске. Цель игры: исходя из какой-либо начальной расстановки, последовательно передвигая фишки и изменяя местоположение пустого квадрата, расположить фишки на доске в порядке строгого возрастания их номеров, то есть привести расположение к стандартной расстановке фишек от номера 1 до номера 15. За один ход разрешается передвинуть только одну фишку. Двигать фишку на каждом ходу можно только по горизонтали или по вертикали и только на одно поле. Нельзя произвольно менять фишки местами, в частности, нельзя поднимать их с плоскости доски и затем перемещать в другое место.
Классический пример игры — это когда фишки с номерами от 1 до 13 находятся на правильных местах, а вот 14 и 15 поменяны местами: после 13 идёт 15, затем 14. Можно ли привести фишки к правильному порядку?
Говорят, люди чуть ли не с ума сходили, чтобы решить эту задачу. Они бросали свою работу и часами, а то и сутками проводили время над решением головоломки.
Оказывается, данная задача неразрешима. Нельзя переставить местами фишки с цифрами 15 и 14, не нарушая правил игры.
В общем случае, решение данной головоломки зависит от начальной расстановки фишек. В частности, играет роль количество так называемых беспорядков. Беспорядком называется явление, когда фишка с бОльшим номером предшествует фишке с меньшим номером. Так вот, если количество беспорядков в расстановке чётно, то задача разрешима и фишки можно привести к стандартному правильному порядку. Если же количество беспорядков нечётно, то, увы, к правильному порядку расстановку привести не удастся никак. Ноль беспорядков принимается за чётное число (ведь число 0 формально делится на два).
В предлагаемом Ллойдом варианте — тот, что представлен в условии вопроса, фишка с числом 15 предшествует фишке с числом 14. Больше "неправильностей" здесь нет. Соответственно, имеем всего один беспорядок. Поскольку единица — нечётное число, то головоломка неразрешима. А если бы, например, была бы расстановка типа 1 2 3 4 5 6 7 8 9 10 11 13 12 15 14, в которой два беспорядка (13–12, 15–14), то тогда вполне можно было бы привести фишки к порядку строгого возрастания номеров.
