Задача о доминировании ферзей

60

Задача о домашировании ферзей

В. Г. ЧВАНОВ

В статье М. Мамикона в «Кванте» 1977 г., № 12 рассматривалась следующая задача:

Задача о домашировании. Какое минимальное число ферзей $F(n)$ можно размещать на шахматной доске $n \times n$ так, чтобы они атаковали все ее свободные поля?

Числа $F(n)$ известны лишь для малых $n (n \leq 11)$, приведенных в таблице 1.

Таблица 1

| $n$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | … |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| $F(n)$ | 1 | 2 | 3 | 3 | 4 | 5 | 5 | 5 | 5 | ? | … |

На рисунке 1 приведены размещения ферзей на доски $3 \times 3$, $8 \times 8$, $11 \times 11$, для которых $F(n)$ равны соответственно 1, 5 и 5. Для больших $n$ задачажет своего решения.

В статье М. Мамикона приводятся следующие оценки для $F(n)$:

$$F(n) \geq \frac{n-1}{2},$$

$$F(n) \leq \frac{5}{8} n + 16 \sqrt{n}.$$

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

Первая геометрическая идея — пробивание каймы

Размещение ферзей на доске $n \times n$, для которых $F(n) = (n-1)/2$ (реализуется нижняя оценка М. Мамикона), называемым идеальным.

Примерми могут служить размещения, показанные на рисунке 1 (при $n=3$ и $n=11$).

После применения из 4 $(n-1)$ клеток, расположенных вдоль ее края. При идеальном размещении (см. рис. 1a, 6) каждый ферзь будетровно 8 клеток на каждой из таких клеток ее клетка не пробивается двумя ферзями, поэтому число ферзей равно 4 $(n-1):8=(n-1)/2$, откуда и получается нижняя оценка (1). Полное доказательство данного в статье М. Мамикона.

Задача 1 (нерешенная). Существуют ли идеальные размещения кроме двух указанных? Конечно ли число идеальных размещений? (Гиотеза: ответ на последний вопрос — положительный.)

Необходимым условием домаширования, размещется, является домашрование на кайме. Поэтому интересно знать, для каких досок возможно домашрование на кайме $(n-1)/2$ ферзями. М. Мамикон доказал, что таких досками являются доски $n \times n$ при $n=2(k^2+l^2)+1$, где $k$ и $l$ — взаимно-простые числа разной четности. Но этим списком также доски не исчерпывают. Примером может служить размещение на рисунке 2 $(n=15)$; еще одно такое размещение я придумал для доски $n \times n$, $n=27$. Эти размещения применяются тем, что в них соблюдается численное равенство ферзур, расположенных лишь в противоположных квадратах, образованных пересечением главных диагоналей.

61

Вторая геометрическая идея — вывести $k$-ферзя за пределы центрального квадрата

Рассмотрим $k$-ферзя на рисунке 4,6 и заменим четыре угловых ферзя на два ферзя, лежащие за пределами центрального квадрата $m \times m$ ($m=5$), как показано на рисунке 5. Тогда мы получим $k$-ферзя из $2m-1$ фигур, доминирующего на доске $3m \times 3m$. Дальнейшее сокращение числа фигур невозможно, так как в квадрате $m \times m$ имеется $2m-1$ диагонали.

Однако, когда мы выносим фигуры по своим диагоналям за пределы центрального квадрата, оказывается, что можно получить $k$-ферзя, доминирующий на доске большого размера, чем $3m \times 3m$, за счет увеличения числа атакуемых горизонталей и вертикалей (см. рисунок на четвертой странице обложки). Естественно спросят.

Задача 4. Каков максимальный размер квадрата, на котором доминирует $k$-ферзя из $2m-1$ фигур?

