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

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

Пример для показан на рисунке.

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

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

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

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

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

Заметим, что

Это означает, что одно из чисел или по модулю превосходит Но в каждом из соответствующих квадратов всего клеток, и числа в них по модулю не превосходят Противоречие.

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

Расстановка для белых ладей показана на рисунке:

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

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

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

Ясно, что следовательно, достаточно показать, что

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

при Расскрывая скобки и приводя подобные, имеем

Последнее является суммой неравенств

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

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

Пример с таким количеством отмеченных клеток показан на рис. справа.

a) Наблюдение 1: не на границе испачканные клетки располагаются парами, то есть нет отдельно стоящей, иначе мы сразу сможем вырезать бублик. Сколько бубликов запрещает пара? Если испачканные клетки соседние по стороне, то они запрещают 12 бубликов, а если соседние по одной вершине, то 14 бубликов. Если одна клетка испачкана на границе, то она запрещает максимум 3 бублика. Так как центральная клетка бублика может быть внутри квадрата , то всего бубликов 4900. Но проблема в том, что клетки могут располагаются не парами, а, например, по три клетки. Для того чтобы доказать задачу формально, перейдем к графам.

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

b) Оставляется читателям в качестве упражнения на построение примера:)

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

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

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

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

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

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

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

Значит, неединичные элементы встречаются парами. Одна пара влияет на три произведения — строку и два столбца или наоборот. Неединичных произведений хотя бы поэтому пары хотя бы две. Если пар хотя бы три, то неединичных чисел хотя бы (если элементов то все они лежат в одной строке, тогда произведения в других строках единичные и равны, аналогично со столбцами). Если же пары ровно две, то в случае их пересечения по одному элементу ими покрыты всего строки и столбца, откуда хотя бы в двух произведение единичное. Итак, неединичных элемента хотя бы

Осталось привести пример

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

На шахматной доске белых клеток При этом, если ладья расположена на белой клетке, то она бьет белых клеток, если же на черной клетке, то 8 клеток.

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

2) Если на какой-то полосе (объединении двух соседних линий), для определенности на горизонтальной, нет ни одной ладьи, то 8 белых клеток этой полосы должны биться 8 ладьями по вертикали, что противоречит условию задачи.

3) Следовательно, на каждой из 4-х горизонтальных и 4-вертикальных полос стоит ровно 1 ладья.

Горизонтальные и вертикальные полосы, пересекаясь, образуют 16 клеток размера ( черных и белых клетки ). Для определения требуемого расположения ладей необходимо указать по одной клетке на каждой горизонтали так, чтобы на одной вертикальной полосе была только одна клетка (см. п. 1). Всего таких способов выбора клеток будет Учитывая утверждения 1) и 2) внутри каждой клетки ладью можно расставить двумя способами и получить количество расстановок

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

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

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

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

Пример подходящей расстановки:

Обозначим через ответ в задаче; положим Докажем сначала, что

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

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

Поскольку из доказанного неравенства (*) следует, что

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

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

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

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

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

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

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