Раскраски

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 синих клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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