49
Ферзь—часовой
В предыдущем разделе наших заметок*) мы установили, что конь может обойти все поля шахматной доски размером 8×8, повышав на каждом из них лишь по разу.
Вопрос об обходе обыкновенной шахматной доски другими фигурами решается значительное проще. Например, длялады такой маршрут изображен на рисунке 1. Здесь
Рис. 1.
ладья добавляется своей цели, делая по дороге 14 поворотов. Докажите, что это число нельзя уменшить.
Указанный путь (он, кстати, подходит также для ферзя и короля) не замкнут. Оdnako мо-
*) См. «Квант», № 8, 9.
жно предложить и замкнутый маршрут (рис. 2). Здесь ладья при
Рис. 2.
желания с конечного поля своего путешествия — a2 может вернуться на исходное — a1. Убедитесь сами, что на нечетной доске (например, размером 7×7 или 9×9) замкнутого пути длялады уже не существует.
Понятно, что для слона задача в обшем случае поставлена некорректно (слон может ходить лишь по полям одного цвета), но если ограничиться только белыми или черными полями, то она также легко решается.
Тепер мы переходим к одним из наиболее распространенных матей-
матических задач на шахматной доске. Эти задачи связаны с различными расстановками фигура, поэтому их обычно называют компбинаторными. Пожалуйста, самой известной из них является следующая «задча о восыми ферзях», поставленная в 1850 году вликиим немецким математиком Ф. Гауссом.
Рассматрить на шахматной доске 8 ферзей
Рис. 3.
так, чтобы никакие два из них не уроскали друг другу*).
На рисунке 3 изображено одно из воз-
*) Конечно, с шахматной точки зрения две фигуры одного цвета не могут угрожать друг другу, но мы получаемся традиционной терминойлогией.
50
можных решений задачи, всего же их существует 92. Доказано также, что все они получаются из 12 основных позиций применением зеркального отражения и поворотами доски на 90°, 180° и 270°. Например, отражая зеркально (относительно пунктирной линия) приведению позицию, получаем другую позицию, устанавливающую нас (рис. 4) *).
Любопытно, что сам Гаусс первоначально представил, что задача допускает лишь 72 решения, и сомневался в правильности числа 92. В нашей эта задача и подобные ей решаются за несколько минут. Достаточно составить несколько программы и ввести ее в вычислительную машину, вскоре все 92 позиции будут выданы на печать.
Сформулируем два вопроса, которые приводят нас соответственно к двум классам разнообразных комбинаторовых задач.
*) Подробно эта задача решается в книге Л. Я. Окунева «Комбинаторные задачи на шахматной доски» (ОНТИ НКТП СССР, 1936)
-
Какое наиболее число однозименных фигур (ферзей, ладей, коней, слонов и королев) можно рассматривать на доске так, чтобы никакие две из них не урезокали друг друга?
-
Какое наиболее число однозименных фигур можно рассматривать на доске так, чтобы никакие две из них не урезокали друг друга?
Первое из этих чисел в теории графов называется числом внутренней устойчивости, а второе — числом внешней устойчивости. Поняття эти далеко не абстрактны, и играют важную роль во многих математических задачах. Примером может служить следующая известная
Задание о часовх. В тюрьме города N около каждой камеры можно посматривать часового. Находясь у одной из камер, часовый видит также, что проискодит в некоторых других, из которых к этой камере ведут коридоры. Каково наиболее число часовых, необходимое для наблюдения за всеми камерами?
Если шахматную доску рассматривать как тюрьму (да простят нам шахматные такую аналогию), причем ее поля считать камерами, а вертикали, горизонтали и диагонали — коридорами, то «часовые» естественнее всего назначить фигур, которые могут вести наgliedение в произвольном направлении.
Оказывается, 5 ферзей в полне способны справиться со всей шахматной «тюрьмой» (рис. 5). По существу мы определяли число внешней устойчивости для ферзей, равное 5 (не трудно показать, что четыерех часов не достигнуто). Доказано, что существуют 4860 способов, которые можно рассматривать
Рис. 5.
5 ферзей-часовых. Кстати, в нашем примере ферзи обладают еще одним интересным свойством: сами они друг другу не урезокают.
Из сказанного следует, что для того, чтобы появить одинокого ферзя противника (короли на доске отсутствует), достаточно иметь 5 ферзей. Однако известно, что в шашках 3damки справляются с одной (если та не стоит на «большой дороге»), хотя они не в состоянии держать одновременно все черные поля доски. Любопытно выяснить, нельзя ли появить вражеского ферзя при помощи менее чем пятей ферзей.
51
Если поставить на доску 9 ферзей, то хотя бы два из них оказывается на одной вертикали или горизонтали, то есть будут угрожать друг другу. Таким образом, число внутренней устойчивости для ферзей равно 8 (рис. 3, 4), а всего подходящих позиций — 92.
Особенно легко нашли задачи решаются для ладьи — наверное, проявляется ее прямолинейность. Ладей-часовых надо иметь
Рис. 6.
8, их достаточно расположить вдоль любой горизонтали или вертикали. Нетрудно также показать, что и число внутренней устойчивости для ладьи равно 8, а соответствующих расположений имеет 8! — число перестановок из 8 элементов *) (n!=1·2·····n). Позиция на рисунке 6 удовлетворяет общим требованиям.
Докажите, что если ладьи перенурованы, то есть отличаться друг от друга, то необходимо расположенный
*) См., например, статью Н. Я. Виленкина «Комбинаторика» («Квант» № 1, 1971).
имеется уже (8!)². На доске размером n×n эти числа соответственно равны n! и (n!)².
Слонов, чтобы справиться со всей доской, достаточно иметь столько же, сколько и ладей — 8 (рис. 7). Однако разместить слонов на доске так, чтобы они не угрожали друг другу, можно почтивое больше, чем ладей — 14 (рис. 8). Для доказательства расстояния диагонали, идущие вверх слева направо (на рисунке 8 они пунктные), всего таких диагоналей 15. На каждой из них может стать не более одного слона, так как слоны не должны угрожать друг другу. Следовательно, общее число слонов не превышает 15. Норовно 15 слонов также нельзя расставить: крайние из наших диагоналей составят из одного-единственного поля. Таким образом, искомое число не более 14. Однако из решения приведено на рисунке 8. Аналогичные расчужения показывают, что на доске размером n×n можно расставить не больше 2n — 2 слонов.
Докажите, что число допустимых расстановок слонов на произвольной
Рис. 7.
Рис. 8.
доске равно квадрату неокоторого числа.
Тепер перейдем к коням. Поставив 32 коня на один белые или один черные поля, мы найдем расположение, при котором они не угрожают друг другу. Покажем, что 32 — число внутренней устойчивости для коней. Для этого разобем доску на 8 равных прямогольников (рис. 9). Легко заметить, что конь, помещенный
Прямоугольник, нападаетровно на одно поле этого же прямоугольника, причем для любых двух таких коней поля, на которые они нападают, различны. Поскольку в каждом прямоугольнике 8 полей, то внутри него можно разместить самое большое 4 коня, не угрожающих друг другу, а общее число не превыходит . Доказите, что имеется лишь два упомянутых расположения — кони стоят только на белых или только на черных полях.
Число внешней устойчивости для коней равно 12 (рис. 10). Тепер разберемся с королями. Нетрудно проверить, что больше 16 королей, не стоящих рядом (то есть не угрожающих друг другу), расставить нельзя (рис. 11).
Число внешней устойчивости для королей
Рис. 9.
правно 9 (рис. 12). В каждом из 9 выделенных прямоугольников рисунка 12 имеет поле, которое может угрожать лишь король, стоящий на поле этого же прямоугольника. Следовательно, для того, чтобы все поля находились под угрозой, в каждом из 9 частей должны стоять хотя бы один король, искомуе число равно 9.
Рис. 11.
Рис. 12.
Очевидно, две пещки не могут одновременного угрожать друг другу. Однако если в вопросе 1 (стр. 50) слова «друг друга» заменить слова «хотя бы одна другой» и разрешить пещам становиться на первую горизонталь, то вопросы 1 и 2 станут корректными и для пещек. Ответом является число 32, причем расположение пещек на рис. 12.
Рис. 13.
сунке 13 удовлетворяет общим требованиям.
В результате наших исследований можно подвести итоги, заполнив таблицу (см. стр. 51).
Воспроизвести неодontaшие доказательства, найти число соответствующих расположений и сделать выводы из таблицы представляется вам самим. В качестве весы сервисных задач можно рекомендовать все расстретенные нами, но на доске размером *). Заметим, что некоторые из них весы сложны, а для других решения еще не найдены. Например, число внешней устойчивости для ферзей до сих пор неизвестно. Другими словами, не решена следующая.
Проблема. Каково наименьшее число ферзей, которые можно расставить на шахматной доске размером так, чтобы все ее свободные поля находились под угрозой?
*) Ряд таких задач расстран в книге А. М. Яглома и И. М. Яглома «Незlementарные задачи в элементарном изложении», М., Физматгиз, 1954.