М1153. Задача о наибольшем числе поворотов замкнутого маршрута шахматной ладьи

Задача из журнала «Квант» ( 1989 год, №3).

Какое наибольшее число поворотов может содержать замкнутый маршрут ладьи, обходящей по одному разу все клетки шахматной доски $ 8 \times 8 $ клеток?

Решение

Ответ: $56$ поворотов. Маршрут с $56$ поворотами показан на рисунке 1.

Центрируем изображение
Рис.1

Докажем, что это число нельзя превысить.

Доказательство

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

Центрируем изображение
Рис.2

Разобьем доску на $4$ квадрата $4 \times 4$. В каждом из них есть коридор, соседний с угловой клеткой. Покажем, что кроме него есть еще хотя бы один коридор. Рассмотрим, например, левый нижний квадрат (рис.3) и допустим, что клетка $a2$ — коридор.

Центрируем изображение
Рис.3

Предположим, что других коридоров в этом квадрате нет. Тогда, очевидно, что маршрут будет последовательно проходить по клеткам $b2$, $b1$, $a1$, $a2$, $a3$, $b3$, $b4$. Следующей будет клетка $а4$, иначе мы в нее никогда не попадем (или маршрут не замкнется). Теперь можно аналогично продолжить маршрут в другую сторону $b2$, $c2$, $c1$, $d1$, $d2$, $e2$. Из полученного рисунка видно, что маршрут должен содержать участок $d3$, $c3$, $c4$, следовательно одна из клеток — $d3$ или $с4$ — коридор (это доказывается также, как для угловых клеток — см. начало решения).

Итак, число коридоров не меньше $ 2 \times 4 = 8 $, а число поворотов — не больше $ 64 — 8 = 56 $.

М.Г.Хованов

М1736. Шахматные кони

Задача из журнала «Квант» (2000 год, 4 выпуск)

Условие

Какое наибольшее число коней можно расставить на доске $5\times5$ так, чтобы каждый из них бил ровно двух других?

Решение

Рисунок 1

На рисунке $1$ приведено расположение $16$ коней, удовлетворяющее условию задачи. Покажем, что большее число коней расставить нельзя. Заметим, что количество коней, расположенных на черных клетках, равно количеству коней, расположенных на белых клетках. Значит, если число пустых белых клеток равно $n$, то число пустых черных клеток равно $n+1$.

Рисунок 2

Заметим, что для оптимального расположения коней центральная клетка пуста, так как в противном случае из восьми клеток, которые бьет конь, стоящий на центральном поле, ровно шесть пустых белых. Отсюда $n\geqslant6$, и число коней не превосходит $25-n-(n+1)\leqslant12$.

Рисунок 3

Разобьем белые клетки на четыре группы так, как показано на рисунке $2$ (клетки одной группы отмечены одинаковыми цифрами). Покажем, что для оптимального расположения по крайней мере одна клетка каждой группы пуста, отсюда будет следовать, что $n\geqslant4$ . Предположим противное: например, что на всех клетках группы $3$ стоят кони. Обозначим их буквами $a$, $b$ и $с$ (рис.3). Конь, стоящий на клетке $а$, бьет клетки $f$, $d$ и центральную. Но, как было показано выше, центральная клетка пуста, значит, на клетках $f$ и $d$ стоят кони.

Аналогично можно показать, что на клетках $e$ и $g$ тоже стоят кони. Но тогда конь, стоящий на клетке $c$, бьет четырех коней, расположенных на $d$, $e$, $f$ и $g$, что противоречит условию.

Итак, число пустых белых клеток $n\geqslant4$. Значит, число коней не больше

$25-n-(n+1)\leqslant12$.

Ответ: $16$.

М. Горелов