Яков Перельман - Живая математика. Математические рассказы и головоломки

Приведем собственный рассказ изобретателя игры о некоторых фактах из ее истории:

«Давнишние обитатели царства смекалки, - пишет Лойд, - помнят, как в начале 70-х годов я заставил весь мир ломать голову над коробкой с подвижными шашками, получившей известность под именем игры в «15». Пятнадцать шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14 и 15 были переставлены, как показано на прилагаемой иллюстрации (рис. 16). Задача состояла в том, чтобы, последовательно передвигая шашки, привести их в нормальное положение, причем, однако, порядок шашек 14 и 15 должен быть исправлен.

Премия в 1000 долларов, предложенная за первое правильное решение этой задачи, никем не была заслужена, хотя все без устали решали эту задачу. Рассказывали забавные истории о торговцах, забывавших из-за этого открывать свои магазины, о почтенных чиновниках, целые ночи напролет простаивавших под уличным фонарем, отыскивая путь к решению. Никто не желал отказаться от поисков решения, так как все чувствовали уверенность в ожидающем их успехе. Штурмана, говорят, из-за игры сажали на мель свои суда, машинисты проводили поезда мимо станций; фермеры забрасывали свои плуги».

____________________

Познакомим читателя с начатками теории этой игры. В полном виде она очень сложна и тесно примыкает к одному из отделов высшей алгебры («теории определителей»). Мы ограничимся лишь некоторыми соображениями, изложенными В. Аренсом.

«Задача игры состоит обыкновенно в том, чтобы посредством последовательных передвижений, допускаемых наличием свободного поля, перевести любое начальное расположение 15 шашек в нормальное, т. е. в такое, при котором шашки идут в порядке своих чисел: в верхнем левом углу 1, направо - 2, затем 3, потом в верхнем правом углу 4; в следующем ряду слева направо: 5, 6, 7, 8 и т. д. Такое нормальное конечное расположение мы даем на рис. 15.

Вообразите теперь расположение, при котором 15 шашек размещены в пестром беспорядке. Рядом передвижений всегда можно привести шашку 1 на место, занимаемое ею на рисунке.

Точно так же возможно, не трогая шашки 1, привести шашку 2 на соседнее место вправо. Затем, не трогая шашек 1 и 2, можно поместить шашки 3 и 4 на их нормальные места: если они случайно не находятся в двух последних вертикальных рядах, то легко привести их в эту область и затем рядом передвижений достичь желаемого результата. Теперь верхняя строка 1, 2, 3, 4 приведена в порядок, и при дальнейших манипуляциях с шашками мы трогать этого ряда не будем. Таким же путем стараемся мы привести в порядок и вторую строку: 5, 6, 7, 8; легко убедиться, что это всегда достижимо. Далее, на пространстве двух рядов необходимо привести в нормальное положение шашки 9 и 13: это тоже всегда возможно. Из всех приведенных в порядок шашек 1, 2, 3, 4, 5, 6, 7, 8, 9 и 13 в дальнейшем ни одной не перемещают; остается небольшой участок в шесть полей, в котором одно свободно, а пять остальных заняты шашками 10, 11, 12, 14, 15 в произвольном порядке.

Рис. 15

Нормальное расположение шашек (положение I)

Рис. 16.

Неразрешимый случай (положение II)

В пределах этого шестиместного участка всегда можно привести на нормальные места шашки 10, 11, 12. Когда это достигнуто, то в последнем ряду шашки 14 и 15 окажутся размещенными либо в нормальном порядке, либо в обратном (рис. 16). Таким путем, который читатели легко могут проверить на деле, мы приходим к следующему результату.

Любое начальное положение может быть приведено к расположению либо рис. 15 (положение I), либо рис. 16 (положение II).

Если некоторое расположение, которое для краткости обозначим буквою S, может быть преобразовано в положение I, то, очевидно, возможно и обратное - перевести положение I в положение S. Ведь все ходы шашек обратимы: если, например, в схеме I мы можем шашку 12 поместить на свободное поле, то можно ход этот тотчас взять обратно противоположными движениями.

