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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Рассмотрим граф, вершинами которого являются вершины прямоугольников, и две вершины графа соединены ребром тогда и только тогда, когда они являются диагонально-противоположными вершинами одного из прямоугольников разбиения.

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

Есть две возможности.

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

Два пути — это и (и аналогичный случай и По условию и имеют одинаковые цвета, поэтому другие концы путей (то есть и одинаковой чётности тоже имеют одинаковые цвета.

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

Предположим, что такое возможно. Покрасим клетки доски как на рис.

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

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

Пример. Разобъем наш квадрат на четыре квадрата Опишем покраску правого нижнего квадрата. Покрасим в цвет верхнюю строчку. Затем каждому четному столбцу сопоставим новый цвет и покрасим в него все клетки этого столбца, кроме верхней. Оставшиеся клетки нечетных столбцов покрасим каждую в свой уникальный цвет. Итого, цветов. Раскраска левого нижнего квадрата выглядит также, только с поворотом на по часовой стрелке и все цвета новые. Раскраска левого верхнего и правого верхнего получаются из исходного поворотом на и и заменой всех цветов на новые. Итого, цветов. Но ещё есть проблема с центральным квадратом, которая решается путём склеивания каких-то двух цветов, попавших в этот квадрат — итого цветов. Для оценки сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

База. Все клеток в одной строке. Если они стоят подряд, то есть в точности квадратов. А если не подряд, то ещё меньше.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Решим задачу для прямоугольника , где — произвольные натуральные числа. Мы докажем, что ответом является число

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

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

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

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

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

Для начала рассмотрим, сколько различных наборов из клеток можно выбрать, чтобы никакие две не находились в одной строке или столбце. Всевозможных способов выбрать клеток так, чтобы в каждой строке и в каждом столбце была ровно одна — ровно число перестановок Это можно объяснить тем, что, допустим, выбирая по клетке в строке, с каждой строкой количество "разрешённых"вариантов уменьшается ровно на 1.

Теперь рассмотрим четвёрки клеток, центры которых лежат на одной прямой. Ясно, что их координаты по оси ординат и абсцисс образуют арифметическую прогрессию с начальным членом и шагом для которых выполняется:

Шаг может принимать значения от 1 до можем оценить сверху количество плохих расстановок по строкам и столбцам (отдельно):

"Запрещённая"четвёрка определяется выбором прогрессии по столбцам, по строкам, направлением (по строкам и столбцам). Каждая "запрещённая"четвёрка клеток встречается в любом наборе из содержащем эти четыре клетки. Остальные клетки можно выбрать произвольно (с учётом строки–столбца), то есть из вариантов.

Получается, что количество всех "плохих"(содержащих хотя бы одну "запрещённую"четвёрку) наборов не превосходит:

Если бы решений не было, то все вариантов были бы плохими, и мы получили бы неравенство:

Разделим на и упростим:

Но при неравенство не выполняется. Получили противоречие.

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

Сначала приведём стратегию за Соню. Пока она не получила больше 299 монет, перед её ходом на доске остаётся хотя бы 101 монета. Разобьем доску на 100 квадратов Получается, что какие-то две монеты лежат в одном и том же квадрате Если эти две монеты соседние по стороне, то Соня надвигает одну на другую, и получает ещё одну монету. Если они стоят по диагонали, то Соня сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину 2, строка — длину 200). Теперь, какой бы ход ни сделала Даша, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Сони), значит, своим следующим ходом Соня сможет получить ещё одну монетку. Таким образом, Соня всегда сможет увеличивать свой выигрыш, пока он меньше 300.

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

Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах а ещё одна располагается в одном из двух последних столбцов 199, 200. Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Даша будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Сони позиция осталась стабильной, то Даша двигает сотую красную фишку между двумя последними столбцами, так же Даша поступит и своим первым ходом. Если же после хода Сони позиция перестала быть стабильной, то Соня подвинула одну из красных монет из некоторого столбца в соседний столбец. Тогда Даша своим ходом вернёт её в столбец Таким образом, на доске всегда останется хотя бы 100 монет, и Соня заработает не более трёхсот рублей.

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

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

