Независимость и доминирование

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

1. Какое наибольшее число одноименных фигур (ферзей, ладей, слонов, коней или королей) можно расставить на доске так, чтобы никакие две из них не угрожали друг другу?

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

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

1. Множество вершин графа называется независимым, если никакие две из них не соединены между собой ребрами. Среди независимых множеств существует хотя бы одно максимально независимое, содержащее максимальное число вершин. Это число вершин называется числом независимости для данного графа (или числом его внутренней устойчивости).

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

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

Такой простой связью между графами и задачами на шахматной доске и объясняется популярность шахматных терминов и задач в литературе по теории графов. Важно отметить, что многие задачи о графах, весьма сложные в общем случае; удается решить для графов шахматных фигур. Примерами служат задачи о независимости и доминировании, которыми мы сейчас и займемся, рассматривая попутно и ряд других вопросов и обобщений, в том числе для доски nґn. Обозначим через N число независимости, а через D число доминирования. В скобках будет указываться фигура, о которой идет речь, а индекс обозначает размер доски. Так, D_n(Л) — это число доминирования для ладей на доске nґn.

Результаты наших исследований будем заносить в табл. 1 (см. стр. 74), знаки вопроса означают, что соответствующие числа нам неизвестны. После каждой строки с числами N и D а таблице идет строка с числом расстановок на доске, т.е. расстановок, в которых участвует, соответственно, N независимых или D доминирующих фигур.

1. Конь. С независимостью коней имеется полная ясность. Очевидно, расставляя 32 коня на полях одного цвета (рис. 61), мы получим два независимых множества. Убедимся, что больше 32 коней расставить невозможно. Пусть мирные кони каким-то образом расположены на доске. Рассмотрим произвольный замкнутый маршрут коня по этой доске. В этом маршруте после каждого поля, занятого конем нашей расстановки, должно следовать свободное поле. Значит, кони не могут занимать более половины доски. Если же половина доски заполнена конями, то они должны следовать в маршруте через одно поле и, значит, располагаться на полях одного цвета.

Рис. 61. 32 мирных коня.

Итак, мы не только доказали, что N₈(К)=32, но и обнаружили существование двух независимых расстановок — кони могут стоять только на белых или только на черных полях. Никаких других фигур, не угрожающих друг другу, в таком большом количестве, расставить нельзя, и поэтому коней по праву можно считать самыми мирными жителями шахматной семьи.

Совершенно аналогично доказывается, что N_n(К)=n²/2, если n четно, и N_n(К)=(n²+1)/2, если n нечетно. В первом случае вновь имеются две (одноцветные) расстановки, а во втором — только одна (кони стоят на полях того цвета, которого на доске больше).

Для доминирования на обычной доске достаточно иметь 12 коней (рис. 62). В общем случае эта задача для коней не решена.

Рис. 62. Двенадцать коней-часовых.

2. Ладья. Все интересующие нас. результаты для ладьи получены в третьей главе: N_n(Л)=D_n(Л)=n, число расстановок равно, соответственно, n! и 2nⁿ-n! На шахматной доске имеем 8! расстановок восьми независимых ладей и 2·8⁸-8! расстановок восьми доминирующих ладей.

3. Ферзь. Рассмотрим числа независимости N_n(Ф). Как мы знаем (см. четвертую главу), N₂(Ф)=1, N₃(Ф)=2, N_n(Ф)=n (n № 2; 3). Число соответствующих расстановок известно только для n Ј 14. На обычной доске можно расставить восемь независимых ферзей 92-мя различными способами.

Число доминирования для ферзей на обычной доске, как, впрочем, и на досках 9ґ9, 10ґ10 и 11ґ11, равно пяти (см. рис. 38). Существует 4860 расстановок пяти ферзей-часовых на доске 8ґ8. В общем случае формула для числа nґn неизвестна (в четвертой главе указаны некоторые верхние и нижние оценки для него).

4. Король. Задачи о независимости и доминировании для королей мы фактически обсуждали в пятой главе. Наибольшее число независимых королей на доске nґn равно k², где n=2k или n=2k-1. На доске 8ґ8 существует 281571 расстановка; формула для доски nґn не найдена. Минимальное число доминирующих королей на обычной доске равно 9, в общем случае формула указана выше. Число расстановок доминирующих королей не подсчитано даже для обычной доски.

