Задача о ферзях

22

М. Мамикон

Задача о ферзях

1. Постановка задачи
   На общий шахматной доске 8×8 пя ть ферзей можно расставить так, чтобы они были все поля доски. Четырех же ферзей для этого не достаточно (доказите!). Доска 3×3 будет одним ферзем, находящимся на центральной клетке. Для доски 6×6 дое ее поле. Значит, $F(11) \leq 5$. Из рисунка 2 можно усмотреть, что $F(10) \leq 5$ и $F(9) \leq 5$.

Найти точное $F(n)$ при больших $n$ довольно сложно. Далее совершенная быстроедующая вычислительная машина не может за разумное время перебрать все варянты расстановки, скажем, десяти ферзей на доске 20×20.

Позному представляется интересный найти хотя бы оценки — верхнюю и нижнюю — для $F(n)$. В этом и будет состоять наше постановка задачи о ферзях.

2. Оценка сизу
   Если на доске $n \times n$ расставить $n$ ферзей вдоль одной из главных диагоналей, а потом убрать два крайних ферзя, то оставшиеся $n-2$ ферзя тоже будут быть все поля доски. Значит,

$$F(n) \leq n-2.$$

Если при расстановке $F(n)$ ферзей, при которой каждое поле бито, на краю доски нет ни одного ферзя, то $4(n-1)$ краевых клеток, образляющих доски, должны быться ферзями изнутри этой рамки. Так как каждый ферзь будет в восмыни направлениях, то он будетровно 8 клеток этой рамки. Если бы даже все ферзи были разные клетки рамки, то необходимо было бы иметь $$\frac{4(n-1)}{8} = \frac{n-1}{2}$$

Рис. 1.

достаочно трех ферзей (рис. 1), двух мало.

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

| $n$ | 3 | 4 | 5 | 6 | 7 | 8 |
| :— | :— | :— | :— | :— | :— | :— |
| $F(n)$ | 1 | 2 | 3 | 3 | 4 | 5 |

На рисунке 2 изображена доска $11 \times 11$ и 5 ферзей на ней, быющие каж-

23

$$\frac{1}{2}n - \frac{1}{2} \text{ферзей. Итак, в этом случае}$$
$$F(n) \geq \frac{1}{2}n - \frac{1}{2}. \quad (2)$$

Оценка (2) верна и в обшем случае. Доказите ее. (Указание. Из (1) вытекает, что при любой расстановке $F(n)$ферзей на доске остатуса, по крайней мере, две свободные отферзей вертикали и две свободные горизонтали.)

Из (2) $F(11) \geq 5$. В п. 1 мы указывали, что $F(11) \leq 5$. Значит, $F(11) = 5$. Аналогично получается $F(10) = 5$. Любопытно, что равенство $F(9) = 5$ таким путем не получается. Доказите его самостояльно!

Рис. 3.

Рис. 4. $k = 3, l = 1$.

Займется теперь улучшением верхней оценки (1).

3. $\langle k, l \rangle = \text{решетка}$
   Рассставимферзей на бесконечной шахматной доске левым ходом $\langle k, l \rangle$-коня (объичный шахматный конь—это $\langle 2, 1 \rangle$-конь), а именно: поставим сначалаферзя на произвольную клетку; затем поставим еще четырехферзей так, как показано на рисунке 3; с каждым из поставленныхферзей поступим таким же образом, и т. д. Полученную расстановку бесконечного числаферзей называемферзой $\langle k, l \rangle$-решеткой. Каждая $\langle k, l \rangle$-решетка является квадратной решеткой, повернуть относительно шахматной доски (рис. 4).

Двигаясь вдоль ряда $^*$), мы периодически будем встречатьферзей. Обозначим длину перiodа решетки по ряду через $W_p$. Например, для $\langle 3, 1 \rangle$-решетки $W_p = 10$ (рис. 4).

Двигаясь вдоль диагонали, мы также будем встречатьферзей периодически. Обозначим длину перiodа решетки по диагонали через $W_\partial$. Для $\langle 3, 1 \rangle$-решетки $W_\partial = 5$ (рис. 4).

Уражнения

1. Для $\langle k, l \rangle$-решетки $W_p = \frac{k^2 + l^2}{d}$, где $d$ — наиболее общий делитель чисел $k$ и $l$.

2. Для $\langle k, l \rangle$-решетки $W_\partial = \frac{k^2 + l^2}{c}$, где $c$ — наиболее общий делитель чисел $k + l$ и $k - l$.

3. Если $k$ и $l$ — взаимно простые числа разной четности, то $W_p = W_\partial = k^2 + l^2$.

4. Перiodы $W' \langle tk, tl \rangle$-решетки и перiodы $W \langle k, l \rangle$-решетки связаны соотношениями $W_p = tW_p$ и $W_\partial = tW_\partial$.

5. Фундаментальная расстановкаферзей
   Пусть $k$ и $l$ — взаимно простые числа разной четности. Расмотрим $\langle k, l \rangle$-решетку. Для нее оба перiodа $W_p, W_\partial$ равны $W_0 = k^2 + l^2$ (упражнение 3).

Вырежем из нашей бесконечной доски квадратную доску $W_0 \times W_0$ так, чтобы ферзь попал в централь-

$^*)$ Ряд—это вертикаль или горизонталь.

25

Докажем, что битые клетки симметрины относительно любой главной диагонали.

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

Из того, что при симметрином относительной главной диагонали и повороте на 90° битые клетки переходят в битые, легко следует симметримножества битых клеток относительно центральной вертикали и центральной горизонтали (почему?).

Значит, с точки зрения битых-небитых клеток все восемь октантов, на которые доска делится центральными рядами и главными диагоналими, равноправны (на рисунке 7 один из таких октантов обозначен буквой O).

6. Дополнительные ферзи

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

Число нечетных диагоналей одного направления на все доске без главной диагонали и угловых «одноклеточных» диагоналей (бьющихся центральным ферзем) равно 2 ($W_0-1$); по одному сторону от главной диагонали их будет $W_0-1$, а в одном октанте — еще в два раза меньше: $\frac{W_0-1}{2}$.

Это число совпадает с числом ферзей Fundamentalной расстановки, находящся по одному сторону от главной диагонали выделенного направления. Каждый ферзь из заштрихованной на рисунке 7 положит на одной из нечетных диагоналей, проходящих через октант $O$. Поэтому среди нечетных диагоналей октаента «пустых» диагоналей (на которых нет ферзей), оченьindo, столько, сколько ферзей в угловом треугольнике $T$. Обозначим это число через $\varphi(n)$.

Рассмотрим одну из пустых диагоналей октаента $O$. Дополнитель ее до симметричной крестообразной фигуры (рис. 8). В силу симметриных клеток на остальных трех диагоналях этой фигуры тоже нет ферзей. Чтобы побить клетки этой фигуры, достаточно расположить два дополнительных ферзя в симметричных клетках $A$ и $B$ центральной горизонтали (рис. 8).

Поскольку в одном октанте число пустых диагоналей равно $\varphi(n)$, то всего достаточно расставить $2\varphi(n)$ дополнительных ферзей.

26

Рис. 9. $k = 3, l = 2$.

Итак,
$$F(n) \leqslant W_0 + 2\varphi(n).$$

7. Ферзи и площади

Чтобы оценить сверху число $\varphi(n)$ ферзей в угловом треугольнике $T$ (рис. 7), вспомним, что ферзи функциональный расстояний расположены в узлах решетки со стороны длины $\sqrt{(2k)^2 + (2l)^2} = 2\sqrt{k^2 + l^2}$ (длина клетки доски принята за единицу), повернуть относительно шахматной доски (рис. 4, 6).

Сдвинем эту решетку так, чтобы ферзи оказались в центрах квадратов (рис. 9). Тогда число ферзей в треугольнике $T$ не будет превосходить числа «сдвинутых квадратов», центры которых лежат в $T$. Поскольку каждой такой квадрат целиком лежит в $\frac{d}{2}$-окрестности треугольника $T$ (рис. 10; $d$ — длина диагонали квадрата), их число не превосходит относительно площади этой окрестности к площади квадрата.

Упражнение 5. $\varepsilon$-окрестность плоской фигуры $F$ называется объединение кругов радиуса $e$ с центрами в каждой точке фигуры $F$. Доказите, что площад $\varepsilon$-окрестности выпуклого многоугольника равна $S + P\varepsilon + \pi e^2$, где $S$ — площад многоугольника, $P$ — его перimetр.

Длина кататов треугольника $T$ равна $\frac{n}{2}$. Сторона квадрата, из которого построена решетка, равна $2\sqrt{k^2 + l^2} = 2\sqrt{\frac{n-1}{2}} = \sqrt{2}\sqrt{n-1}$.

Значит, искомое отношение площад равно
$$\frac{n^2}{8} + \left(1 + \frac{\sqrt{2}}{2}\right)n\sqrt{n-1} + \pi(n-1) \over 2(n-1)$$.

Поскольку $W_0 = k^2 + l^2 = \frac{n-1}{2}$, из (3)
$$F(n) \leqslant \frac{5}{8}n + \left(1 + \frac{\sqrt{2}}{2}\right)\frac{n}{\sqrt{n-1}} + \frac{1}{8(n-1)} + \pi - \frac{3}{8}.$$

Ввиду того, что $\frac{n}{\sqrt{n-1}} < 2\sqrt{n}$ и $\frac{1}{8(n-1)} < 1$, при $n \geqslant 2$, а $1 + \frac{\sqrt{2}}{2} < 2$, получаем для досок со стороны в $2(k^2 + l^2) + 1$ клеток, где $k$ и $l$ — взаимно простые числа разной четности, окончательную оценку сверху:
$$F(n) \leqslant \frac{5}{8}n + 4\sqrt{n} + 5.$$

8. Произвольные доски

Пусть теперь у нас есть доска $n \times n$, где $n \geqslant 11$. Возьмем такое натуральное $m$, что $8m^2 + 3 \leqslant n < 8(m+1)^2 + 3$. Поскольку $n \geqslant 11$, такое $m$ найдется. Заметим, что $8m^2 + 3 = 2[(2m)^2 + 1^2] + 1 = 2(k^2 + l^2) + 1$, где $k = 2m, l = 1$.