1) Приведём пример хорошей раскраски, в которой 120 чёрных клеток. Красим первый столбец белым, следующие 3 столбца — черным, пятый столбец — белым, и далее продолжаем с периодом 5.

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

Покажем, что оно единственно. Посмотрим на границу между 5-м и 6-м столбцами. Эта граница не может находиться внутри блока, значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник Далее продолжим аналогичные рассуждения с отрезанием прямоугольников Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника В первом столбце не может быть вертикальная доминошка, поэтому в 1-м и 2-м столбцах точно находится блок. Аналогично в 4-м и 5-м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша раскраска хорошая, завершено.

2) Оценка. Рассмотрим хорошее разбиение прямоугольника В каждом блоке не более двух чёрных клеток, иначе мы можем заменить две горизонтальные доминошки этого блока на вертикальные, и разбиение останется хорошим.

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

Остаётся понять, что тёмных доминошек не более 20. Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в образованном ими прямоугольнике можно заменить все доминошки на горизонтальные, и разбиение останется хорошим. Рассмотрим две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять 0, 1, 2 или 3 клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно). Суммируя длины промежутков для пар ближайших тёмных доминошек, получаем, что количество вертикалей не менее

Но оно равно 100. Отсюда и что невозможно при Неравенство установлено. Доказательство оценки завершено.

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

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

Докажем, что среди ходов должно быть хотя бы 20 неприятных (а значит, количество приятных ходов не больше 44). Расставим в клетках числа, как показано на первом рисунке; клетки с одинаковыми числами удалены на одно и то же расстояние от центра, а клетки с меньшими номерами ближе к центру, чем клетки с большими.

Каждый ход из клетки с числом 1 не уменьшает расстояния до центра и потому неприятен — таких ходов 4. Ход из клетки с числом 2 может быть приятным, только когда он идёт в клетку с числом 1. Но на доске восемь чисел 2 и только четыре числа 1, поэтому хотя бы четыре хода из клеток с числом 2 будут неприятными.

Рассмотрим теперь ходы, ведущие в 32 клетки с числами, не меньшими 6. Заметим, что эти ходы не могут идти из клеток с числами 1 и 2, то есть в рассуждении выше они не учтены. Такой ход может быть приятным, только если он идёт из клетки с номером, не меньшим 7; однако таких клеток всего 20. Значит, среди рассмотренных ходов ещё неприятных, и общее количество неприятных ходов не меньше, чем

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

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

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

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

Приведем пример посещения ферзем 57 клеток:

Оценка. Расставим на доске 21 корабль так, как показано на рисунке. Таким образом, для поражения каждого из кораблей необходимо отметить по крайней мере 21 клетку.

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

Рассмотрим клетки

Конь не сможет одновременно бить две из них. Их поэтому хотя бы одна будет не под боем.

Будем считать, что главная диагональ покрашена в цвет 1. Разобьём нашу доску на квадратов Тогда в каждом таком квадрате будет ровно по 3 клетки каждого цвета. Значит, всего каждого цвета клеток, так что нам придётся перекрасить хотя бы клеток. Будем приводить всё к цвету 1 и покажем, что нам не придётся трогать белые клетки. Рассмотрим отдельный квадрат В нём есть два уголка, не содержащие цвет 1. Тогда, если центральная клетка уголка цвета 3, сделаем 4 перекрашивания (2 с одной угловой клеткой и 2 — с другой), а иначе — 2 перекрашивания (по одному с угловыми клетками). Тогда уголок станет цвета 1, причём мы не взаимодействовали с другими клетками. Сделав так для всех уголков, получим раскраску всей доски в цвет 1.

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

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

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

Пример. Укладываем у стороны длиной вплотную друг к другу слева направо ряд из квадратов; следующий ряд из квадратов выкладываем со сдвигом на клетку вверх и вправо, следующий ряд — со сдвигом вверх и влево, и так далее (см. рис.).

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

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

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