5. Слон. В предыдущей главе доказано, что N_n(С)=2n-2 (n > 1) и, в частности, на обычной доске можно расставить 14 независимых слонов. Число расстановок равно 2ⁿ.

Далее, мы знаем, что D_n(С)=n, и на доске 8ґ8 доминируют 8 слонов. Хотя формула для числа расстановок n слонов, доминирующих на доске nґn, имеет довольно громоздкий вид, приведем ее. Число расстановок слонов равно [(2k-1)!(4k²+k)]² при n=4k; [(2k)!(4k²+5k+2)]² при n=4k+2 и, наконец, 2(k!)²(k+2) при n=2k-1 (k > 0).

Интересно, что при четных n число различных расстановок 2n-2 независимых слонов, как и число различных расстановок n доминирующих слонов, представляет собой полный квадрат. В частности, на обычной доске имеем, соответственно, 2⁸=(2·4)²=16²=256 расстановок мирных слонов и [(2·2-1)!(4·2²+2)]²=108²=11664 расстановок слонов-часовых. Понятно, в чем здесь дело. Белопольные и чернопольные слоны можно расставлять отдельно друг от друга. При этом, если доска четная, число расстановок белопольных слонов, обладающих -некоторым свойством (независимости или доминирования), равно числу расстановок чернопольных слонов, обладающих тем же свойством. Пусть это число равно t. Комбинируя каждую из расстановок белопольных слонов с каждой из расстановок чернопольных слонов, всего получаем t² расстановок слонов, обладающих выбранным свойством.

Итак, насколько нам удалось, мы заполнили табл. 1. Так как числа независимости и доминирования на обычной доске найдены для всех фигур, то мы решили обе проблемы, упомянутые выше. Нами указано также, сколько существует расстановок наибольшего числа независимых фигур на доске 8ґ8; что касается доминирования, то здесь еще остались нерешенными два вопроса.

Таблица 1

N; D	Конь	Ладья	Ферзь	Король	Слон
Число независимости для доски 8?8 (N8)	32	8	8	16	14
Число расстановок	2	40320	92	281571	256
Число независимости для доски n?n (Nn)	n2/2, при четных n, (n2+1)/2, при нечетных n	n	1, при n=1 и n=2, 2, при n=3, n, при n і 4	k2, где n=2k или n=2k-1	1, при n=1, 2n-2, при n і 2
Число расстановок	2, при четных n, 1, при нечетных n	n!	?	?	1, при n=1, 2n, при n і 2
Число доминирования для доски 8?8 (D8)	12	8	5	9	8
Число расстановок	?	2·88-8!	4860	?	20736
Число доминирования для доски n?n (Dn)	?	n	?	k2, где n=3k, n=3k-1 или n=3k-2	n
Число расстановок	?	2·nn-n!	?	?	см. стр. 73

Уникальной является позиция Дьюдени, изображенная на рис. 63. Здесь на доске одновременно уместилось рекордное число независимых ферзей — 8, ладей — 8 и слонов — 14. На доске находится также 21 мирный конь, и еще для одного рекорда не хватает 11 белых полей. При желании на свободные черные поля доски можно поставить восемь независимых королей.

Рис. 63. Рекорд Дьюдени.

Менее популярны задачи о доминировании и независимости пешек; мы предлагаем читателям исследовать их самостоятельно. Заметим, что, в отличие от фигур, для пешек можно рассматривать отдельно два случая — когда все они одного цвета, и когда на доску разрешается ставить и белые, и черные пешки.

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

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

Сколькими способами можно расставить p независимых фигур на деске nґn (p Ј N_n)?

В восьмой главе такая задача будет решена для двух ферзей (p=2); при увеличении p ее решение существенно усложняется.

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

При каком минимальном значении n можно уместить на доске nґn весь комплект белых и черных фигур (без пешек), чтобы фигуры разного цвета не били (уже по-настоящему!) друг друга?

Очевидно, на доске 4ґ4 шестнадцать шахматных фигур займут все ее поля и невольно войдут в соприкосновение. Однако на доске 5ґ5 искомые расстановки уже существуют (рис. 64), одна из них центрально-симметрична (рис. 64, а).

Рис. 64. Белые и черные не мешают друг другу.

