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

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

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

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

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

Теперь сделаем то же самое с первым и четвертым столбцом (2 хода), а потом - с первой и четвертой строкой (еще 2 хода).

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

Приведем пример, что оба варианта могут реализоваться.

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

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

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

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

Первые позиции заполняем различными простыми числами Эти числа должны быть новыми, то есть не использовавшимися ранее в таблице.

В следующих клетках размещаем числа

Последние две позиции оставляем незаполненными.

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

Это количество можно посчитать как разность количества клеток в квадрате и количества клеток в квадрате (размер пустого квадрата в рамке). Это равно .

Разобьём таблицу на квадратов Поскольку сумма чисел во всей таблице равна

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

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

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

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

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

вхождений Следовательно, имеем

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

В результате двойного подсчета мы получаем следовательно кратно Следовательно, должно быть кратно что завершает доказательство.

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

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

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

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

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

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

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

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

Если или то номера Пети и Васи совпадут во всех клетках. Значит, и Пусть тогда где Получаем Поэтому так как аналогично с Следовательно, количество клеток, получивших одинаковые номера, равно

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

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

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

Над (под) диагональю находится чисел. Заметим, что сумма 300 наибольших чисел таблицы (14, 15, , 25, взятые по 25 раз) равна и ровно в три раза больше суммы 300 наименьших чисел (1, 2, …, 12, взятые по 25 раз), которая равна . Обозначим . Тогда если над диагональю есть число меньше 14, то там сумма меньше, чем , а под диагональю всегда хотя бы ?! Значит, над диагональю все максимальные числа и аналогично под диагональю все минимальные числа. Тогда все числа на диагонали равны 13.

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

Заметим, что (в силу выбора Тогда

Заметим, что

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

Докажем, что Пусть е слагаемое этой суммы равно Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что то есть Пусть то есть Тогда в первых столбцах содержатся только числа от до следовательно, там содержатся все такие числа. Отсюда следует, что и Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых. Итак,

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

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

Придумаем алгоритм. Разобьём фишки на четвёрки, стоящих на двух соседних вертикалях. Каждую четвёрку передвинем за 30 ходов так, как показано на рисунке:

"Потери"на горизонтальные ходы происходят только на втором и четвёртом этапах.

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

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

Наконец,

Таким образом, все суммы и равны нулю.

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

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

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

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

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

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