Клетчатые задачи

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

Таким образом, каждый раз мы закрашиваем хотя бы 3 отрезка. А после выставления 37 фишек мы закрасим зелёным как минимум 111 отрезков.

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

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

Таким образом, у каждой стороны квадрата будет не больше трёх клеток с фишками. Поэтому будет закрашено зелёным не более 6 из 7 отрезков границ в этой линии, то есть непокрашенных отрезков хотя бы 4, что противоречит выводу из пункта 2. Значит, 37 фишек выставить нельзя.

36 фишек выставить можно (числами обозначено, в какой последовательности выставляются фишки):

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

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

Оценка. Покажем, что никакое не подходит.

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

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

откуда

что невозможно при и достаточно большом .

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Назовем соседними две клетки с общей стороной. Число интересных пар, содержащих заданную отмеченную клетку, не больше 4, а для граничной клетки — не больше 3 . Тогда общее число интересных пар не превосходит . При этом если среди отмеченных клеток есть две соседние, то содержащая их интересная пара считается дважды. Заметим, что среди 9 клеток из прямоугольника обязательно есть две соседних. Поэтому среди отмеченных клеток имеется либо граничная, либо две соседних. Таким образом, общее число интересных пар не превосходит 35. Пример разметки с 35 интересными парами приведен ниже.

Несложно проверить, что куб можно разрезать на кубика и кубика

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

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

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

Пример на рисунке.

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

Оценка. Раскрасим доску в шахматном порядке. Пусть, не умаляя общности, клон начинает путь с белой клетки. Тогда цвета его клеток идут в таком порядке: Б-Б-Ч-Б-Б-Ч-Б-Б-Ч и т. д. В самом деле, за два хода как конь клон возвращается на клетку белого цвета и делает лишний ход Б-Б. Поэтому после 27 посещенных клеток клон пройдет по всем белым клеткам, и перейти на 28-ю клетку (а она тоже должна быть белого цвета) не сможет.

Пример приведен на картинке, клетки пронумерованы в порядке обхода клона, клетка с номером один — та, с которой он начинает.

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

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

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

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

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

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

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