Все поля шахматной доски 8 на 8 покрыли 32 мя косточками домино

Обновлено: 19.04.2024

На доске 8×8 клеток можно расположить несколько доминошек (то есть прямоугольников из двух клеток), не накладывающихся друг на друга. Пусть N количество способов положить так 32 доминошки, а S количество способов положить так 16 доминошек. Что больше N или S? Способы, которые получаются друг из друга поворотом или отражением доски, считаются различными

задан 26 Фев '17 20:34

1 ответ

Задача аналогична этой, но здесь есть своя небольшая специфика.

Докажем, что $%S > N$%. Для этого каждому 32-покрытию мы сопоставим некоторым способом 16-покрытие так, чтобы разным покрытиям всей доски соответствовали разные частичные покрытия с помощью 16 доминошек. Иными словами, мы должны предъявить способ снять 16 доминошек, а потом показать, что положить их на место можно однозначно. Отсюда будет следовать, что $%S\ge N$%. Строгое неравенство следует из того факта, что можно предъявить примеры (достаточно всего одного!) 16-покрытий, не продолжаемых до полного покрытия. Сделать это легко, создавая "изолированные" угловые клетки.

Выделим 16 клеток -- 8 чёрных и 8 белых. Укажем их в шахматной нотации: a1, a5 (чёрные), b3, b7 (белые). Дальше периодически повторяем: c1, c5, d3, d7, e1, e5, f3, f7, g1, g5, h3, h7.

Среди выделенных 16 клеток нет соседних по стороне. Поэтому каждая из этих клеток покрыта своей доминошкой. Их будет ровно 16. Снимем их с доски, и проверим, что положить их на место можно однозначно. Прежде всего, укажем на основное отличие от предыдущей задачи. Рассмотрим клетку b1. Допустим, что она пустая. Какой доминошкой тогда она покрыта? То ли a1-b1, то ли c1-b1? Чтобы выяснить это, начнём восстанавливать картину слева, то есть с вертикали "a". У нас была доминошка, покрывающая a1. Она могла лежать двумя способами, покрывая a1-a2 или a1-b1. Предположим первое. Тогда клетка a2 освобождается. Но она не могла быть покрыта ничем другим. Тогда это однозначно говорит о том, что надо положить на место a1-a2.

Предположим теперь, что a2 не свободна. Тогда b1 обязана быть свободной, и снятая доминошка занимала клетки a1-b1. Теперь переходим к a5. Если рядом с ней по вертикали что-то свободно, то доминошка, покрывающая a5, там и лежала. Заметим, что обе клетки a4 и a6 одновременно освободиться не могли. Если они обе заняты, то доминошка лежит горизонтально: a5-b5.

По первой вертикали всё восстановили однозначно, и теперь переходим ко второй. Там всё аналогично: если рядом с b3 по вертикали есть свободная клетка, то кладём туда доминошку, покрывавшую b3. Такая клетка, если она есть, всего одна. Если её нет, то сначала смотрим влево. Если клетка a3 свободна, то кладём на место a3-b3, так как a3 ничем другим не покрывается. Если a3 не свободна, то единственным вариантом будет b3-c3. И так далее, слева направо и снизу вверх. Изначальное расположение мы однозначно можем восстановить.

Все поля шахматной доски 8 × 8 покрыли 32-мя косточками
домино. Каждая косточка закрывает в точности два поля. Докажите,
что при любом покрытии число вертикально лежащих косточек чётно,
и число горизонтально лежащих косточек тоже чётно

Наконец-то хоть одна интересная задача на мэил ру!

Вот, собственно, моё решение.

Очевидно, что если покрытие корректно (а нам именно такие и нужны) , то число_горизонтальных_косточек = 32 - число_вертикальных_косточек. Поэтому достаточно доказать что в любом корректном покрытии чётное число вертикальных косточек (тогда число горизонтальных становится чётным автоматически) .

Пройдёмся по шахматной доске сверху вниз по рядам и попробуем расставлять вертикальные косточки разными способами. В силу произвольности расстановки это и будет означать правильность утверждения.

Будем говорить, что вертикальная косточка открывается в этом ряду, если она начинается в этом ряду, если смотреть сверху вниз. Будем говорить, что вертикальная косточка закрывается в этом ряду, если она была открыта на 1 ряд выше. Будем говорить, что ячейка свободна, если на ней ещё не разместили никакую доминошку.

