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

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

«Давнишние обитатели царства смекалки, - пишет Лойд, - помнят, как в начале 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.

КРОКЕТ[2]

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

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

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

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

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

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