ООО «Шахматы», Санкт-Петербург,
тел: +7-905-223-03-53

МАТЕМАТИЧЕСКИЕ ЕДИНОБОРСТВА (продолжение-4)

Еще остается задача доказать правильность или ложность вышеприведенного утверждения, но, как бы трудно ни было раскрыть закон, столь же легко теперь доказать, что автор дал верный совет.

 

Заканчивая, выбирем какую-либо позицию, удовлетворяющую вышеназванному условию, B, и не удовлетворяющую ему, например, характеризующуюся свойством N. Как легко показать и очень скоро будет показано, результат выглядит следующим образом

1.Позиция 0, 0, 0 является позицией B;

2.В результате уменьшения трех чисел позиции B всегда возникает позиция N;

3.В результате соответствующего уменьшения одного из трех чисел позиции N всегда возникает позиция B.

Если это верно, то автор прав, ибо тот, кто обладает позицией B, должен, в соответствии с положением 2, предоставить противнику позицию N посредством уменьшения одной из кучек. Затем тот, согласно положению 3, снова может предоставить первому игроку позицию B. При этом числа постоянно уменьшаются до тех пор, пока, наконец, не создастся позиция 0, 0, 0, которая, будучи позицией B, при правильной игре не может быть создана тем, за кем первый ход — ее создает тот, кто делает ответный ход. Отсюда следует, что позиции B являются позициями с угрозой потери, если положения 1, 2 и 3 верны.

Но то, что положения 1, 2 и 3 верны, проясняется благодаря арифметике. Сначала просто видно, что позиция 0, 0, 0 проиграна для того, за кем очередь хода, следовательно, она является позицией B.

Затем становится ясно, что при уменьшении числа, написанного в двоичной системе, возникает новое число, написанное в той же системе, которое, будучи шаг за шагом прочитанным слева направо, с определенной очередностью заменяет единицу нулем. Если, например, я уменьшаю число

13 = 1101,

то должен получить число, которое, если я прохожу ряд слева направо, заменяет единицу нулем; это видно еще отчетливее, если речь идет о 8 = 1000 — при двоичном способе написания числа, меньшего 8, в четвертом ряду, конечно, не стоит единица. Если, с другой стороны, я уменьшаю двоичное число 1001, то должен буду заменить первую или последнюю единицу нулем. Если, двигаясь слева направо, я заменю ноль единицей, то я увеличил бы число, какое изменение в направление направо ни намеревался бы предпринять. Тем самым этот первый пункт очевиден. В ряду сверху вниз, где единица была заменена нулем, условие B не выполнено, так как в ряду стоит теперь одна-единствен- ная единица. Иными словами, в результате уменьшения одной из трех кучек, в соответствии с положением 2 из позиции B на деле всегда возникает позиция N, так как, по меньшей мере в одном ряду, число единиц нечетное.

Остается еще доказать, что и наоборот, из позиции N всегда можно в результате уменьшения одной из трех кучек создать позицию B. Возьмем в качестве примера позицию N.

11 110 010

10 101 001

1 110 110

Условие B было бы выполнено, если бы последнее число в двоичной системе было бы написано следующим образом:

1 101 011

Но ведь это последнее меньше указанного числа 1 110 110 позиции N, и я, следовательно, в результате уменьшения имеющегося числа могу создать число, удовлетворяющее условию. Необходимо ли церемонно облачать дедукцию в абстрактные понятия? Вряд ли!

Тем самым доказаны положения 1,2 и 3, а, следовательно, и положение, сформулированное неизвестным открывателем.

Вероятно, автор правила не доказал его таким способом, а обратил внимание на следующее обстоятельство благодаря знаку: если a, b, c — позиция с угрозой потери (например, 1, 2, 3), то такой же является и 2a, 2b, 2c (при вышеназванном примере 2, 4, 6) и, кроме того, 2a + 1, 2b + 1, 2c (3, 5, 6). Такое положение не столь далеко, как идея, от двоичного написания, и можно предположить, что оно послужило неизвестному гению, разглядевшему теорию игры «Возьми», в его путешествии первопроходца. Доказать это положение легко. Что должен сделать тот, за кем ход, в ситуации 2a, 2b, 2c? Если он уменьшит кучку 2a, то в результате создаст четное число 2A или нечетное число 2A + 1, где A меньше a. Теперь в ситуации A, b, c, так как A меньше a, а a, b, c — позиция с угрозой потери, несомненно, имеется ход, выводящий отсюда создание позиции с угрозой потери. Скажем, A, B, c — позиция с угрозой потери, где B меньше b. Следовательно, тот, за кем следующий ход, может ответить на ход

