E17 Метод усреднения

Метод состоит в том, что мы вычисляем (или оцениваем) среднее значение некоторой характеристики по всем объектам, а затем делаем вывод: *хотя бы один объект не хуже среднего$* ($и хотя бы один не лучше). Формально: если $N$ чисел имеют среднее $M = S/N$, то среди них найдётся число $\geq M$ и число $\leq M$.

Почему этот метод существует отдельно от принципа Дирихле (E4)? Дирихле говорит: если $n+1$ предмет в $n$ ящиках, то в каком-то ящике $\geq 2$ предметов. Усреднение говорит: средняя загрузка ящика $= M$, значит хотя бы один ящик загружен $\geq M. Разница в том, что Дирихле работает с дискретными объектами и целочисленными оценками, а усреднение работает с любыми числовыми характеристиками — непрерывными, дробными, суммарными. Усреднение часто используется там, где Дирихле прямо не применить.

Интуиция: в классе 30 учеников средний рост 170 см. Значит, найдётся хотя бы один ученик ростом $\geq 170$ см (и хотя бы один $\leq 170$ см). Это тривиально — но именно эту «тривиальность» мы эксплуатируем в нетривиальных задачах, когда среднее вычисляется через сложную комбинаторную сумму.

Метод часто связан с двойным счётом (E1): сначала двойным счётом находим суммарное значение $S$, затем делим на число объектов $N$ и получаем среднее $M = S/N$, из которого делаем вывод о существовании объекта с нужным свойством.

• Принцип среднего. Пусть $x_1, x_2, \ldots, x_N$ — вещественные числа и $\overline{x} = \frac{1}{N}\sum_{i=1}^N x_i$. Тогда $\min_i x_i \leq \overline{x} \leq \max_i x_i$, причём существует $i$ с $x_i \geq \overline{x}$ и существует $j$ с $x_j \leq \overline{x}$. Условие: применимо всегда. Когда использовать: для доказательства существования объекта с $x \geq M$ или $x \leq M$.
• Следствие для существования. Если среди $N$ объектов суммарная «стоимость» равна $S$, то найдётся объект со стоимостью $\geq S/N$. Условие: стоимость — неотрицательная числовая характеристика. Когда использовать: задачи на нижнюю оценку, «докажите, что найдётся объект с не менее чем...».
• Связь с двойным счётом. Если каждый из $N$ объектов вносит вклад в суммарную характеристику $S$, и $S$ вычислена двойным счётом, то среднее $S/N$ — готовая нижняя оценка. Когда использовать: комбинаторные задачи о рёбрах, парах, пересечениях.
• Усреднение по подмножествам (вероятностный аргумент). Если выбрать случайный объект из $N$ и его ожидаемое значение равно $M$, то найдётся конкретный объект со значением $\geq M$. Это переформулировка принципа среднего в языке вероятностей. Когда использовать: продвинутые задачи, теорема Турана.

• Вычислить суммарную характеристику $S$ двойным счётом: подсчитать одну и ту же величину двумя способами, получить $S$, а затем поделить на $N$.
• Найти «правильные объекты» для усреднения: что именно усредняем — рёбра по вершинам, задачи по ученикам, пересечения по парам.
• Перейти от суммы к среднему: записать $\overline{x} = S/N$ и сделать вывод о существовании объекта с $x_i \geq \overline{x}$.
• Применять к графам: если суммарная степень вершин $= 2|E|$, то средняя степень $= 2|E|/n$, значит найдётся вершина со степенью $\geq 2|E|/n$.
• Применять к множествам: если $N$ подмножеств содержат в сумме $S$ элементов, найдётся подмножество с $\geq S/N$ элементами.
• Соединять с неравенством: зная среднее, оценить максимум или минимум через конкретные оценки параметров задачи.

Поверхностные признаки (что буквально написано):
- «Докажите, что найдётся...», «покажите, что существует...», «докажите, что хотя бы один...».
- Задача требует доказать существование объекта с некоторым числовым свойством (степень, количество, длина).
- В условии фигурируют «среднее», «суммарное», «в сумме дают».

Структурные признаки (форма выражения, объекты):
- Есть набор однотипных объектов (вершины, ученики, подмножества) с числовыми характеристиками.
- Суммарная характеристика вычисляется легко (через двойной счёт или формулу), а нужно доказать существование объекта с большим значением.
- Нижняя оценка в задаче выглядит как дробь с $N$ в знаменателе.

Цель задачи (что от тебя хотят):
- Доказать существование вершины/объекта с характеристикой не меньше заданного порога.
- Найти нижнюю оценку максимального значения.
- Доказать существование конфигурации (подграфа, подмножества) с нужными параметрами.

Задача 1. В классе 30 школьников. Известно, что каждый из них решил хотя бы одну из трёх задач контрольной, причём суммарное число решённых задач равно 53. Докажите, что найдётся школьник, решивший не менее двух задач.

Источник: тренировочная (дух ВсОШ школьного тура, 8–9 класс).

