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

В одной строке не менее 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 интересными парами приведен ниже.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть выбран некоторый максимальный набор секций.

Сделаем два замечания.

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

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

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

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

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

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

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