Математика для любознательных
Шрифт:
Возникает вопрос: нельзя ли идти дальше и объединить эти два типичных расположения - схем 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 имеет одну инверсию, - ее серия есть серия нечетных инверсий.
Поучительной в этой игре является и ее история. При своем появлении игра вызвала всюду, как мы уже рассказали, сильнейшее, прямо лихорадочное возбуждение и породила настоящую манию игры. С этой лихорадкой удалось справиться только математике. И удалось ей это так полно, что в наши дни подобная страстность в этой игре уже совершенно немыслима. Победа достигнута была благодаря тому, что математика создала исчерпывающую теорию игры, теорию, не оставляющую в ней ни одного сомнительного пункта и превратившую ее в образчик настоящей математической игры. Исход игры зависит здесь не от каких-либо случайностей и даже не от исключительной находчивости, как в других играх, а от чисто математических факторов, предопределяющих исход с безусловной достоверностью [36] .
36
«Такен (игра в 15), - говорит французский математик Люка - не только весьма интересная игрушка, но также и прибор, с помощью которого чрезвычайно легко дать наглядное понятие об одном из важнейших отделов алгебры, а именно о теории определителей, принадлежащей Лейбницу. Поэтому теорию и практические приемы игры в такен можно считать своего рода подготовкой к изучению этой части алгебры».
– Ред.
Иллюстрация, приведенная в начале этой статьи, помещена в любопытной книге Сама Лойда «Энциклопедия головоломок» (Нью-Йорк, 1914). Это большой том, заключающий 5000 разнообразных задач и развлечений, из которых тысяча иллюстрирована. Рисунок интересующей нас игры сопровождается следующим текстом: «Давнишние обитатели царства смекалки помнят, как в начале 70-х годов я заставил весь мир ломать голову над коробкой с подвижными шашками, получившей известность под именем «игры в 14-15». Пятнадцать шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14-я и 15-я были переставлены, как показано на прилагаемой иллюстрации. Задача состояла в том, чтобы последовательно передвигая шашки, привести их в исходное положение, причем, однако, порядок шашек 14-й и 15-й должен быть исправлен».
Премия в 1000 долларов, предложенная за первое правильное решение этой задачи, никем не была заслужена, хотя тысячи людей уверяли, что выполнили требуемое. Все принялись без устали решать эту задачу. Рассказывали забавные истории о торговцах, забывавших из-за этого открывать свои магазины, о почтенных чиновниках, целые ночи напролет простаивавших под уличным фонарем, отыскивая путь к решению. Непостижимой особенностью игры было то, что никто не желал отказываться от поисков решения, так как все чувствовали уверенность в ожидающем их успехе. Штурмана, говорят, из-за игры садили на мель свои суда, машинисты проводили поезда мимо станций, торговля была деморализована. Фермеры забрасывали свои плуги, и один из таких моментов изображен на прилагаемой иллюстрации.
Вот несколько новых задач, кроме той, которая приведена выше:
Задача 2-я. Исходя из расположения, показанного на схеме II, привести шашки в правильный порядок, но со свободным полем в левом верхнем углу (см. чертеж).
К задаче 2-й.
Задача 3-я. Исходя из расположения схемы II, поверните коробку на четверть оборота и передвигайте шашки до тех пор, пока они не примут расположения чертежа.
К задаче 3-й.
Задача 4-я. Передвижением шашек превратите коробку в «магический квадрат», а именно, разместите шашки так, чтобы сумма чисел была во всех направлениях равна 30.
Расположение зад. 2-й может быть получено из начального положения следующими 44 ходами.
14, 11, 12, 8, 7, 6, 10, 12, 8, 7,
4, 3, 6, 4, 7, 14, 11, 15, 13, 9,
12, 8, 4, 10, 8, 4, 14, 11, 15, 13,
9, 12, 4, 8, 5, 4, 8, 9, 13, 14,
10, 6, 2, 1.
Расположение зад. 3 достигается следующими 39 ходами:
14, 15, 10, 6, 7, 11, 15, 10, 13, 9,
5, 1, 2, 3, 4, 8, 12, 15, 10, 13,
9, 5, 1, 2, 3, 4, 8, 12, 15, 14,
13, 9, 5, 1, 2, 3, 4, 8, 12.
Магический квадрат с суммою 30 получается ряда ходов:
12, 8, 4, 3, 2, 6, 10, 9, 13, 15,
14, 12, 8, 4, 7, 10, 9, 14, 12, 8,
4, 7, 10, 9, 6, 2, 3, 10, 9, 6,
5, 1, 2, 3, 6, 5, 3, 2, 1, 13,
14, 3, 2, 1, 13, 14, 3, 12, 15, 3.
Приведем замечание немецкого математика Шуберта о числе возможных задач при «игре в 15».
«Сколько всего возможно задач; т. е. сколько различных расположений можно дать 15 шашкам, причем каждый раз пустое поле расположено справа внизу? Чтобы определить, сколько перестановок можно получить с помощью 15 предметов, начнем с 2-х предметов: а и b. Они могут дать лишь две перестановки, именно - ab и Ьа. При трех предметах имеется уже втрое больше перестановок, т. е. 6, так как предмет а может быть поставлен перед Ьс и перед cb, и кроме того, имеются еще две перестановки, начинающиеся с b, и две начинающиеся с с. Отсюда можно заключить, что четыре предмета а, b, с, d могут дать вчетверо большее число различных перестановок, т. е. 4x3x2 = 24 перестановки. Продолжая так, можно найти, что 15 шашек допускают всего
2x3x4x5x6x7x8x9x10x11x12x13x14x15
перестановок. Вычислив это произведение, мы найдем для числа задач игры внушительное число:
1 биллион 307674 миллиона 368000».
Из этого огромного числа задач ровно половина принадлежит к разрешимым и столько же - к неразрешимым. Заметим еще, что если бы возможно было ежесекундно давать шашкам новое положение, то чтобы перепробовать всевозможные расположения, потребовалось бы, при непрерывной работе круглые сутки, - свыше 40.000 лет.
<