Подсчеты в клетчатых задачах

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

или что и требовалось.

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

подходящих пар. То есть всего нужных нам пар не меньше, чем

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

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

Оценка.

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

Отметим два факта:

1.

Количество операций четно, ведь операция меняет четность числа черных клеток, тогда достаточно показать, что .

2.

Порядок выполнения операций не влияет на конечный результат перекрашивания.

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

Рассмотрим несколько случаев:

1.

Тогда клеток НЕ находящихся в столбцах и строках, где были операции II-го или III-го типа , а любая операция I-го типа перекрашивает не более двух клеток, тогда всего ходов хотя бы

2.

После выполнения операций II-го типа останется ровно 100 белых клеток. , значит, операций III-го типа нет, тогда для перекрашивания белых клеток понадобиться хотя бы 50 операций I-го типа. Получаем, что всего операций не меньше, чем .

3.

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

4.

: — нечётное.

Этот случай невозможен по чётности количества ходов.

Случаи для аналогичны случаям для .

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

Выполним операцию III-го типа ко всем клеткам из первой строки. Это 100 ходов. Далее применим операцию I-го типа к парам из клеток первой строки (на пары разобьем последовательно , то есть 1-ая и 2-ая клетки, 3-яя и 4-ая, , 99-ая и 100-ая). Это ещё ходов. Итого 200.

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

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

имеем

По неравенству между средним квадратическим и арифметическим, имеем

Тогда

Обозначим количество белых клеток через

Тогда после сокращения на получаем

С другой стороны, по неравенству между средним арифметическим и геометрическим, имеем

То есть

откуда получаем

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

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

Заметим, что при данное неравенство не выполнено, откуда

Пример. Как на рисунке. Клеточки квадрата имеют сторону

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

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

Оценим Аналогично

Тогда

Обозначим количество белых клеток через Тогда после сокращения на получаем

С другой стороны То есть

откуда получаем

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

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

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

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

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

Рассмотрим разрезание как на картинке. Четыре прямоугольника на границе имеют размер . Оставшиеся 19 прямоугольников имеют размер .