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

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

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

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

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

Лемма. В любой гармонической расстановке либо в каждой строке, либо в каждом столбце находится ровно буквы.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

Оценка. Разобьём квадрат на квадратиков

Среди этих квадратиков не более

квадратиков, в которых покрашено хотя бы 2 клетки.
Остальных квадратиков — не менее

Из каждого из них можно вырезать трёхклеточный уголок.

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

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

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

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

Заметим, что на шахматной доске имеется диагоналей, содержащих нечётное число клеток и не имеющих общих клеток. Следовательно, число фишек не может быть больше (на каждой такой диагонали свободна хотя бы клетка).

Пример на ровно клеток изображен на рисунке.

Докажем, что нельзя расставить больше фишек. Число фишек на каждой вертикали кратно значит, их не больше а на всей доске — не более

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

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

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

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

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

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

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

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

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

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

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

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

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

Положим и пусть и — количества синих и красных клеток. Оценим сверху количество общих сторон красных клеток с синими.

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

(1)

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

(2)

Из (1) и (2) следует, что

Поскольку получаем отсюда

Поскольку а целое, получаем нужный результат.

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

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

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

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

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

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

Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с номерами от до поставим числа 1 до 5 и числа от до Тогда в каждой строке будет 5 уникальных чисел и еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице будут числа от до

Замечание.

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

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

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

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

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

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

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

Значит,

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

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

Если теперь проделать такие же рассуждения со второй и третьей строкой, получим, что третья строка должна быть противоположна второй (т.к. во второй также найдутся две рядом стоящие клетки одного цвета). Аналогично далее строки будут чередоваться, и вся таблица заполняется однозначно. Теперь поймём, при каких условиях на первую строку раскраска будет подходящей. Предположим, что в первой строке найдётся подстрока, в которой клеток одного из цветов хотя бы на больше, чем другого. Такую подстроку можно сократить до подстроки длины так, чтобы разница была ровно (т.к. при отбрасывании одной клетки разница меняется на 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 синих клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.

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

Занумеруем столбцы этой фигуры слева направо числами от до (пусть — количество столбцов). Пусть -й столбец содержит клеток, тогда

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

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

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

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

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

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

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

Если мы расставим и так, как показано на картинке ниже (в клетках, которых нет на картинке, стоят нули), то мы получим пример на

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

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

Аналогично, если мы определим как сумму чисел в клетках, находящихся в столбце с номером не меньшим и строкой не большей (если то ), то мы найдём такое число что

Пусть — число в клетке с на пересечении строки и столбца Поскольку мы можем оценить сумму чисел во всех клетках как

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