Допустим, мы находимся в самом первом ряду. В первом ряду 8 свободных ячеек. Мы можем открыть в нём только чётное число вертикальных доминошек, так как иначе в нём останется нечётное число свободных ячеек, и их гарантированно не получится покрыть горизонтальными доминошками (потому что горизонтальные понижают число свободных ячеек на 2 - чётное число) .

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

Продолжая рассуждения и далее до 7го ряда, закроем все доминошки на 8м ряду. Очевидно, что число вертикальных доминошек равно числу открываний вертикальных доминошек, а на каждом ряду мы могли открыть лишь чётное число доминошек, поэтому сумма открываний доминошек чётна.

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

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

У вас есть самая обыкновенная шахматная доска, размер которой 8х8 . При этом, в шахматной доске нету двух противоположных по диагонали квадратиков. Также у вас есть 31 кость домино. Ваша задача состоит в том, чтобы ответить на простой вопрос: можно ли расположить все кости на шахматной доске? Одна кость занимает два квадратика. Обычно, если на собеседовании задают подобный вопрос, то еще просят обосновать свой ответ, поэтому сделайте это тоже.

Решение

Давайте начнем с самого начала. У вас есть доска размером 8х8 , соответсвенно на доске есть 64 квадратика. Если учесть тот момент, что двух не хватает, то получаем цифру 62. Теперь если каждое домино занимает по два квадратика, а у нас 31 кость домино, то хочется сразу ответить положительно, но это будет неправильный ответ.

На этом этапе важно заметить, что мы удалили именно два противоположных по диагонале квадратика. Это означает, что на нашей доске осталось на два, к примеру, черных квадратика меньше, нежели белых квадратиков. Таким образом, у нас на доске сейчас 32 белых и 30 черных квадратов.

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

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

Итак, ответ для данной задачи - нет!

Больше интересных новостей

Задача про вентилятор

Найдите ошибку в коде

Логическая задача про стопку монет

Шахматная доска и кости домино

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

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

Nota bene! Материал этой статьи — это усеченный вариант вот этого jupyter-notebook, все картинки и анимации, которые вы увидите в статье, сгенерированы кодом из этого ноутбука (правда анимаций не будет в github предпросмотре). К слову, картинки из заголовка также сгенерированы с помощью python/matplotlib

Сделать это невозможно, и этому есть красивое и простое объяснение:

На оставшейся части доски 30 черных и 32 белых клетки
Каждая доминошка состоит из одной черной и одной белой клетки
Как бы мы не разрезали фигуру на доминошки, в итоге на доминошках будет равное число белых и черных клеток

Динамическое программирование по профилю

Про динамического программирования есть статья на хабре, которая даже содержит пример с покрытием доминошками, я немного расширю этот пример.

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

Аналогично можно вычислить число "сочетаний" , воспользовавшись одним из следующих рекуррентных соотношений

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

Посмотрим на следующий класс фигурок: у нас есть прямоугольник , на строке присутствуют первые клеток, остальные задаются профилем, на строке первые клеток задаются профилем, остальные не участвуют. Профиль — это последовательность нулей и единичек длины : если на -ой позиции профиля единичка, это значит что в этой фигуре есть соответствующая клетка, всего профилей (красные клетки — единички, синие — нули).

Профиль однозначно задается числом (его бинарное представление вплоть до разрядов является последовательностей нулей и единичек).

Прямоугольник соответствует фигуре с , и нулевым профилем. На фигурках такого типа мы можем считать две основные функции

Максимальное возможное число покрытых доминошками клеток в этой фигуре
Количество способов полностью покрыть доминошками эту фигуру

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

горизонтальную доминошку, если это возможно

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

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

Сверяемся с википедией, пока все в порядке. Давайте еще на всякий случай проверим, количество способов замостить полоску — должно получиться число Фибоначчи.

Что ж, поехали дальше, проверим на доске с вырезанными углами

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

Слишком просто, давайте вырежем несколько клеток

Попробуем теперь сделать тоже самое для замощения максимальной возможной части фигуры

И попробуем фигурку из заголовка

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

Замощение с помощью решения задачи о максимальном паросочетании

