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

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

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

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

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

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

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

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

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

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

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

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