Клетчатые задачи

Заметим, что больше фигурок из клеток в каждой поместить на клетчатую бумагу, в которой всего клетки, заведомо не удастся (т. к. Поэтому остается подыскать пример из полосок. Вот он:

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

Пример. На рисунке отмечены клетки, по которым пройдет ладья.

Очевидно, что если — минимально возможное число нулей в таблице, то искомая сумма достигает максимума, равного числу

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

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

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

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

Оценка. Разделим квадрат на 4 одинаковых квадрата В каждом из этих четырёх покрасим клетки в 4 цвета следующим образом:

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

Пример:

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

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

если содержит хотя бы один множитель, кратный девяти;

если содержит не менее двух множителей, кратных трем, но не кратных девяти.

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

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

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

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

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

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

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

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

Приведём пример, показывающий, что коней достаточно. На рисунке отмечены кони, которых нужно снять с доски.

Назовём реверсированием набора лампочек смену состояния всех лампочек этого набора на противоположное. Отметим два простых факта.

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

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

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

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

Если , то чётно и не равно нулю (в противном случае все лампочки будут выключены), откуда

Аналогичным образом рассматриваются случаи и Для дальнейшего заметим, что для Поэтому при

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

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

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

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

Оценка. Давайте рассмотрим пары отмеченных клеток:

Заметим, что чтобы для каждой из пар клеток выполнялось условие, хотя бы две из пяти клеток (соседних 3 или сами 2 рассматриваемые клетки) должны быть закрашены. Причём области, где могут находиться закрашенные клетки с каждой из пар отмеченных клеток не пересекаются. Значит, наименьшее количество клеток, которые можно закрасить, чтобы выполнялось условие - 2016.

Пример. Закрасим центральную строку:

Тогда у каждой клетки найдётся соседняя по стороне закрашенная клетка.

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

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

Следовательно, всего ладей не больше, чем

Покажем далее как разместить ладей. На доске можно разместить ладьи как показано на рисунке, а затем поставить таких квадратов по диагонали.

Оценка. Всего покрыто клеток. клеток, описанных в условии покрыты, раз. Остается еще покрытий клеток. Значит, клеток, покрытых хотя бы раз, не более

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

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

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

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

Найдем наибольшее значение суммы. В каждом квадрате есть хотя бы два числа “”. Поэтому наибольшее значение суммы — это Достигается, когда в центральном квадрате стоят две единицы, а остальные числа — двойки.

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

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

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

Пример разрезания приведен на картинке. Возможно, он не единственный.