В Париже опасная игра нашла себе приют под открытым небом, на бульварах, и быстро распространилась из столицы по всей провинции.[36] Вскоре, говорят французские источники, не было в провинции ни одного уединенного сельского домика, где не угнездился бы этот паук, подстерегая жертву, готовую запутаться в его сетях. Настоящий бич человечества, вот какой рисуется эта игра одному французскому автору. «Бедствие, более страшное, чем табак и алкоголь!» — восклицает он в комическом отчаянии.
В 1880 г. игорная лихорадка достигла, по-видимому, своей высшей точки. Вся пестрая, разноязычная литература, порожденная этой игрой, относится к немногим годам между 1879 и 1883.
Вскоре после этого демон, тиранивший стольких людей, был повержен и побежден. Математика — вот его победительница, и победа не была для нее особенно трудной, между тем как «демон алкоголя и табака» никогда, конечно, не будет следовать за ее триумфальной колесницей, сколько бы славы ни сулила победа над ним.
Когда демон был оружием математики повержен во прах, источник мучений столь многих и многих стал ясен для всех. Математическая теория игры обнаружила, что из многочисленных задач, которые могут быть предложены, только половина разрешима, между тем как другая не разрешима никакими ухищрениями.
Стало ясно, почему иные задачи не поддавались самым упорным усилиям; стало ясно, почему устроители турниров отваживались назначать огромные премии за разрешения некоторых задач, и ни один из многочисленных соревнователей не смог овладеть ими.
В этом отношении всех превзошел сам изобретатель игры, предложивший издателю нью-йоркской газеты для воскресного прибавления неразрешимую задачу с премией в 1000 долларов за ее разрешение; и так как издатель колебался, то изобретатель выразил полную готовность внести названную сумму из собственного кармана.
Мы до сих пор не назвали имени изобретателя:
Самуэль (Сэм) Лойд. Он родился в городе Филадельфии. В шахматных кругах он приобрел широкую известность как составитель остроумных задач; кроме того, им придумано множество иных головоломок. Мы воспроизводим здесь портрет
этого изобретательного человека. Любопытно, что ему не удалось получить в Америке патента на придуманную им игру. Хотя Лойд не мог предусмотреть чудовищного успеха своего изобретения и совершенно не ожидал его, он подал заявление о патенте. Согласно инструкции, он должен был представить «рабочую модель» для исполнения пробной партии; он предложил чиновнику патентного бюро неразрешимую задачу, и когда последний осведомился, разрешима ли она, изобретатель должен был ответить: «Нет, это математически невозможно». — «В таком случае, — последовало возражение, — раз задача не разрешима, то не может быть и рабочей модели, а без модели нет и патента». Странным образом Лойд удовлетворился этой мнимой логикой и этой удивительной резолюцией, — но, вероятно, был бы более настойчив, если бы хоть отчасти предвидел неслыханный успех своего изобретения.
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]
Примечание редактора
Иллюстрация, приведенная в начале этой статьи, помещена в любопытной книге Сэма Лойда «Энциклопедия головоломок» (Нью-Йорк, 1914). Это большой том, заключающий 5000 разнообразных задач и развлечений, из которых тысяча иллюстрирована. Рисунок интересующей нас игры сопровождается следующим текстом.
«Давнишние обитатели царства смекалки помнят, как в начале 70-х годов я заставил весь мир ломать голову над коробкой с подвижными шашками, получившей известность под именем „игры в 14–15“. Пятнадцать шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14-я и 15-я были переставлены, как показано на прилагаемой иллюстрации. Задача состояла в том, чтобы, последовательно передвигая шашки, привести их в исходное положение, причем, однако, порядок шашек 14-й и 15-й должен быть исправлен.
Премия в 1000 долларов, предложенная за первое правильное решение этой задачи, никем не была заслужена, хотя тысячи людей уверяли, что выполнили требуемое. Все принялись без устали решать эту задачу. Рассказывали забавные истории о торговцах, забывавших из-за этого открывать свои магазины, о почтенных чиновниках, целые ночи напролет простаивавших под уличным фонарем, отыскивая путь к решению. Непостижимой особенностью игры было то, что никто не желал отказываться от поисков решения, так как все чувствовали уверенность в ожидающем их успехе. Штурманы, говорят, из-за игры сажали на мель свои суда, машинисты проводили поезда мимо станций, торговля была деморализована. Фермеры забрасывали свои плуги, — один из таких моментов изображен на прилагаемой иллюстрации.
К задаче 2-й
Вот несколько новых задач, кроме той, которая приведена выше.
Задача 2-я. Исходя из расположения, показанного на схеме I, привести шашки в правильный порядок, но со свободным полем в левом верхнем углу (см. чертеж). Задача 3-я. Исходя из расположения схемы I, поверните коробку на четверть оборота и передвигайте шашки до тех пор, пока они не примут расположения чертежа.
К задаче 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, И, 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-х предметов: а и Ь. Они могут дать лишь две перестановки, именно — ab и Ьа. При трех предметах имеется уже втрое больше перестановок, т. е. 6, так как предмет „а“ может быть поставлен перед Ьс и перед cb, и, кроме того, имеются еще две перестановки, начинающиеся с Ь, и две, начинающиеся с с. Отсюда можно заключить, что четыре предмета а, Ь, с, d могут дать вчетверо большее число различных перестановок, т. е. 4 × 3 × 2 = 24 перестановки. Продолжая так, можно найти, что 15 шашек допускают всего
2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 × 11 × 12 × 13 × 14 × 15
перестановок. Вычислив это произведение, мы найдем для числа задач игры внушительное число:
1 биллион 307 674 миллиона 365 000».
Из этого огромного числа задач ровно половина принадлежит к разрешимым и столько же — к неразрешимым. Заметим еще, что если бы возможно было ежесекундно давать шашкам новое положение, то, чтобы перепробовать все возможные расположения, потребовалось бы, при непрерывной работе круглые сутки, свыше 40 000 лет.
Странная задача на премию Профессор Г. Симон
Лет 20 тому назад в Берлине подвизался искусный счетчик, предлагавший публике такую задачу (переделываем ее на русский лад):
«Кто сможет уплатить 5 рублей, 3 рубля или 2 рубля полтинниками, двугривенными и пятаками, всего 20-ю монетами, — тому будет выдано наличными деньгами сто рублей».
Посетителям вручались необходимые монеты, — конечно, заимообразно. Но обещанная сотня рублей должна была остаться навсегда в руках счастливца, которому удалось бы решить задачу.
Разумеется, пол-Берлина потело над разрешением этой задачи (стояли как раз жаркие июльские дни), казавшейся не особенно трудной. Сто рублей хорошо пригодились бы всем, значит — стоит потрудиться. По мере того как выяснялась бесполезность попыток, физиономии решавших вытягивались, и розовые мечты о заманчивой награде испарялись. Надежды оказывались обманчивыми. Ловкий счетчик мог безбоязненно обещать в десять раз большую награду. Никто не вправе был бы на нее притязать, ибо задача требует невозможного.
Как в этом убедиться?
Нам не понадобится глубоко забираться в дебри алгебры, но все же не будем бояться х, у и z.
Рассмотрим сначала, можно ли уплатить требуемым образом пять рублей. Пусть для этого нужно × полтинников, у — двугривенных и z — пятаков. Сумма их должна составить 500 копеек, т. е.
50х + 20у + 5z = 100,
или, разделив на 5,
10х + 4у + z = 100.
Это легко осуществить на разные лады. Если, например, взять х = 8, то будем иметь
80 + 4у + z = 100,
или
4у + z = 20;
последнему уравнению можно удовлетворить, если принять z = 4, или 8, или 12, или 16 и, следовательно, (при z = 4) 4у = 16, у = 4. Действительно, 8 полтинников, 4 двугривенных и 4 пятака составляют 500. Однако при этом не выполнено условие употребить в общей сложности 20 монет: мы употребили 8 + 4 + 4 = 16 монет. К нашему первому уравнению