2A, b, c,

превратив b в 2B, а на ход 2A + 1, b, c превращением 2b в 2B + 1. Таким образом, второй игрок всегда ориентируется на меньшие позиции. Но применительно к меньшим позициям, например, 2, 4, 6 или 3, 5, 6 имеет силу теорема. Поэтому тот, за кем второй ход, может спокойно ориентироваться на вышеописанный способ и, добравшись до меньших позиций, оттеснить противника на позицию с угрозой потери.

Из этой теоремы следует конструкция, использующая двоичную систему, как можно доказать без больших усилий.

На основе игры «Возьми» можно создать различные другие игры, несколько модифицируя правила. Например, можно предписать, что из кучки горошин разрешается брать не более трех, бобов — не более двух, а чечевицы — не более одного зерна. С другой стороны, можно увеличить число кучек, например, до четырех или пяти. Первая вариация дает простое решение, а для второй даже нет необходимости варьировать положение о позициях с угрозой потери. Верно, в свою очередь, что позициями с угрозой потери являются те, которые в соответствии с двоичным написанием в каждом ряду имеют четное число единиц.

Интересная вариация возникает, если установить правила игры следующим образом: тот, за кем очередь хода, имеет право разделить кучку на две или уменьшить — по собственному усмотрению. Отличие от игры «Возьми» заключается в том, что теперь число кучек может расти во время игры. Например, при ситуации 1, 2, 3 тот, кому предстоит ходить, может разделить тройную кучку на две — из одного и из двух плодов, и легко увидеть, что тем самым он избегает поражения. Ведь что же теперь делать другому игроку? Если он разделит одну из двойных кучек, противник последует его примеру. Вообще-то противник действует последовательно, так он и должен выиграть. Отсюда следует, что 1, 2, 3 не является позицией с угрозой потери и что при татуировке только следующий шаг 1, 2, 4 ведет к возникновению позиции с угрозой потери.

Две позиции с угрозой потери, опирающиеся друг на друга, создают новую. Это можно понять без особых сложностей, так как второй игрок может так отвечать на ход начинающего игру, будто позиции с угрозой потери, не участвующей в игре, вообще не было бы, и должен таким способом в конце концов опустошить стол, т.е. выиграть. Например, так как 1, 1 и 1, 2, 4 представляют собой позиции с угрозой потери, в их число входит и 1, 1, 1, 2, 4.

В свою очередь, позиция с угрозой потери, соединенная с выигрышной позицией, дает выигрышную позицию, так как ход, который превращает первоначально выигрышную позицию в позицию с угрозой потери, превращает в позицию такого рода и расширенную позицию.

Это замечание важно для того, чтобы сократить трудную работу создания «татуировки», так как с его помощью каждая позиция, сколько бы кучек в ней ни было, может быть оценена, если только все позиции с угрозой потери принимаются за три кучки. Предположим, к примеру, позицию

2, 3, 4, 5.

Она имеет тот же характер, что и позиция 1, 1, 1, 2, 3, 4, 5, так как расширение на позиции с угрозой потери 1,1 не меняет характера. Эта расширенная позиция содержит, однако, позицию с угрозой потери 1, 2, 4, которая вследствие этого может быть упразднена. Первоначальная позиция имеет тем самым упомянутый характер, обозначенный как 1, 3, 5. Последняя, однако, представляет собой позицию с угрозой потери, как можно понять, исходя из знаний, полученных о положении кучек. Я делаю вывод, что 2, 3, 4, 5 представляет собой позицию с угрозой потери. Именно так в целом и поступают. Если предстоит оценить позицию

a, b, c, d, e,

