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

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

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

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

Расстановок, когда -я фигура бьёт -ю — не более чем

Умножив на число пар получим грубую оценку сверху количества “плохих” расстановок:

Но это число меньше чем количество всех расстановок. (

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

Переберём все квадраты по длины стороны :

Зафиксируем все квадраты со стороной положением их левого нижнего угла.

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

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

Итак, всего квадратов:

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

Получаем ответ

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

Поэтому остаток от деления на 5 суммы всех расставленных чисел равен

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

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

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

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

Нам нужно максимизировать это выражение, т.е. минимизировать сумму квадратов восьми чисел, сумма которых составляет 23. Как известно, сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2.

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

Аналогичную оценку можно получить для суммы "вертикальных"слагаемых, что даёт нам итоговое значение 234.

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

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

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

Пример. Для прямоугольника получаем

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

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

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

Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше Каждое слово содержит не больше клеток, поэтому количество правильных слов не меньше Отсюда

Пример. На картинке показано, в каком порядке красить клетки: сначала красим все серые клетки, дальше в порядке возрастания номеров. Несложно видеть, что у каждой клетки с номером, начиная с не более одного соседа с бoльшим номером.

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

Допустим, можно. Каждым ходом освобождается от шашек не более одной клетки. Так как вначале все клетки заняты, а в конце ровно 9999 клеток должны быть свободны, то никакая свободная клетка не должна быть повторно занята. На клетке , где собраны все шашки, пересекаются вертикаль и горизонталь. Ходы на делались только с этой вертикали и этой горизонтали, причем из каждой клетки не более одного раза. Число шашек, пришедших из клетки в , равно расстоянию между и . Сумма расстояний от всех клеток вертикали и горизонтали максимальна для угловой клетки X, она равна . Значит, включая шашку, стоявшую изначально на Ф, на этой клетке могло собраться не более 9901 шашки. Противоречие.

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

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

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

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

Рассмотрим левый квадрат на рисунке ниже:

В нём клетки разбиваются на 4 квадрата 3 на 3, поэтому сумма чисел в них равна Далее, каждая пятёрка более тёмных клеток сверху и снизу лежат в одном квадрате 3 на 3, кроме них в этих квадратах ещё 4 клетки, в которых записано число, не менее -1. Следовательно, сумма чисел в каждой более тёмной пятёрке клеток не превосходит 4. Числа в оставшихся трёх более светлых клетках не больше 1, поэтому общая сумма не больше В правом квадрате приведён пример правильного заполнения квадрата с суммой

Разобьем доску на рамки толщины и пронумеруем рамки по убыванию длин сторон. Тогда всего клеток в рамках с нечетными номерами

Тогда черных клеток там ровно Заметим, что каждый король бьет не более 2 черных клеток из этих рамок. Поэтому королей не меньше

Пример для доски изображен на картинке и естественным образом обобщается на любое нечетное число.

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

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

поскольку суммарное количество длин всех ребер равно количеству клеток доски.

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

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

с другой,

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

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

Наконец,

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Сначала рассмотрим “крайнюю” ситуацию. Если во всех клетках таблицы числа равны то и все произведения равны а их общая сумма равна

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

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

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

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