В задачах о доминировании часто требуется, чтобы под обстрелом находились не только свободные поля доски, но и занятые фигурами. Мы уже приводили расстановку пяти ферзей-часовых, обладающих этим свойством. Восемь ладей, стоящих вдоль любой вертикали или горизонтали также нападают на все поля доски. Что касается других фигур, то для нападения на все поля доски их требуется несколько больше, чем для обычного доминирования. Коней и слонов надо иметь на два больше, а королей даже на три. Таким образом, 14 коней, 10 слонов или 12 королей в состоянии держать под обстрелом все 64 поля доски. Соответствующие расстановки приведены на рис. 65, а-в.

Рис. 65. Под охраной все поля доски.

Исследуем теперь доминирование различных наборов фигур, не обязательно одноименных. Пять ферзей справляются с шахматной доской (держат ее свободные поля под ударом), но меньшим числом фигур не обойтись. Любопытно, однако, что двух из пяти ферзей можно заменить более слабыми фигурами, — двумя ладьями или даже ладьей и слоном (рис. 66, а, б), причем в первой расстановке атакованы все 64 поля доски. Если мы хотим, чтобы ферзей сопровождал конь или король, то на доске придется оставить четыре ферзя (рис. 66, в, г, положение ферзей здесь одно и то же).

Рис. 66. Пять фигур-часовых.

Можно ли расставить на доске восемь фигур одного цвета, чтобы они держали под обстрелом все 64 поля доски?

Рис. 67. Доминирование на шахматной доске.

Как ни странно, комплект фигур доминирует на доске лишь в том случае, если слоны одноцветные (рис. 67, а). Если же слоны разного цвета, то одно поле всегда будет в безопасности. Доказано, что неатакованным может быть любое поле доски (на рис. 67, б — это поле c1) Если мы хотим, чтобы под охраной, как и раньше, находились только свободные поля доски, то хватает семи фигур из комплекта, одного слона можно просто снять (рис. 68).

Рис. 68. Семь фигур-часовых.

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

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

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

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

Иначе говоря, спрашивается, при какой раскраске доски фигуры, стоящие на полях одного цвета, не угрожают друг другу, т.е. являются независимыми. Меньше всего красок — две — требуется в случае коней. Собственно, здесь и раскрашивать нечего, годится обычная черно-белая доска. Двух красок хватает для раскраски любой доски nґn, а при n, равном 1 или 2, можно ограничиться и одной краской.

В случае слонов и ладей для раскраски обычной доски достаточно восьми красок (а для раскраски доски nґn — n красок). Каждую вертикаль доски, заполненной слонами, можно окрасить в свой цвет. Для ладей все поля первой горизонтали окрасим в разные цвета, а для раскраски последующих горизонталей используем циклический сдвиг красок. Другими словами, если краски занумеровать числами от 1 до 8 (для доски nґn — числами 1, 2, ..., n), то окраска первой горизонтали — 1, 2, ..., 8; второй — 2, 3, ..., 8, 1; третьей — 3, 4, ..., 8, 1, 2 и т.д.; восьмой — 8, 1, ..., 7.

Переходя к королям, заметим, что для них все четыре поля произвольного квадрата 2ґ2 должны быть окрашены в разные цвета. Четырех красок хватает и для любой доски nґn (при n=1 — одна краска). Левый нижний квадрат 2ґ2 можно произвольно раскрасить в четыре цвета, затем так же раскрасить соседние квадраты 2ґ2 и т.д., пока не будет раскрашена вся доска (если n не делится на 4, то, естественно, числа полей, окрашенных в разные цвета, могут несколько отличаться).

Рис. 69. Задача о раскраске доски.

На рис. 69 показана раскраска шахматной доски для ферзей (числа от 1 до 9 соответствуют девяти краскам). Действительно, здесь никакие два одинаковых числа не стоят на одной вертикали, горизонтали и диагонали. Восьми красок для раскраски доски с ферзями не хватает. Если предположить противное, то найдутся восемь расстановок восьми мирных ферзей, заполняющих в совокупности всю доску. Но такого набора расстановок не существует (см. стр. 49). В общем случае доказано, что любую доску nґn можно раскрасить в n+3 цвета так, чтобы ферзи, стоящие на полях одного цвета, не угрожали друг другу. Для некоторых n достаточно и меньшего числа красок: n+2, n+1 или n. Существует гипотеза, по которой хроматическое число графа ферзей при любом n і 3 равно либо n, либо n+1.

| Оглавление |