Головоломка "15 чисел" хорошо известна. Ее можно купить, есть масса вариантов помимо чисел: сложить картинку, например. Суть в том, что квадрат делится на 16 квадратиков, один отсутствует, и квадратики можно двигать на пустое место. И нужно, меняя их местами, расставить в нужном порядке.
В классической головоломке на квадратиках были числа от 1 до 15, они стояли по порядку, но два последних были поменяны местами. И нужно эти два поменять местами.
Эту головоломку описал Перельман в одной из своих "занимательных" книг, и ещё Бушков в "Летающих островах", второй книге таларской серии. Да и вообще она хорошо известна.
Головоломка стала страшно популярной, до безумия. Мне хочется верить, что сейчас такое уже невозможно: люди немного поумнели. Хотя черт знает...
Доказательство неразрешимости очень просто. Перельман его почему-то не приводит, Бушков, разумеется, тоже.
Если вы это доказательство знаете, то можете дальше не читать.
Нам потребуется понятие "инверсии". Если в ряду чисел число побольше стоит раньше числа поменьше, то это одна инверсия. Например, в ряду 1;2;3;5 инверсий нет, в ряду 5;1;2;3 инверсий три, а в 5;3;1;2 инверсий пять (пятерка раньше трех других, а тройка раньше 1 и 2).
Обмен местами двух соседних чисел меняет число инверсий на одну: если первое число больше второго, то одну инверсию мы устраним, а если меньше, то создадим.
В итоге четность числа инверсий изменится: четное станет нечетным, а нечетное - четным.
Если между числами стоят n других, то обмен их местами тоже непременно изменит четность общего числа инверсий. В самом деле, сначала надо подогнать одно число к другому, совершив n обменов и изменив четность n раз; потом поменяем эти два, изменив четность еще раз; и потом надо отогнать число на прежнюю позицию (еще n перемен). В итоге число изменений четности будет 2n+1, что всегда нечетно. В итоге четность изменится.
Число 16, которое стоит неявно на пустом месте, стоит изначально в правом нижнем углу и должно в итоге там и оказаться. Остальные числа, кроме 14 и 15, тоже должны вернуться в прежнюю позицию. А 14 и 15 должны обменяться местами.
При этом обмены чисел местами возможны только с числом 16. Оно сделает столько ходов вправо, сколько и влево, и столько же ходов вниз, сколько и вверх. Под ходом понимается обмен местами. В итоге четность при возвращении числа 16 на место не меняется.
Вот это ключевой момент: как бы вы не гоняли квадратики, если пустое место вернется туда, где было, то чётность числа инверсий не изменится.
А обмен 14 и 15 меняет четность. В исходной позиции одна инверсия (нечет), а в финальной их нет (чёт).
Поэтому это невозможно сделать по правилам.
Указанный способ доказательства невозможности называется методом инварианта. Над найти величину, которая при данных преобразованиях не меняется, и если в начальном и конечном положении она разная, то это доказывает невозможность.
Точно так же можно доказать, что кубик Рубика невозможно собрать, если один уголок повернуть "силой". Потому что любой поворот делает четное число обменов.
Пример из другой области: можно ли разрезать круг на части и сложить из них квадрат? А наоборот? Кажется, что нельзя, и правильно кажется, но как это доказать? Достаточно найти инвариант, а именно: кусок границы берем со знаком плюс, если он выпуклый; со знаком минус, если вогнутый; и не берем вовсе, если это отрезок прямой. Разрез по любой кривой создаст две новые границы, причем выпуклому участку одной соответствует вогнутый участок другой. При сложении кусочков две границы исчезнут, но опять-таки выпуклый кусок соединится с вогнутым. Так что характеристика границы не меняется, это инвариант.
А у круга (вся граница выпуклая) и квадрата (вся границя из отрезков) эти характеристики разные, у круга положительная, а у квадрата нулевая.
Очень красиво! Найти инвариант - большой успех.
Пара заключительных замечаний по пятнишке. Во-первых, важно оказалось считать пустую клетку числом 16. Во-вторых, вообще числовая головоломка решается, а если надо собрать картинку из Плейбоя, то уже не так всё очевидно. То есть надо сообразить, что можно приписать клеткам числа, на числах учесть порядок и найти инвариант...
В этом и состоит мастерство, на самом деле.