Как думать (рассуждение ученика$):
1. $Что я вижу?$ 30$ объектов (школьников) с числовыми характеристиками (количество решённых задач). Надо доказать существование объекта с характеристикой $\geq 2$.$2. *$Какой триггер? «Найдётся хотя бы один с...» + конкретная числовая характеристика → метод усреднения.$3. *$Первый ход: вычислю среднее число задач на одного школьника: $\overline{x} = 53/30 \approx 1{,}77$.$4. *$Ключевая идея:* среднее больше 1, значит хотя бы один школьник решил строго больше среднего, то есть $\geq 2$ задач. (Точнее: если бы все решили $\leq 1$, суммарное было бы $\leq 30 < 53$ — противоречие.)

Решение:
Обозначим число задач, решённых $i$-м школьником, через $x_i$. По условию:$\sum_{i=1}^{30} x_i = 53.$ Если бы каждый школьник решил не более одной задачи ($x_i \leq 1$ для всех $i$), то$$\sum_{i=1}^{30} x_i \leq 30 < 53 — \text{противоречие.}$$ Значит, найдётся школьник с $x_i \geq 2$.

Ответ: такой школьник найдётся.

Что в этой задаче было главным: сравнить суммарное значение (53) с максимально возможным при отрицании тезиса (30) — это и есть метод усреднения в простейшей форме.

Задача 2. В простом графе на $n \geq 2$ вершинах нет треугольников. Докажите, что число рёбер не превышает $n^2/4$. (Теорема Манте́ля.)

Источник: теорема Мантела (1907); стандартная задача ВсОШ регионального тура и олимпиад высокого уровня, 9–11 класс.

Как думать (рассуждение ученика$):
1. $Что я вижу?* Граф без треугольников, надо ограничить число рёбер. Числа $n$ и $n^2/4$ подсказывают: среднее здесь — это $n/2$.$2. *$Какой триггер? Задача на существование/оценку суммарной характеристики (рёбер) по всем объектам (вершинам). Думаю об усреднении.$3. *$Первый ход: для каждого ребра $\{u, v\}$ посчитаю $\deg(u) + \deg(v)$.$4. *$Ключевая идея: если $\{u,v\}$ — ребро, то $u$ и $v$ не имеют общего соседа (иначе был бы треугольник). Значит $\deg(u) + \deg(v) \leq n$.

Решение:
Пусть $G$ — простой граф на $n$ вершинах без треугольников, $E = |E(G)|$ — число рёбер. Для любого ребра $\{u, v\} \in E(G)$ вершины $u$ и $v$ не имеют общего соседа: если бы вершина $w$ была смежна и с $u$, и с $v$, тройка $\{u, v, w\}$ образовывала бы треугольник. Значит, множества $N(u)$ и $N(v)$ (соседей $u$ и $v$) не пересекаются, причём $N(u) \cup N(v) \subseteq V$:$$\deg(u) + \deg(v) \leq n \quad \text{для каждого ребра } \{u,v\}.$$ Суммируем по всем рёбрам:$$\sum_{\{u,v\} \in E} (\deg(u) + \deg(v)) \leq n \cdot |E|.$$ С другой стороны, левая часть — это двойной счёт: каждая вершина $u$ степени $\deg(u)$ входит в точно $\deg(u)$ рёбер, поэтому:$$\sum_{\{u,v\} \in E} (\deg(u) + \deg(v)) = \sum_{u \in V} \deg(u)^2.$$ По неравенству Коши–Буняковского (или QM-AM):$$\sum_{u \in V} \deg(u)^2 \geq \frac{\left(\sum_{u \in V} \deg(u)\right)^2}{n} = \frac{(2|E|)^2}{n} = \frac{4|E|^2}{n}.$$ Получаем:$$\frac{4|E|^2}{n} \leq n \cdot |E| \implies 4|E| \leq n^2 \implies |E| \leq \frac{n^2}{4}.$$

Ответ: $|E| \leq \dfrac{n^2}{4}$.

Что в этой задаче было главным: связать локальное условие (нет треугольников → $\deg(u)+\deg(v)\leq n$) с глобальной суммой через двойной счёт, а затем применить неравенство для среднего. Усреднение и двойной счёт здесь неразлучны.

• Ошибка: путать метод усреднения с принципом Дирихле → Почему неверно: Дирихле говорит о распределении предметов по ящикам (дискретно), усреднение — о числовых характеристиках объектов. В задаче про рёбра графа прямое применение Дирихле не работает. → Как избежать: если в задаче нужна нижняя оценка через частное $S/N$ — это усреднение.
• Ошибка: сделать вывод «среднее = $M$, значит все объекты $\geq M$» → Почему неверно: из среднего следует лишь существование одного объекта $\geq M$, но не то, что все такие. → Как избежать: формулируй вывод точно: «найдётся хотя бы один объект с...».
• Ошибка: вычислить среднее неверно → Использовать не ту суммарную характеристику или не то количество объектов. → Как избежать: явно запиши $S = \sum x_i$ и $N$ = число слагаемых; убедись, что они относятся к одним и тем же объектам.
• Ошибка: применить усреднение, когда суммарное значение трудно вычислить → Метод работает, только если $S$ можно найти явно или через двойной счёт. → Как избежать: сначала убедись, что умеешь вычислить $S$, и только потом делай вывод о среднем.
• Ошибка: не указать, что найденный объект конкретен → «Есть объект с...» — нужно обосновать, что он существует, а не просто среднее такое. → Как избежать: явно сослаться на принцип среднего: «так как среднее $> M$, найдётся объект со значением $> M$».