СПБГУ - задания по годам → .02 СПБГУ 2016

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

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

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

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

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

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

Установим теперь, что у них должно быть больше 15 кактусов. Предположим противное: пусть всего у них кактусов. Занумеруем кактусы числами от 1 до . Для кактуса с номером найдется кактусофил , у которого его нет. Но тогда для кактусофилов нет кактуса, который был бы у всех. И, тем более, нет такого кактуса, если мы к ним добавим еще нескольких кактусофилов так, чтобы их количество стало равно 15. Противоречие.

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

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

Если взять все числа, оканчивающиеся на или то их будет ровно 400, но никакая разность не равна 4,5 или 6.

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

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