Клетчатые задачи → .03 Подсчеты в клетчатых задачах

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим противное. Ясно, что в таблице есть пустые столбцы. Заметим, что крайним пустой столбец быть не может. Действительно, если, скажем, правый столбец пуст, то из самого правого непустого столбца можно сдвинуть фишку вправо. Аналогично доказывается, что не может быть двух пустых столбцов подряд. Итак, слева от каждого пустого столбца есть фишка. Её нельзя сдвинуть вправо, значит, в той же строке справа через одну от неё стоит фишка. Таким образом, каждая “левая” фишка находится в строке, где есть другие фишки. Пусть всего пустых столбцов Тогда соответствующих “левых” фишек не меньше Следовательно, все фишки занимают не более строк, и пустых строк не меньше то есть больше чем пустых столбцов. Аналогично можно доказать, что пустых столбцов больше, чем пустых строк. Противоречие.

Пусть — количество клеток доски которые одновременно доминируют по строке и по столбцу, — количество клеток доски которые доминируют только по строке, — количество клеток доски которые доминируют только по столбцу. Заметим, что

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

следовательно,

Сложив суммы трех столбцов, получим, что сумма всех записанных чисел равна 333. Сложим теперь все ряды, проходящие через центр. Их 4: строка, столбец и две диагонали. Сумма равна 444. В нее центральное число входит четырежды, а остальные — ровно по разу. Три экземпляра центрального числа и дают избыток в 444 — 333 = 111. Значит, центральное число равно 111:3 = 37.

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечание.

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