Клетчатые задачи и комбинаторные подсчёты на СПБГУ

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

Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с номерами от до поставим числа 1 до 5 и числа от до Тогда в каждой строке будет 5 уникальных чисел и еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице будут числа от до

Замечание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример на фишки:

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

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

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

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

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

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

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

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

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

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

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

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

Разделим таблицу на 12 прямоугольников и еще одну клетку.

Тогда в каждом прямоугольнике должна быть отмечена хотя бы 1 клетка и всего отмечено хотя бы 12 клеток.

_________________________________________________________________________________________________________________________________________________________________________________

Отметим центральный крест без середины.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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