Математика шахматной доски

Математика шахматной доски
Александр Сергеевич Киселев

Задачи, связанные с шахматной доской, обсуждаются на математических кружках издавна. Наверное, одной из причин этого является одновременная обиходная простота шахмат (все видели доску и большинство даже слышали, как ходят фигуры) и их невероятная сложность (гроссмейстеры учатся годами, чтобы выигрывать в этой игре) – этот дуализм, который делает шахматную доску, возможно, наилучшим объектом для исследования на первом году кружка, когда детям ещё чужды абстракции и важны связи с осязаемым миром.

Математика шахматной доски

Александр Сергеевич Киселев

© Александр Сергеевич Киселев, 2022

ISBN 978-5-0056-2265-5

Создано в интеллектуальной издательской системе Ridero

Вступление

Взаимоотношения шахмат и математики достойны если не целого романа-эпопеи, то уж как минимум объёмной повести. Математики знают, что в шахматах, как и в любой другой игре с конечным числом позиций, существует выигрышная стратегия для одного из игроков – за это шахматистам впору ненавидеть математиков. Однако общее число всех возможных позиций настолько огромно, что даже современным компьютерам не под силу провести их полный перебор – и за это математикам уже впору возненавидеть шахматистов (или, вернее, того, кто эту будоражащую умы игру изобрёл).

Тем не менее, современные шахматные программы уже стабильно обыгрывают игроков-людей, даже не имея возможности перебрать все варианты – ведь и частичный перебор машине удаётся намного лучше, чем человеку. Но, несмотря на значительные успехи компьютеров, шахматы вполне живы и активно развиваются, как вид спорта.

Многие известные шахматисты (например, А. Е. Карпов или М. Н. Таль) в юности проявляли математические способности и выигрывали математические олимпиады, а М. М. Ботвинник и вовсе был доктором техническим наук и крупным специалистом по электротехнике. Многие известные математики (например, академик А. А. Марков) и физики (например, академик П. Л. Капица) достаточно хорошо играли в шахматы.

Задачи, связанные с шахматной доской, обсуждаются на математических кружках[1 - Об устройстве непосредственно моего математического кружка написано в Приложении 1.] издавна. Наверное, одной из главных причин этого является одновременная обиходная простота шахмат (все дети хоть раз видели доску и большинство даже слышали, как ходят основные фигуры) и их невероятная сложность (ведь гроссмейстеры учатся годами, чтобы научиться выигрывать в этой игре) – этот дуализм, который и делает именно шахматную доску, возможно, наилучшим объектом для исследования на первом году математического кружка, в котором детям ещё чужды абстракции и так важны связи с реальным осязаемым миром.

Задачи, которые обсуждаются в этой книге, делятся на два типа: первый будет связан с разрезанием самой доски и, как правило, вообще не использует магию шахмат (хотя там иногда нелишне бывает вспомнить о раскраске, характерной для шахматной доски), а второй связан с шахматными фигурами, непосредственно с тем, как они ходят и бьют.

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

В завершение вступительной части отмечу, что ещё больше интересных сюжетов, чем я опишу дальше, на стыке шахмат и математики можно почерпнуть в прекрасной книге [4], написанной шахматистом и кандидатом технических наук Евгением Гиком сорок лет назад. С тех пор ничего настолько масштабного и подробного по теме не выходило.

Задачи на разрезание

Полимино

Клетчатые фигурки, о которых пойдёт речь в этом параграфе, известны людям с древности. Однако публикации различных результатов, связанных с ними, относятся к первой половине ХХ века, а сам термин «полимино» (от греческого ????? «многий, множественный») ввёл в употребление американский математик Соломон Голомб, в 1953 г. выступивший с докладом о «новой математической забаве» в Гарвардском математическом клубе. Он же впервые использовал названия для конкретных фигур: мономино (состоящее из одной клетки), домино (из двух), тримино, тетрамино, пентамино и гексамино. Впоследствии Мартин Гарднер значительно поспособствовал популяризации этих терминов. В книгах [1], [2] и [3] можно найти ещё много любопытной информации.

Как обычно, за сто с лишним лет после первого появления этих задач (и шестьдесят с лишним после появления названия) задачи, связанные с полимино, сильно помолодели – если тогда их решали взрослые, дипломированные и остепенённые математики, то теперь основными решателями таких задач стали школьники. Некоторые из них вполне доступны даже первокласснику (что проверено на реальных первоклассниках), поскольку не требуют никаких знаний.

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