Возвращаясь к черно-белой раскраске как на шахматной доске можно заметить интересную интерпретацию задачи замощения доминошками. Давайте посмотрим на граф, в котором клетки фигуры — это вершины, ребрами соединены клетки, имеющие общую сторону. Так вот, доминошка в этом графе — это как раз ребро. Если раскрасить граф в шахматном порядке, то внезапно можно обнаружить, что этот граф — двудольный, черные — одна доля, белые — другая. Если переформулировать задачу замощения наибольшего числа клеток в терминах этого графа, то получается, что нужно найти максимальное по размеру множество ребер такое, чтобы вершины являлись концом не более одного ребра. В общем то, это довольно известная задача о максимальном паросочетании. Давайте попробуем её применить для решения этой задачи, тут получится даже с анимацией, приведу базовый алгоритм Куна для нахождения максимального паросочетания.

Здесь даже получается проанимировать процесс

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

UPD. Для последнего примера простое обоснование на основе черно-белой раскраски не работает. Насколько мне известно, есть два общих критерия для существования полного замощения:

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

Бонус! Раскраска планарного графа в 5 цветов.

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

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

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

Рассмотрим прежде всего несколько задач о покрытии доски костями домино размером 2×1. Всюду предполагается, что каждое домино покрывает два поля доски, а каждое поле покрыто одной половиной домино. Начнем со следующей старинной задачи.

Можно ли покрыть домино квадрат размером 8×8, из которого вырезаны противоположные угловые клетки (рис. 2,а)?

Мы могли бы воспользоваться алгебраическими рассуждениями12, однако «шахматное» решение и проще, и изящнее. Окрасим наш урезанный квадрат в черно-белый цвет, превратив его в шахматную доску без двух угловых полей a8 и h1 (рис. 2,б). При любом покрытии доски каждое домино покрывает одно белое и одно черное поле. У нас же белых полей на два меньше, чем черных (вырезанные поля - белые), и поэтому необходимого покрытия не существует! Как мы видим, раскраска доски не только позволяет шахматисту легче ориентироваться во время игры, но и служит средством решения математических задач.

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

Пусть теперь на шахматной доске вырезаны два поля разного цвета. Всегда ли можно покрыть оставшуюся часть доски 31 домино?

Оказывается, что всегда. Эффектное доказательство нашел известный американский математик Р. Гомори. Проведем на шахматной доске границы между вертикалями и горизонталями так, как показано на рис. 3. В лабиринте между этими границами черные и белые поля следуют друг за другом, чередуясь, как пуговицы двух цветов на замкнутой нити (путь, по которому можно обойти этот лабиринт, является замкнутым). Какие бы два поля разного цвета мы ни вырезали из доски, нить разорвется: в одном месте, если вырезанные поля находятся рядом, и в двух местах - в противном случае. При этом каждый кусок нити будет состоять из четного числа полей. Следовательно, эти куски, а значит - и всю доску, покрыть домино можно!

Любопытные идеи, связанные с пуговицами и нитями, мы еще встретим в главе 11.

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

Задачи о шахматной доске и домино составляют лишь небольшую часть огромной серии задач такого сорта. Американский математик С. Голомб создал целую науку, которую назвал полимипо, а его книга, посвященная этой теме, переведена во многих странах мира, в том числе у нас13. В общем случае полимино представляет собой односвязную фигуру, состоящую из квадратов. С точки зрения шахматиста односвязность означает, что все квадраты полимино можно обойти ходом ладьи. В зависимости 07 числа квадратов, полимино бывают различного тига. Мономино содержит один квадрат, домино - два, тримино - три, тетрамино - четыре, пентамино - пять, гептамино - шесть квадратов и т. д. В задачах о полимино покрываются разнообразные доски, не обязательно прямоугольные. Мы остановимся еще на нескольких вопросах, связанных с обычной шахматной доской. Очевидно, покрыть дсску только прямыми тримино, т. е. домино 3×1, невозможно, так как 64 не делится на 3. Возникает следующая задача.

Можно ли покрыть шахматную доску 21 прямым тримино и одним мономино? Если это возможно, то какие поля может занимать мономино?

Одно из необходимых покрытий дапо на рис. 4,а. Для определения возможных расположений мономино проведем на доске две системы параллельных прямых, как показано на рис. 4,б.

Легко убедиться, что при любом покрытии каждое тримино покрывает ровно одно поле, через которое проходит сплошная линия, и ровно одно, через которое проходит пунктирная линия. Поскольку число полей, пересекаемых сплошными прямыми, равно 22, так же как и число полей, пересекаемых пунктирными прямыми, а тримино имеется 21, то мономино может покрывать лишь поля, пересекаемые обоими семействами прямых. А таких полей - всего четыре: c3, c6, f3 и f6! Поворачивая доску на 90, 180 и 270°, можно получить соответствующие покрытия для каждого из этих четырех полей.