Я не знаю ответа на этот вопрос, однако с другой серии $k$-ферзей указаны примером, которые позволяют замерно улучшить оценку сверху для $F(n)$. В частности, для любого $m$ из серии $m=12c+9$ ($c=0,1,2,...$) можно построить $k$-ферзя из $2m-1$ фигур, который доминирует на доске $n \times n$, где $n=42c+31=(7m-1)/2$. Таким образом, для всех $n$ из серии $n=42c+31$ ($c=0,1,2,...$), мы получаем оценку

$$F(n) \leq \frac{4n-5}{7}.$$

Заметим, что число вертикалей (а также горизонталей), а также таких $k$-ферзем, равно $l=(3m-1)/2$.

$k$-ферзь, изображенный на обложке, и есть один из $k$-ферзей этой серии (при $c=0$). Рассмотрим его подробнее. Он состоит из 3-х, обладающих определенными «конструтивными» достоинствами, группы фигур. Каждая, взятая отдельно, группа атакует во всех направлениях столбко рядов, сколько содержится в ней фигур. Причем, в вертикальном и одном из диа-

62

гональных направлений ряды атакованы без разрывов, в другом — атакован каждой третий ряд, в горизонтальном — каждой второй. Крайние группы содержат $\frac{2}{3}m-1$, а средняя — по $\frac{2}{3}m$ фигур, размещенных последовательным ходом коня вдоль параллельных линий 1-1, 2-2, 3-3. Линия 1-1 проходит через центральную клетку доски. Расстояния между линиями 2-2, 3-3 и линии 1-1 выбирается так, чтобы за пределами доски $m \times m$ с 2-х ее сторон (см. рисунок на обложке) находилось по $\frac{m-1}{4}$ фигур каждой крайней группы. Но при этом часть фигур каждой группы выходит из синей зоны и в ней образуется разрыв (показано зеленьм) в сплошном диагональном проюе. Фигуры, вышедшие из синей зоны, возвращают в нее параллельным переносом по своим диагональным так, чтобы ликидировать образованшийся разрыв.

Улучшение нижней оценки для $F(n)$

Тепер вернемся к нижней оценке $F(n)$. Ее можно улучшить, размещенной оценкой $F(n)$ для досок $n \times n$, сравнимых по модулю 4.

Заддача 5. Докажите для каждой вида досок $n \times n$ выполяемость следующих оценок $F(n)$:

$$n = 4k \quad F(n) \geq \frac{n}{2},$$

(4)

Указание. Число полей краевой каймы доски, на которой доминируют $\frac{n-1}{2}$ ферзей, кратно 8; число фигур идеальной расстановки $F(n) = 2k+1$.

Заддача 6. Дано по $\frac{n-1}{2}$ вертикальных, горизонтальных, восходящих и низходящих диагональных линий. Укажите все значения $n$, для которых возможно эти линиями (они идут через центры клеток) зачеркнуть все клетки доски $n \times n$.

Заддача 7 (нерешенная). Конечно ли число досок, для которых выполняются оценки (4), (5), (6)? Гипотеза: число таких досок конечно.

Оценки (4), (5), (6) позволяют нам расширить таблицу 1. Действительно, с их учетом можно записать, что $F(12) \geq 6$; $F(13) \geq 7$; $F(17) \geq 9$; $F(12)=6$ и $F(13)=7$ легко получить, доставвая размещения $F(11)=5$ (рис. 1 «6») до размеров $12 \times 12$ и $13 \times 13$ с установкой дополнительной фигуры в угловой клетке доски. Размещение же $F(17)=9$ показано на рисунке 6.

«Качество» того или иного доминиующего размещения удобно оценить относением $\mu = \frac{F(n)}{n}$. Итак, наши результаты можно представить в виде таблицы 2.

Таблица 2 заслуживает выполнения, но ее анализ мы оставляем читателем. Отметим лишь следующие о том, что доска $8 \times 8$ является наиболее suitableми и формальными для размещения $F(n)$ позволяющим нам ответить на этот вопрос пока утвердилено.

Заддача 8 (о внешнем доминировании). Какое максимальное число ферзей можно размещить на бесконечной шахматной доске так, чтобы атаковали все доски $n \times n$?