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

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

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

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

Если или — нечётно, то в этих столбцах нет ни одного коротышки, расстояния от которого до двух выделенных домов одинаковы.

Если а чётно, то в столбце находится один коротышка, расстояния от которого до двух домов одинаковы.

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

Если же то в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно Аналогично, в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно

Заметим, что

Значит, какое-то из чисел не больше

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

Для каждой ячейки посчитаем сумму чисел ней и в её соседях и сложим все эти суммы. Полученное число будет не менее

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

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

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

Поделим клетки на три вида — угловые(4), боковые(12), внутренние(9). Легко видеть, что угловые входят ровно в один квадрат , боковые — в два, а внутренние — в 4. Чтобы сделать сумму по квадратам минимальной (а мы вдруг захотели сделать именно так), нужно взять первые два вида клеток, в сумме их как раз . Тогда сумма будет равна , чему она и равна по условию. Но поскольку это единственный способ получить такую сумму, то раскрашены могут быть только все клетки, кроме внутренних.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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