Следующая задача несколько отличается от рассмотренных выше.

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

Если представить себе, что доска - это стенка, а домино - кирпичи, то существование указанной границы (шва) свидетельствует о непрочной кладке. Иначе говоря, в задаче спрашивается, можно ли расположить «кирпичи» так, чтобы «стенка» не рухнула. Прямоугольник, который удается покрыть необходимым образом, называется «прочным». В «прочности» шахматной доски можно убедиться на рис. 5. В общем случае Гарднер показывает, что из домино можно сложить «прочный» прямоугольник, если его площадь четна, а длина и ширина больше четырех, при этом исключение составляет лишь квадрат 6×6.

Ниже мы будем часто иметь дело с прямоугольными шахматными досками того ила иного размера. При этом всегда считается, что доска m×n имеет m вертикалей и n горизонталей (шахматных). Мы говорим, что доска «четна», если число ее полей четно, и «нечетна» - в противном случае. Всюду, где размеры доски не указаны, имеется в виду стандартная шахматная доска, для которой m = n = 8.

Доска 100×4 покрыта домино. Доказать, что ее можно распилить по одной из границ между вертикалями и горизонталями, не затрагивая ни одного домино.

Любая из указанных границ делит доску на две части, состоящие из четного числа полей. Поля каждой части разобьем на два класса: покрытые домино, целиком лежащими в этой части, и покрытые домино, пересекаемыми границей. Так как число полей каждой части четно (быть может, нуль), равно как и число полей первого класса (каждое домино покрывает два поля), то и число полей второго класса четно. А это и значит, что число домино, пересекаемых границей, четно. Всего разделяющих границ существует 102 (99 вертикальных и 3 горизонтальных), н если каждая из них пересекает домино, то в покрытии участвует не менее 102×2 = 204 домино. В нашем же распоряжении их только 200! Фактически мы показали, что прямоугольник 100×4 является «непрочным».

Вопрос о возможности покрытия произвольной прямоугольной доски линейными k-мино (домино k×1) решается следующей теоремой14.

Доску m×n можно покрыть линейными k-мино в том и только в том случае, если хотя бы одно из чисел m или n делится без остатка на k.

Проиллюстрируем теорему на следующем примере.

Можно ли покрыть доску 10×10 (на такой доске играют в стоклеточные шашки) прямыми тетрамино?

Прямое тетрамино имеет размеры 4×1, и, значит, в принципе 25 костей могли бы покрыть все поля нашей доски. Однако из теоремы следует, что это невозможно - 10 не делится на 4.

Рассмотрим еще несколько задач о шахматной доске. В решении следующей задачи виовъ используется ее раскраска.

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

Задание невыполнимо. Действительно, если бы указанное смещение фигур существовало, то каждая «белая» фигура (стоящая на белом поле) стала бы «черной» (попала на черное поле), а каждая «черная» - «белой».

Таким образом, доска состояла бы из одинакового числа белых и черных полей, а это противоречит ее «нечетности».

Популярными являются задачи о разрезании шахматной доски. Самой известной из них является следующая, принадлежащая С. Лойду.

На полях a1, b2, c3, d4 стоят четыре коня. Разрезать доску на четыре конгруэнтные части (совпадающие при наложении) так, чтобы на каждой из них оказалось по коню.

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

Пусть после нескольких разрезов доски образовавшиеся части разрешается перекладывать так, чтобы следующий разрез мог рассечь не одну, а сразу несколько частей. Сколько разрезов потребуется для получения 64 отдельных полей доски (квадратов 1×1)?

Сначала разрежем доску пополам, затем обе половины положим рядом и разрежем доску на четыре одинаковые части и т. д. Всего понадобится 6 разрезов (2 е = 64) и меньшим числом не обойтись.

Пусть теперь части доски разрешается резать только отдельно. Сколько разрезов понадобится для получения 64 полей в этом случае?

Как правило, эта задача (особенно, если она предлагается после предыдущей) вызывает определенные трудности. Видимо, это связано с некоторой инерционностью нашего мышления. Ведь сразу видно, что понадобится 63 разреза! Действительно, каждый разрез увеличивает число частей на единицу; при этом в начальный момент мы имеем одну часть (саму доску), а в конечный - 64 (все поля доски).

В задаче на рис. 7,а требуется выполнить три задания, причем одно математическое и два чисто шахматных:

а) разрезать доску на четыре конгруэнтные части;

б) заматовать черного короля кратчайшим путем при ходе белых;

в) заматовать черного короля кратчайшим путем при ходе черных верные играют кооперативно).

Решения: а) как нужно разрезать доску, показано на рис. 7,б; б) при ходе белых мат дается на 12-м ходу: 1-12. Сe1-b4, Крe3-d3-c4, Сe4-c2-b3, Крc4-c3, Сb4-d6, Сb3-d5, Крc3-c2, Сd6-c5, Сd5-c4, Сd6-b4 мат (все ходы черного короля вынуждены и не приводятся); в) при правильной игре после 1. … Крe6-e7 мат невозможен, так как черный король скрывается на e8 - 2. Сe1-b4+ Крe7-e8, и чернопольный слон вынужден уйти с диагонали a3 - e7 ввиду угрозы пата. Однако если черные играют кооперативно (помогают белым дать мат), то цель достигается всего через три хода:
1. … Крe6-d6
2. Крe3-d4 Крe6-e7
3. Сe1-b4+ Крe7-e6
4. Сe4-d5 мат. Ряд полей нашей доски при матовании не используется, но при их исключении не было бы задачи на разрезание доски.

Рассмотрим теперь один известный парадокс, связанный с разрезанием шахматной доски. Разрежем доску на четыре части, как показано на рис. 8,а (в данном случае нам невыгодно раскрашивать ее поля), и из образовавшихся частей сложим прямоугольник (рис. 8,б). Площадь доски равна 64, а площадь полученного прямоугольника равна 65. Таким образом, при разрезании доски откуда-то взялось одно лишнее поле!

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

Известный популяризатор математики начала века Е. Игнатьев придумал «метод шахматной доски», позволяющий выводить различные формулы15. Приведем два несложных примера на эту тему.

Найдем сумму n первых натуральных чисел «методом шахматной доски». Для этого на доске (n + 1)×n (на рис. 9,а n = 8) окрасим в чериый цвет все поля первой вертикали, все поля второй вертикали (кроме верхнего), третьей вертикали (кроме двух верхних) и т. д., наконец - нижнее поле n-й вертикали. В результате белых и черных полей на нашей доске будет поровну, а именно 1 + 2 + … + n. Поскольку вся доска состоит из п (n + 1) полей, получаем
2 (1 + 2 + … + n) = n(n + 1),

откуда вытекает известная формула для суммы арифметической прогрессии:
1 + 2 + … + n = n(n + 1)/2.

Для этого возьмем доску (2n + 1)×(2n + 1) и закрасим ряд ее полей черным цветом так, как показано на рис. 9, 6 (для случая n = 5). Очевидно, каждая черная часть содержит (1 + 2 + … + n) полей. Без учета центрального поля мы имеем здесь четыре одинаковые белые и черные части. Необходимая формула следует из того, что наша доска содержит (2n + 1)² полей и состоит из центрального поля и восьми одинаковых частей (четырех белых и четырех черных - рис. 9,б).

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

Рис. 10. Теорема Пифагора на шахматной доске:
а - квадрат и четыре треугольника; б - два квадрата и четыре треугольника

В заключение главы приведем одно старинное доказательство на шахматной доске… теоремы Пифагора. Нарисуем на доске квадрат, как показано на рис. 10,а. Доска разбивается на этот квадрат и четыре конгруэнтных прямоугольных треугольника. На рис. 10, 6 мы видим те же четыре треугольника, а также два квадрата. Итак, треугольники в обоих случаях занимают одну и ту же площадь. Следовательно, одну и ту же площадь занимают и оставшиеся части доски без треугольников, на рис. 10,а - одного квадрата, а на рис. 10,б - двух. Поскольку большой квадрат построен на гипотенузе прямоугольного треугольника, а маленькие - на его катетах, то «пифагоровы штаны во все стороны равны»!

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

12. Именно такое решение дано в книге Т. Саати «Целочисленные методы оптимизации и связанные с ними экстремальные проблемы» (М., «Мир», 1973).

13. С. Голомб. Полимино. М., «Мир», 1974.

14. Она доказана А. Сойфером в статье «Клетчатые доски и полимипо» («Квант», 1972, № 11); там же приведен ряд новых задач о полимино.

15. Е. Игнатьев. В царстве смекалки, или арифметика для всех. Кн. 1 - 3. М. - Пг., Госиздат, 1923.

Читайте также: