|
|
 |
Условие
На бесконечной во все стороны шахматной доске выделено некоторое множество
клеток A. На всех клетках доски, кроме множества A, стоят короли. Все короли могут по команде одновременно сделать ход, заключающийся в том, что король либо остаётся на месте, либо занимает соседнее поле, то есть делает "ход короля". При этом он может занять и то поле, с которого сходит другой король, но в результате хода двум королям оказаться в одной клетке запрещается. Существует ли такое k и такой способ движения королей, что после k ходов вся доска будет заполнена королями? Рассмотрите варианты:
а) A есть множество всех клеток, у которых обе координаты кратны 100 (предполагается, что одна горизонтальная и одна вертикальная линии занумерованы всеми целыми числами от минус бесконечности до бесконечности и каждая клетка доски обозначается двумя числами – координатами по этим двум осям);
б) A есть множество всех клеток, каждая из которых бьётся хотя бы одним из 100 ферзей, расположенных каким-то фиксированным образом.
Решение
а) Предположим противное: пусть существует способ заполнения всей доски королями за k < 10n ходов. Рассмотрим квадрат K размера 10n+5×10n+5. В него могли попасть короли только из квадрата со стороной 10n+5 + 2k < 10n+5 + 2·10n. Но там королей меньше чем
(1 – 10–4)(10n+5 + 2·10n)2 = 102n+10·(1 – 10–4)(1 + 2·10–5)² < 102n+10·(1 – 10–4)(1 + 10–4) < 102n+10, то есть меньше чем клеток в K. Противоречие.
б) Рассмотрим горизонтальную линию клеток, на которой не стоит ни одного ферзя. Поскольку один ферзь бьёт ровно три клетки этой линии, все 100 ферзей бьют не более 300 клеток. За один ход можно уменьшить это число на 2: все короли, стоящие левее самой левой "битой" клетки двигаются на один шаг вправо, а все короли, стоящие правее самой правой "битой" клетки – на один шаг влево. Такие ходы можно одновременно делать во всех горизонтальных линиях без ферзей (когда в линии остаётся только одна битая клетка, то двигаются только короли слева от неё). Действуя таким образом, за 150 ходов короли полностью займут все горизонтальные линии, кроме тех, на которых стоят ферзи. Эти линии можно занять за 50 (или менее) ходов, передвигая королей по вертикали, – опять за один ход мы можем уменьшать число незаполненных линий на 2.
Ответ
а) Не существует; б) существует.
Замечания
1. Отметим, что полученная оценка числа ходов (200) не зависит от расположения ферзей.
2. Баллы: 9 + 5.
