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

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

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

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

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

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

а белых клеток —

Их разность по условию равна т. е.

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

Получили противоречие.

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

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

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

Рассмотрим в нашем квадрате квадратов

Назовём их выделенными.

Заметим, что если одна клетка некоторого диполя принадлежит какому-то выделенному квадрату, то другая клетка этого диполя принадлежит (соседнему) выделенному квадрату.

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

Получаем оценку: максимальное число непересекающихся диполей во всём квадрате не больше

Построим теперь пример на диполей. Для этого “отрежем” левый нижний выделенный квадрат. Останется клетчатая фигура из клеток, которая разбивается на квадрат и два прямоугольника и Эта фигура полностью разбивается на диполи, поскольку любые последовательные клеток строки или столбца, очевидно, разбиваются на три диполя.

Предположим, что можно. Сумма всех чисел равна А удвоенная их сумма равна Посчитав суммы арифметических прогрессий, получаем

Противоречие, так как

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

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

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

Докажем утверждение от противного. Пусть есть раскраска, при которой отсутствует пара параллельных линий с одинаковым числом черных клеток. Будем называть весом линии количество черных клеток на ней. Пусть есть горизонталь веса Тогда вертикалей и диагоналей каждого направления должны иметь веса так как все они пересекают эту горизонталь. Тогда и горизонталей имеют веса так как все они пересекают вертикаль веса Циклически переставим горизонтали и вертикали так, чтобы нижняя горизонталь и левая вертикаль имели вес (свойства раскраски при этом не изменятся). Пронумеруем горизонтали снизу вверх от до а вертикали — от до слева направо. Каждая диагональ пересекает по разу горизонталь и вертикаль веса поэтому диагонали веса должны проходить через клетку их пересечения — клетку Итак, все клетки и не закрашены.

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

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

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

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

Тогда Вася достигает своей цели при

То есть если , то Вася не сможет выполнить задуманное.

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

Рассмотрим раскраску таблицы в три цвета, как показано на рисунке:

Если в исходной таблице к числам цвета 2 прибавить единицу, а из чисел цвета 3 вычесть единицу, то мы получим такую перестановку, что набор чисел сохранится. А сумма в каждой тройке тоже.

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

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

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

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

Первое решение.

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

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

Осталось раскрасить множество клеток, которое Васей и Петей разбито на пары так что ни одна Васина пара не совпадает с Петиной парой.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Для удобства назовём непересекающиеся группы клеток одного разбиения (Пети или Васи) фигурками.

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

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

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

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

Докажем, что полученная покраска будет искомой. Рассмотрим, например, произвольную фигурку Пети . Пусть - произвольная фигурка Васи. Заметим, что среди общих клеток фигурок и разность числа чёрных и белых клеток равна или 0 , в зависимости от чётности числа клеток в этом пересечении. Поэтому достаточно доказать, что разность +1 встречается среди пересечений фигурки Пети с фигурками Васи столько же раз, сколько и разность -1 . Пусть фигурке в графе соответствует вершина , которая лежит в некотором цикле из построенного ранее разбиения . Тогда каждой разности +1 соответствует ребро цикла , входящее в , а каждой разности -1 - ребро цикла , исходящее из . Из построения цикла следует, что рёбер, входящих в , в нём будет столько же, сколько и рёбер, исходящих из . Поэтому фигурок Васи, в клетках пересечения с которыми будет ровно на одну чёрную клетку больше, будет столько же, сколько фигурок Васи, в клетках пересечения с которыми будет ровно на одну белую клетку больше. Таким образом, в фигурке поровну чёрных и белых клеток.

Оценка.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример, подтверждающий точность полученной оценки

хороших клеток уже возможно.

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

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

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

Предположим противное: пусть среди четырёх клеток на пересечении любых двух строк и любых двух столбцов есть две клетки одинакового цвета.

Назовём горизонтальной (вертикальной) парой две клетки разного цвета, лежащие в одной строке (одном столбце). Назовём горизонтальным (вертикальным) совпадением две клетки одинакового цвета, лежащие в одной строке (одном столбце). Разделим пары на 6 типов по цветам входящих в них клеток:

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

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

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

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