то, следует справиться с таблицей по поводу трех кучек о том, какая кучка f дополняет пару a, b до позиции с угрозой потери и прибавить к вышеназванной позиции f, f, в результате чего характер не меняется. В этом случае она становится

a, b, c, d, e, f, f.

Теперь позицию с угрозой потери a, b, f расщепляют, получая тем самым

c, d, e, f,

и эта позиция содержит теперь четыре кучки. Можно еще раз продолжить применение этого метода, пока позиция не будет сведена к одной из трех кучек. Характер последней позиции известен согласно предпосылке, следовательно, таким образом можно определить и характер первоначальной.

Предпосылка, конечно, заключалась в том, что характер позиций трех кучек известен. Для того, чтобы выполнить эту предпосылку, следует татуировать, т.е. систематически продвигаться от меньших кучек к большим.

Позиции с угрозой потери 1, 2, 4 и 1, 3, 5 уже известны нам. Исследуем теперь 2, 3, 6. В результате уменьшения 2, 3 или 6 возникает выигрышная позиция, так как новая позиция ведет, очевидно, к известным позициям с угрозой потери. Возникает вопрос о том, спасает ли, скажем, позицию расщепление кучки. Сразу же обнаруживается, что расщепление 2 или 3 ведет к потере. Если расщепить 6 на 5, 1, то противник берет 2 и выигрывает. Также и расщепление 6 на 4, 2 или 3, 3 ведет к потере. Тем самым установлено, что 2, 3, 6 является позицией с угрозой потери — на шаг дальше в татуировке.

1, 6, 8 — позиция с угрозой потери, так как расщепление 8 не помогает, а еще менее другие ходы.

Труднее определить характер 1, 7, 9, так как расщепление 9 на 6+3 проблематично. Характер 1, 7, 6, 3 является как раз тем же, что и 1, 7, 2, так как 6,3, 2 — позиция с угрозой потери, а отсюда мы видим, что 1, 7, 6, 3 выигрышная позиция и, следовательно, 1, 7, 9 — позиция с угрозой потери. 1, 10, 12 при уменьшении 10 или 12 с несомненностью ведет к формированию выигрышных позиций; сомнительными снова оказываются позиции, которые возникают отсюда в результате расщепления 10 или 12. 1, 6, 4, 12 — выигрышная позиция; 1, 7,3, 12 имеет характер 9, 3, 12, так как 1, 7, 9 — позиция с угрозой потери, а поэтому 1, 7, 3, 12 — выигрышная позиция; 1, 8,2, 12 имеет характер 4, 8, 12 — выигрышная позиция, так как 12 = 8+4; расщепление 10 ведет, следовательно, к формированию выигрышных позиций. 1, 10, 9, 3 имеет характер 10, 7, 3 — выигрышная позиция; 1, 10, 7, 5 имеет характер 10, 7, 3 — выигрышная позиция; 1, 10, 8, 4 имеет характер 10, 8, 2 — выигрышная позиция. Следовательно, также и расщепление 12 ведет к формированию выигрышных позиций. Поэтому 1, 10, 12- позиция с угрозой потери.

Общий закон уже виден. Позиция 1,2+4n, 4+4n, как и 1,3+4n, 5+4n являются позициями с угрозой потери для всех значений n. Для n = 0 эта величина возвращается к 1, 2, 4, как и 1, 3, 5; для n = 1 к 1, 6, 8 и 1, 7, 9; для n = 2 — к 1, 10, 12 и 1, 11,13. Можно привести доказательства этого предположения с помощью математической индукции; материалы для доказательства уже четко указаны выше, так как, подобно первым шагам, можно действовать и дальше. Нет необходимости приводить доказательства в виде математической проблемы, но от этого читателя убережем; для специалиста эта задача не особенно трудна, пока он не упускает из виду то обстоятельство, что каждая позиция a, b, a+b является выигрышной позицией, так как в результате расщепления a+b на a, b отсюда возникает позиция с угрозой потери.

ООО «Шахматы»

Санкт-Петербург

время работы с 10-00 до 19-00

тел. 983-03-53 или 8-905-223-03-53

 SKYPE - Piterchess

 ICQ - 229-861-097

 VIBER: +79052230353

 info@64ab.ru