Клетчатые задачи → .02 Разбиение доски на части

Приведем пример. Паша мог расставить ладьи так:

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

Разобьем доску на 9 квадратов Заметим, что ни в одном таком квадрате не может оказаться две закрашенных клетки, потому что они заведомо граничат друг с другом. Отсюда следует, что в каждом из квадратов их не больше одной, тогда всего их не больше Пример на в первой, третьей и пятой строках закрасим первую, третью и пятую клетки.

Заметим, что каждый король, снятый с доски, мог бить не более из оставшихся (иначе и некоторые из оставшихся били бы друг друга). Поэтому число оставшихся королей не может превосходить число снятых более чем в раза, то есть не может быть больше Пример приведён на рисунке: серым обозначены короли, которых необходимо убрать.

Мы покажем, что (i) если то любая хорошая расстановка содержат пустой квадрат но (ii) если то существует хорошая расстановка, которая его не содержит.

(i). Предположим, что Рассмотрим произвольную хорошую счастливую расстановку. Существует ряд в крайнем левом поле которого стоит ладья. Рассмотрим последовательных строк, одной из которых является Их объединение содержит ровно ладей.Теперь удалите крайние левые столбцы из (таким образом будет удалена хотя бы одна ладья). Оставшаяся часть представляет собой прямоугольник поэтому его можно разбить на квадраты размером и эта часть содержит не более ладьи. Таким образом, один из этих квадратов пуст.

(ii). Теперь предположим, что Сначала мы построим хорошую расстановку без пустого квадрата для случая После этого мы изменим его, чтобы он работал при меньших значениях

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

Далее, мы покажем, что в каждом квадрате на доске есть ладья. Рассмотрим такой квадрат и рассмотрим последовательных строк, объединение которых содержит Пусть самая нижняя из этих строк имеет номер с (обратите внимание, что ). Тогда ладьи в этом союзе расставляются по столбцам с номерами

или, расположив эти числа в порядке возрастания,

Легко проверить, что первое число в этом списке не превосходит (если то а первое число в списке — ), последнее не превышает а разница между любыми двумя последовательными числами не превышает Таким образом, один из последовательных столбцов, пересекающих содержит число, указанное выше, и ладья в этом столбце находится внутри что и требовалось. Конструкция для установлена.

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

Покажем, что ладей достаточно. Для этого заметим, что на каждую строку хватит одной ладьи: можно поставить её в клетку строки с минимальным номером, а затем обойти все клетки строки в порядке возрастания номеров.

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

Наконец, поскольку на каждой клетке диагонали должна побывать ладья, Пете придётся использовать не менее ладей.

Оценка. Из каждого мамонта выпустим три стрелки в тех направлениях, в которых он бьёт. Сопоставим стрелку диагонали (не обязательно главной), если мамонт, из которого ведёт стрелка, стоит в этой диагонали, а стрелка идёт вдоль неё. Тогда каждой диагонали сопоставлено не более двух стрелок: в противном случае две из них будут идти в одном направлении, и один из мамонтов будет бить другого. Поскольку диагоналей всего (по в каждом направлении), стрелок им сопоставлено не более а значит, всего мамонтов не больше

Пример. Три возможных примера расположения мамонтов, не бьющих друг друга, показаны на рисунке.

Ладья бьёт всего клеток — в своей вертикали и своей горизонтали. Рассмотрим другую клетку C в этой горизонтали. Её бьёт еще ровно одна ладья находящаяся с ней в одной вертикали. Эта же ладья бьёт одну клетку находящуюся с в одной вертикали. — угловые клетки клетчатого прямоугольника. Если этот прямоугольник — квадрат, ладьям и достанется по половине от клеток и Если же он — не квадрат, то одна из клеток и достанется ладье а другая — ладье Отсюда ясно, что ладье всего достанется клеток: та, на которой она стоит, и половина от оставшихся клеток. То же верно для каждой ладьи.

Клетки, не лежащие на краю доски образуют квадрат Разобьем его на квадраты В каждом из них стоит не более одного короля, то есть всего королей во внутренних клетках доски — не более Поэтому на краю доски стоят не менее королей. Теперь разобьем на квадраты всю доску и поставим по королю в левую верхнюю клетку каждого из них. Получим королей, не бьющих друг друга, из которых на краю стоят ровно

Предположим, что на поле можно разместить фигуры при , тогда можно разместить и при . Разобьём поле на 16 квадратов , тогда ровно в 12 из них будут стоять по 1 королю («к»), а в 4 других - 12 коней-лошадей («л») и 1 мяч, т.е. 13 фигур, значит, пустых квадратов быть не должно. Соответственно, квадраты будем называть к-квадраты и л-квадраты. Заметим, что если хотя бы в одном из л-квадратов две «л» стоят у общей стороны с другим квадратом, то этот соседний квадрат не будет содержать «к», значит, он должен быть л-квадратом, но тогда в сумме в этих двух квадратах разместится не более 4 фигур, т.к. клетки прямоугольника разбиваются на пары в виде хода «л», а во всех 4 л-квадратах разместится не более фигур, а должно быть 13. Кроме того, не существует л-квадратов с 4 «л» (аналогичные рассуждения). Значит, в каждом л-квадрате будет ровно 3 «л» и никакие 2 «л» не могут стоять парой у общей стороны с другим квадратом, следовательно, такие л-квадраты находятся в углах поля и 3 «л» стоят с краю всего поля, причём в одном из них ещё стоит и мяч.

Тогда из двух выделенных на поле квадратов хотя бы один должен оказаться пустым противоречие. Значит, .

Для уже можно построить пример. Отметим слоном мяч и поставим королей и коней.

Заметим, что на шахматной доске имеется диагоналей, содержащих нечётное число клеток и не имеющих общих клеток. Следовательно, число фишек не может быть больше Удовлетворяющая условию задачи расстановка фишек изображена на рисунке.

Ясно, что когда Дед Мороз красит 3-ю клетку (после этого хода 3 красные и 2 синие), Снегурочка закрасила только 2 клетки, а, значит, не могла выиграть. Покажем, что Дед Мороз может гарантировать себе победу.

Выделим внутри квадрат и будет работать в нём. Пусть первым ходом Дед Мороз красит центр одного из таких квадратов (ясно, что со всех четырёх сторон от этой клетки он может закрасить ещё хотя бы 2 клетки). Пусть далее Снегурочка красит одну из клеток доски. Если эта синия клетка в одном столбце с красной, то в строке с красной клеткой нет синих. Если эта синия клетка в одной строке с красной, то в столбце с красной клеткой нет синих. Иначе в строке с красной клеткой нет синих.

Пусть в строке нет синих. Дед Мороз покрасит любую соседнюю со своей красной. Далее есть 2 клетки(соседние с получившимся прямоугольником 1 на 2), покрасив любую из которых, Дед Мороз выиграет. Ясно, что за один ход Снегурочка покрасит не более одной из них, и следующим ходом Дед Мороз выигрывает (по сказаному ранее Снегурочка к этому моменту ещё не выиграет). Случай, если нет синих клеток в столбце с красной разбирается аналогично.