Итак, мы имеем две серии расположений таких, что положения одной серии могут быть переведены в нормальное I, а другой серии - в положение II. И, наоборот, из нормального расположения можно получить любое положение первой серии, а из расположения II - любое положение второй серии. Наконец, два любых расположения, принадлежащие к одной и той же серии, могут быть переводимы друг в друга.

Нельзя ли идти дальше и объединить эти два расположения - I и II? Можно строго доказать (не станем входить в подробности), что положения эти не превращаются одно в другое никаким числом ходов. Поэтому все огромное число размещений шашек распадается на две разобщенные серии: 1) на те, которые могут быть переведены в нормальное I: это - положения разрешимые; 2) на те, которые могут быть переведены в положение II и, следовательно, ни при каких обстоятельствах не переводятся в нормальное расположение: это - положения, за разрешение которых назначались огромные премии.

Рис. 17. Шашки не приведены в порядок

Как узнать, принадлежит ли заданное расположение к первой или ко второй серии? Пример разъяснит это.

Рассмотрим расположение, представленное на рис. 17. Первый ряд шашек в порядке, как и второй, за исключением последней шашки (9). Эта шашка занимает место, которое в нормальном расположении принадлежит 8. Шашка 9 стоит, значит, ранее шашки 8: такое упреждение нормального порядка называют «беспорядком». О шашке 9 мы скажем: «Здесь имеет место 1 беспорядок». Рассматривая дальнейшие шашки, обнаруживаем упреждение для шашки 14; она поставлена на три места (шашек 12, 13, 11) ранее своего нормального положения; здесь у нас 3 беспорядка (14 ранее 12; 14 ранее 13; 14 ранее 11). Всего мы насчитали уже 1 + 3=4 беспорядка. Далее, шашка 12 помещена ранее шашки 11, и точно так же шашка 13 - ранее шашки 11. Это дает еще 2 беспорядка. Итого, имеем 6 беспорядков. Подобным образом для каждого расположения устанавливают общее число беспорядков, освободив предварительно последнее место в правом нижнем углу. Если общее число беспорядков, как в рассмотренном случае, четное, то заданное расположение может быть приведено к нормальному конечному; другими словами, оно принадлежит к разрешимым. Если же число беспорядков нечетное, то расположение принадлежит ко второй серии, т. е. к неразрешимым (ноль беспорядков принимается за четное число их).

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

Обратимся теперь к головоломкам в этой области. Вот несколько разрешимых задач, придуманных изобретателем игры.

Исходя из расположения, показанного на рис. 15, привести шашки в правильный порядок, но со свободным полем в левом верхнем углу (рис. 18).

Рис. 18. К первой задаче Самуэля Лойда

Рис. 19. Ко второй задаче Самуэля Лойда

Исходя из расположения рис. 15, поверните коробку на четверть оборота и передвигайте шашки до тех пор, пока они не примут расположения рис. 19.

Передвигая шашки согласно правилам игры, превратите коробку в магический квадрат, а именно: разместите шашки так, чтобы сумма чисел была во всех направлениях равна 30.

Крокетным игрокам предлагаю следующие пять задач.

Крокетные ворота имеют прямоугольную форму. Ширина их вдвое больше диаметра шара. При таких условиях что легче: свободно, не задевая проволоки, пройти с наилучшей позиции ворота или с такого же расстояния крокировать шар?

Рис. 20. Схема игры в крокет

Толщина крокетного столбика внизу - 6 см. Диаметр шара 10 см. Во сколько раз попасть в шар легче, чем с такого же расстояния заколоться?

Шар вдвое уже прямоугольных ворот и вдвое шире столбика. Что легче: свободно пройти ворота с наилучшей позиции или с такого же расстояния заколоться?

Ширина прямоугольных ворот втрое больше диаметра шара. Что легче: свободно пройти в наилучшей позиции мышеловку или с такого же расстояния крокировать шар?