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

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

Для начала рассмотрим, сколько различных наборов из клеток можно выбрать, чтобы никакие две не находились в одной строке или столбце. Всевозможных способов выбрать клеток так, чтобы в каждой строке и в каждом столбце была ровно одна — ровно число перестановок Это можно объяснить тем, что, допустим, выбирая по клетке в строке, с каждой строкой количество "разрешённых"вариантов уменьшается ровно на 1.

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

Шаг может принимать значения от 1 до можем оценить сверху количество плохих расстановок по строкам и столбцам (отдельно):

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

Получается, что количество всех "плохих"(содержащих хотя бы одну "запрещённую"четвёрку) наборов не превосходит:

Если бы решений не было, то все вариантов были бы плохими, и мы получили бы неравенство:

Разделим на и упростим:

Но при неравенство не выполняется. Получили противоречие.

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

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

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

Приведем пример посещения ферзем 57 клеток:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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