Клетчатые задачи → .01 Раскраски

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

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

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

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

1	2	3	…	1
2	3	1	…	2
3	1	2	…	3
1	2	3	…	1

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

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

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

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

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

В решении будем называть квадратами все четверки с координатами Аналогичное определение введем для квадратов

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

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

откуда то есть

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

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

Значит, -тетрамино покроют нечетное количество белых клеток, а должны покрыть — противоречие.

Раскрасим дно прямоугольной коробки в горошек как на рисунке с одной чёрной клеткой в каждом квадратике

Пусть всего получилось черных клеток. Каждый квадратик покрывает ровно одну черную клетку, а каждая плитка  — или черных клеток. Значит, четность числа совпадает с четностью количества квадратиков

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

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

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

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

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

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

Оценка. Сначала сформулируем и докажем следующую лемму:

Лемма. Пусть — количество клеток некоторого цвета Тогда существует не более квадратов в которых клеток этого цвета хотя бы

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

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

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

Но так как каждая клетка покрашена в один цвет:

Значит,

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

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

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

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

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

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

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

Получаем ответ:

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

Докажем теперь, что меньше 120 закрашенных клеток не может быть.

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

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

Сравним числа и

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

Но раз а в каком-то из наших не более чем 10 столбцов присутствуют хотя бы 6 красных клеток. Так как в нём должно быть ещё и 6 синих, мы получаем, что общее количество закрашенных клеток в этом столбце хотя бы 12, то есть, и Тогда, чтобы было меньше 120, необходимо Продолжим эти рассуждения.

Поскольку значит Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 7 красных клеток, откуда

Поскольку в каком-то столбце присутствуют хотя бы то есть хотя бы 8 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 9 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 11 красных клеток, откуда

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

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

Но раз а в какой-то из наших не более чем 10 строк присутствуют хотя бы 7 синих клеток. Так как в ней должно быть ещё и 5 красных, мы получаем, что общее количество закрашенных клеток в этой строке хотя бы 12, то есть, и Тогда, чтобы было меньше 120, необходимо Продолжим эти рассуждения.

Поскольку в какой-то строке присутствуют хотя бы то есть хотя бы 8 синих клеток, откуда

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

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

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

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

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

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

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

Предположим, что можно. Разберём два случая:

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

Случай Если то Занумеруем строки и покрасим строки с номерами в красный цвет. Далее по аналогичным рассуждениям получим, что кратно Снова пришли к противоречию.

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

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

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

Если делится нацело то можно разделить всё только на прямоугольники Их будет штук, если обозначить

Если даёт остаток при делении на то обозначим так же и покажем, что делится нацело на

Пронумеруем строки сверху вниз и покрасим строку в цвет остатка её номера по модулю Тогда на доске клеток каждого цвета и клеток каждого цвета

Рассмотрим произвольное разрезание на прямоугольники. Пусть в разрезании участвуют прямоугольников Перекрасим все клетки, покрытые этими прямоугольниками в -ый цвет. Каждый из прямоугольников содержит по одной клетке каждого из цветов. Тогда на доске клеток каждого цвета и клеток каждого цвета которые покрыты фигурами

Заметим, что каждая из фигур покрывает клетки фиксированного цвета. Тогда кратно и кратно Наконец, кратно Значит, в этом случае можно разделить всё на прямоугольники

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

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

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

Пусть в Петином разбиении горизонтальных домино и вертикальных домино. Тогда в Васином разбиении тетрамино. Горизонтальные домино содержат одну черную клетку и одну белую и вносят вклад 0 в разность количества черных и белых клеток фигуры. А каждая вертикальная доминошка и каждая -тетраминошка вносит вклад в эту разность.

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

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