Первый естественный вопрос, связанный с полимино, это их количество для каждого вида. То, что мономино всего одно, сомнений не вызывает. Как получить все варианты для домино? Достаточно добавить одну клетку к мономино. Легко увидеть, что во всех четырёх случаях получается одно и то же (с точностью до поворота), поэтому фигурка из двух клеток (домино) всего одна.

Рисунок 1. Получаем домино из мономино

Двигаясь дальше, выясняем, что тримино бывают уже двух видов: прямое и угловое.

Рисунок 2. Получаем тримино из домино

Точно так же добавляем клетки и получаем пять различных видов тетрамино (см. рисунок 3) и 12 различных видов пентамино (это упражнение предлагается самостоятельно выполнить читателю, соответствующая картинка приведена в Приложении 2).

Рисунок 3. Получаем тетрамино из тримино

Тетрамино имеют устоявшиеся названия, которыми мы будем пользоваться в дальнейшем (на рисунке 3 слева направо и сверху вниз: прямое тетрамино, T-тетрамино, косое тетрамино, L-тетрамино и квадратное тетрамино).

Аналогично можно получать и все фигурки большего размера.

Разрезания шахматной доски на полимино

Достаточно естественным образом встаёт вопрос: из каких полимино можно составить доску? Чаще всего задача формулируется в другую сторону: на какие полимино можно разрезать всю доску (без остатка)? При этом слово «разрезать» здесь не следует трактовать буквально (хотя в моей практике был школьник, который именно так и поступал: брал бумажный квадрат 8?8 и резал его на заявленные части – однако даже к нему быстро пришло понимание, что результат такой работы будет практически невозможно продемонстрировать педагогу).

Ясно, что на мономино шахматная доска разбивается достаточно легко. Не вызывает особенных проблем и её разбиение на домино.

Рисунок 4. Разбиение на мономино

Рисунок 5. Разбиение на домино

Попытка разбить на прямые тримино приводит к тому, что остаётся одна клетка, не входящая ни в одну фигурку. Младшие школьники обычно либо в растерянности (им в принципе непривычно, что на вопрос «можно ли» бывает отрицательный ответ), либо говорят, что разрезать невозможно, потому что у них осталась одна лишняя клетка.

Школьник постарше, знакомый с понятием делимости, сразу формулирует это иначе: доску нельзя разрезать на тримино (хоть на прямые, хоть на угловые), потому что её площадь не делится на 3 (не делится без остатка, как принято называть это явление в школе[2 - По поводу понятия делимости смотрите Приложение 3.]). Интересно, что на резонный вопрос «А почему она должна делиться?» некоторые из них ответить не могут, то есть это наблюдение настолько интуитивно очевидное, что далеко не всегда ребёнок задумывается над его причинами.

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

Условие делимости площадей является необходимым, то есть если площадь доски не делится на площадь маленьких фигурок, то разрезать точно не удастся. Обратное неверно!

Но для тримино всё работает идеально в нужную сторону: площадь шахматной доски (64 клетки) не делится на площадь тримино (3 клетки), поэтому её невозможно разрезать ни на прямые, ни на угловые тримино.

Так как 64 делится на 4, то никаких очевидных проблем с разрезанием доски на тетрамино не предвидится. Действительно, на прямые, квадратные, L- и T- тетрамино её разрезать можно.

Рисунок 6. Разбиение на прямые тетрамино

Рисунок 7. Разбиение на квадратные тетрамино

Рисунок 8. Разбиение на L-тетрамино

Рисунок 9. Разбиение на T-тетрамино

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

На самом деле разрезать шахматную доску (как и любой другой прямоугольник) на косые тетрамино нельзя. Классическое доказательство этого факта такое: предположим, что у нас получилось, тогда каждая клетка доски входит в какое-то косое тетрамино. Рассмотрим угловую клетку, у неё есть всего два варианта, какой тетраминошкой она покрыта (на самом деле эти варианты одинаковы с точностью до поворота доски).

Рисунок 10. Варианты покрытия угловой клетки косым тетрамино

Тогда третья от угла клетка покрыта однозначно, тогда и пятая от угла покрыта однозначно, а для покрытия седьмой от угла уже не остаётся никакой возможности.

Рисунок 11. Покрытие стороны косыми тетрамино

Такое же рассуждение можно провести и для прямоугольника любого другого размера.

Получилась важная вещь: необходимого условия вовсе не достаточно, чтобы утверждать, что разрезание возможно. Эту информацию можно донести до школьника и на более очевидном примере (я особенно люблю полоску 1?64), но иногда школьнику кажется, что если доска будет достаточно широкой, чтобы хотя бы одно полимино на неё поместилось, то никаких проблем с разрезанием он не встретит. Шахматная доска лучше подходит для развенчания этого мифа.