Головоломки, гений и 1000 долларов

Как развлекаются математики? Вы когда-нибудь задумывались об этом? Например, известный лектор Оксфордского университета Чарльз Доджсон в свободное время писал потрясающие сказки в жанре абсурда – и как минимум с одной из них вы точно знакомы. Его перу принадлежит книга «Алиса в стране Чудес», а Льюис Кэрролл – его литературный псевдоним. Впрочем, это было не единственное его хобби – несколько лет Доджсон потратил на то, чтобы собрать большую коллекцию математических головоломок. Однако в этой области не было равных другому знаменитому математику – Сэму Лойду и его не менее известной головоломке «15-14».

Сама задача выглядит достаточно просто. В квадратной коробочке 4*4 расположены 15 квадратных шашек с номерами от 1 до 15, которые можно двигать, но не доставать. Изначально шашки 14 и 15 расположены неправильно, и чтобы решить головоломку, нужно расположить все шашки в правильном порядке. При этом тому, кто первым найдет решение, математик обещал премию в размере 1000 долларов!

Головоломка вызвала небывалый ажиотаж. В своей автобиографии Сэм Лойд рассказывал о владельцах лавок, которые забывали открывать свои заведения, о знаменитом священнике, который простоял всю зимнюю ночь под уличным фонарем, пытаясь припомнить, как ему удалось решить задачу. Но… Премия так и не была востребована! Никто из тех, кто утверждал, что решил головоломку, так и не смог показать верную последовательность ходов. Предвидел ли это математик?

На самом деле Сэм Лойд был уверен, что платить ему не придется. Оказалось, что головоломка не имеет решения! Лойд доказал это в своей автобиографии, а мы покажем наглядно сейчас.

Во-первых, стоит определить очень интересную величину – параметр беспорядка Dp. Для каждого расположения шашек он равен числу таких их пар, что числа на них стоят в обратном порядке. Например, если головоломка собрана, число таких пар равно Dp = 0.

А если передвинуть по кругу три шашки в правом углу, то пары (12,11), (15,13), (15,14), (15,11), (13,11) и (14,11) окажутся неупорядоченными, и Dp будет равен 6.

Аналогично, если двигать 5 шашек, получим Dp = 10.

И вот здесь можно заметить очень важный факт! Как бы мы не двигали шашки из их начального, верного положения, всегда параметр беспорядка будет четным. Строго это доказывается в разделе комбинаторного анализа, или, проще говоря, комбинаторике.

А теперь давайте посмотрим на расположение шашек, которое предлагал исправить Сэм Лойд. Здесь неправильно расположены относительно друг друга только шашки 15 и 14, следовательно, параметр беспорядка равен 1. Так как единица – число нечетное, получить такое расположение из правильного невозможно, а значит, и наоборот – решить головоломку – не получится. Хитрый математик мог быть абсолютно спокоен за свои 1000 долларов.