Схема II.
Любое начальное положение может быть приведено либо к нормальному схемы I, либо к конечному схемы II.
Это значительно упрощает задачу: все необозримое разнообразие положений шашек сведено к двум типичным схемам I или II, так что приходится иметь дело лишь с этими двумя. Если некоторое расположение, которое для краткости обозначим буквою S, может быть преобразовано в положение схемы I, то, очевидно, возможно и обратное - перевести положение схемы I в положение S. Ведь все передвижения шашек (все "ходы", как будем говорить кратко) несомненно обратимы: если, например, в схеме I мы можем шашку 4 поместить на свободное поле, то можно ход этот тотчас взять обратно противоположным движением. И если расположение переводится в расположение не схемы I, а схемы II, то соответственно этому расположение схемы II может быть переведено в расположение S.
Итак, мы имеем две серии расположений таких, что положения одной серии могут быть все переведены в "нормальное" I, а другой серии - в положение II. И наоборот, мы уже видели, что из "нормального" расположения можно получить любое положение первой серии, а из расположения схемы II - любое положение второй серии. Наконец, два любых расположения, принадлежащие к одной и той же серии, могут быть взаимно переводимы друг в друга: если оба относятся, например, к первой серии, то это значит, что одно из них может быть переведено в положение схемы I, а положение схемы I переводится в другое из данных двух положений; короче - одно данное положение переводимо в другое и наоборот.
Возникает вопрос: нельзя ли идти дальше и объединить эти два типичных расположения - схем I и II? Это было бы возможно, если бы одно из них переводилось каким-нибудь образом в другое. Тогда обе серии расположений естественно слились бы в одну. Сопоставляя друг с другом расположения схем I и II, можно строго доказать (не станем входить здесь в подробности), что положения эти не могут быть превращены одно в другое никаким числом передвижений. Это - огонь и вода. Поэтому все огромное число размещений шашек распадается на две разобщенные серии: 1) на те, которые могут быть переведены в "нормальное" схемы I: это - положения разрешимые; 2) на те, которые могут быть переведены в положение схемы II и, следовательно, ни при каких обстоятельствах не переводятся в "нормальное" конечное расположение: это - положения неразрешенные, те именно, за разрешение которых тщетно назначались огромные премии.
Но как узнать, принадлежит ли заданное расположение к первой или второй серии? Пример разъяснит это.
Рассмотрим представленное здесь расположение.
Схема III.
Первый ряд шашек в порядке, как и второй, за исключением последней шашки (9). Эта шашка занимает место, которое в "нормальном" расположении принадлежит 8. Шашка 9 стоит, значит, "ранее" 8; такое упреждение нормального порядка будем называть "инверсией". О шашке 9 мы скажем: здесь имеет место "одна инверсия". Рассматривая дальнейшие шашки, обнаруживаем упреждение для шашки 14; она поставлена на три места (шашек 12, 13, 11) ранее своего нормального положения; здесь у нас 3 инверсии (14 ранее 12; 14 ранее 13; 14 ранее 11). Всего мы насчитали уже 1 + 3 = 4 инверсии. Далее шашка 12 помещена ранее шашки 11, и точно так же шашка 13 - ранее шашки 11. Это дает еще 2 инверсии. Итого имеем таким образом 6 инверсий. Подобным образом для каждого заданного расположения устанавливают "общее число инверсий", освободив предварительно последнее место в правом нижнем углу. Если общее число инверсий, как в рассмотренном случае, четное, то заданное расположение может быть приведено к "нормальному" конечному; другими словами, оно принадлежит к разрешимым. Если же число инверсий нечетное, то данное расположение принадлежит ко второй серии, т. е. к неразрешимым.
Из-за недостатка места мы должны отказаться от строгого доказательства всего изложенного. Но можно наметить кратко главные этапы в ходе этого доказательства. Среди ходов будем различать "горизонтальные" и "вертикальные" (смысл этих слов, конечно, ясен). Легко видеть, что всякий "вертикальный" ход изменяет число инверсий либо на 1, либо на 3, т. е. на нечетное число. Чтобы одно положение шашек перевести в какое-либо другое, необходимо сделать h горизонтальных и вертикальных ходов, причем - если в обоих положениях свободное поле находится в правом нижнем углу, - оба числа, h и четные. Горизонтальные ходы не могут изменить инверсий, вертикальные же изменяют его каждый раз на нечетное число, т. е. в общем итоге - так как число четное - на четное число. Вот почему для переводимости двух расположений (в которых пустое поле находится в правом нижнем углу) одного в другое необходимо, чтобы они различались между собою четным числом инверсий. Это условие взаимного перевода является притом не только необходимым, но, очевидно, также и достаточным. "Нормальное" расположение имеет 0 инверсий, и, следовательно, ему соответствует серия положений с четным числом инверсий (при условии, что свободное поле на одном и том же месте). Расположение II имеет одну инверсию, - ее серия есть серия нечетных инверсий.
Поучительной в этой игре является и ее история. При своем появлении игра вызвала всюду, как мы уже рассказали, сильнейшее, прямо лихорадочное возбуждение и породила настоящую манию игры. С этой лихорадкой удалось справиться только математике. И удалось ей это так полно, что в наши дни подобная страстность в этой игре уже совершенно немыслима. Победа достигнута была благодаря тому, что математика создала исчерпывающую теорию игры, теорию, не оставляющую в ней ни одного сомнительного пункта и превратившую ее в образчик настоящей математической игры. Исход игры зависит здесь не от каких-либо случайностей и даже не от исключительной находчивости, как в других играх, а от чисто математических факторов, предопределяющих исход с безусловной достоверностью.
Примечания редактора
Иллюстрация, приведенная в начале этой статьи, помещена в любопытной книге Сама Лойда "Энциклопедия головоломок" (Нью-Йорк, 1914). Это большой том, заключающий 5000 разнообразных задач и развлечений, из которых тысяча иллюстрирована. Рисунок интересующей нас игры сопровождается следующим текстом: "Давнишние обитатели царства смекалки помнят, как в начале 70-х годов я заставил весь мир ломать голову над коробкой с подвижными шашками, получившей известность под именем "игры в 14-15". Пятнадцать шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14-я и 15-я были переставлены, как показано на прилагаемой иллюстрации. Задача состояла в том, чтобы последовательно передвигая шашки, привести их в исходное положение, причем, однако, порядок шашек 14-й и 15-й должен быть исправлен".
Премия в 1000 долларов, предложенная за первое правильное решение этой задачи, никем не была заслужена, хотя тысячи людей уверяли, что выполнили требуемое. Все принялись без устали решать эту задачу. Рассказывали забавные истории о торговцах, забывавших из-за этого открывать свои магазины, о почтенных чиновниках, целые ночи напролет простаивавших под уличным фонарем, отыскивая путь к решению. Непостижимой особенностью игры было то, что никто не желал отказываться от поисков решения, так как все чувствовали уверенность в ожидающем их успехе. Штурмана, говорят, из-за игры садили на мель свои суда, машинисты проводили поезда мимо станций, торговля была деморализована. Фермеры забрасывали свои плуги, и один из таких моментов изображен на прилагаемой иллюстрации.
Вот несколько новых задач, кроме той, которая приведена выше:
Задача 2-я. Исходя из расположения, показанного на схеме II, привести шашки в правильный порядок, но со свободным полем в левом верхнем углу (см. чертеж).
К задаче 2-й.
Задача 3-я. Исходя из расположения схемы II, поверните коробку на четверть оборота и передвигайте шашки до тех пор, пока они не примут расположения чертежа.
К задаче 3-й.
Задача 4-я. Передвижением шашек превратите коробку в "магический квадрат", а именно, разместите шашки так, чтобы сумма чисел была во всех направлениях равна 30.