II

II

Изобретенная в Америке, игра эта получила там и первую свою математическую теорию — в трудах американских математиков Вулсей Джонсона и Вильяма Сторн. Впрочем, независимо от них и вскоре вслед за ними развил основания этой теории также ряд других математиков в различных странах Европы.

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

Вообразите теперь любое начальное расположение шашек, т. е. такое, при котором 15 шашек размещены в пестром беспорядке. Нетрудно убедиться, что рядом передвижений всегда можно привести шашку № 1 на место, занимаемое ею на чертеже. Точно так же возможно, не трогая шашки 1, привести шашку 2 на место рядом с ней, которое она занимает на схеме I.

Схема I

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

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

Схема 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 и, следовательно, ни при каких обстоятельствах не переводятся в «нормальное» конечное расположение: это — положения неразрешимые, те именно, за разрешение которых тщетно назначались огромные премии.

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

Рассмотрим представленное здесь расположение.

Первый ряд шашек в порядке, как и второй, за исключением последней шашки (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 горизонтальных и v вертикальных ходов, причем — если в обоих положениях свободное поле находится в правом нижнем углу — оба числа, h и v, четные. Горизонтальные ходы не могут изменить инверсий, вертикальные же изменяют их каждый раз на нечетное число, т. е. в общем итоге — так как v число четное — на четное число. Вот почему для переводимости двух расположений (в которых пустое поле находится в правом нижнем углу) одного в другое необходимо, чтобы они различались между собою четным числом инверсий. Это условие взаимного перевода является притом не только необходимым, но, очевидно, также и достаточным. — «Нормальное» расположение имеет 0 инверсий, и, следовательно, ему соответствует серия положений с четным числом инверсий (при условии, что свободное поле на одном и том же месте). Расположение II имеет одну инверсию, — его серия есть серия нечетных инверсий.

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

Данный текст является ознакомительным фрагментом.