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

Обозначим через ответ в задаче; положим Докажем сначала, что

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

Мысленно отметим все клетки строки Ясно, что любую клетку по-прежнему можно отметить. Удалим из клетчатой плоскости строку и сдвинем вместе две получившиеся полуплоскости так, чтобы снова получилась клетчатая плоскость. Теперь мы можем отметить любую клетку этой новой плоскости, отмечая на каждом шагу клетку, в кресте которой уже есть не менее отмеченных клеток (поскольку из этого креста удалена одна клетка строки ). Следовательно, изначально на этой плоскости должно было быть отмечено не менее клеток. Значит, на исходной плоскости сначала должно быть хотя бы отмеченных клеток не из ; отсюда и следует

Поскольку из доказанного неравенства (*) следует, что

Осталось показать, как отметить клеток так, чтобы затем можно было отметить любую другую клетку плоскости. Покажем по индукции, что подходит пример, показанный на рисунке, состоящий из двух «лесенок» высот и ; нетрудно понять, что в нём как раз клеток. При утверждение очевидно: при одной отмеченной клетке можно отметить любую клетку в её кресте, а затем и любую клетку вообще.

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

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

Пример. Разобьем доску на два квадрата и покрасим все клетки каждого квадрата в один цвет. В этом примере можно вырезать только разноцветных доминошек.

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

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

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

______________________________________________________________________________________________________________________________________________________

Пример. Существует много оптимальных расстановок, Например, достаточно занять кузнечиками вертикальных ряда, как показано на рисунке:

В каждой горизонтали стоит два кузнечика, поэтому суммарное число кузнечиков равно как раз

Разобьём доску на квадратов Покажем, что в каждом квадрате может стоять не более гепардов, не бьющих друг друга — отсюда будет следовать, что общее число гепардов не может превосходить

Рассмотрим произвольный квадрат размера и произвольного гепарда в нём. Гепард бьёт все клетки квадрата, кроме клеток, лежащих с ним в одной строке или в одном столбце. Если один из остальных гепардов в квадрате стоит в одной строке с а ещё один, — в одном столбце с то и стоят в разных строках и столбцах и, следовательно, бьют друг друга; это невозможно. В противном случае, без ограничения общности, все гепарды в квадрате стоят в одной строке с то есть их не больше

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

Разделим таблицу на 12 прямоугольников и еще одну клетку.

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

_________________________________________________________________________________________________________________________________________________________________________________

Отметим центральный крест без середины.

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

Разобьем квадрат на прямоугольника Так как вырезанных клеток то из одного такого прямоугольника вырезано не более одной клетки. Из него и можно получить одну из указанных фигур.

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

Разобьем доску на квадратов доминошек (прямоугольников и один пятиклеточный уголок. В каждой доминошке сумма чисел не менее так как иначе в дополняющем квадрате сумма будет не более четырех. В трехклеточном уголке сумма не менее трех, так как иначе в дополняющем квадрате сумма будет не более четырех. Итого, сумма не менее

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

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

Очевидно, что если — минимально возможное число нулей в таблице, то искомая сумма достигает максимума, равного числу

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

В приведенной таблице нули находятся лишь на пересечении строки и столбца с четными номерами. Таким образом, максимальное значение суммы всех чисел в таблице равно

Оценка. Разделим квадрат на 4 одинаковых квадрата В каждом из этих четырёх покрасим клетки в 4 цвета следующим образом:

Заметим, что для каждого из цветов в выделенных 4 клетках не более двух коней, так как иначе какой-то из коней этого цвета будет бить двух коней. Значит, в квадрате не более 8 коней. Тогда в квадрате не более коней.

Пример:

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

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

Убрать двух коней, стоящих на простых клетках, контролируемых чёрными клетками (ими могут быть и сами чёрные кони).

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

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

Приведём пример, показывающий, что коней достаточно. На рисунке отмечены кони, которых нужно снять с доски.

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

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

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

Оценка. Давайте рассмотрим пары отмеченных клеток:

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

Пример. Закрасим центральную строку:

Тогда у каждой клетки найдётся соседняя по стороне закрашенная клетка.

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

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

Расположим коня в виде четырех прямоугольников прилегающих к углам доски и не имеющих общих участков границы. Легко проверить, что такой пример подходит.

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

Семи фигур не хватит, поскольку Пример для фигур легко строится: двумя такими фигурками легко покрыть квадрат а квадрат состоит из четырёх квадратов