E9 Экстремальный принцип

Идея метода: рассмотрим экстремальный объект — самый большой, самый маленький, самый далёкий, с наибольшим значением какого-то параметра. Из того, что он экстремальный, вытекают сильные ограничения на его «соседей» и связи, которые позволяют сделать нужный вывод.

Метод состоит в следующем: выбираем объект, максимизирующий (или минимизирующий) заданную характеристику. Затем рассуждаем: «раз этот объект — самый большой, у его соседей нет права быть ещё больше». Это противоречие или необходимое свойство — и есть доказательство.

Аналогия: если вы ищете самого высокого человека в очереди и смотрите на его соседей — они ниже. Из этого можно сделать нелривиальные выводы о структуре очереди.

Экстремальный принцип — один из самых частых методов на ВсОШ (частота 7), потому что он применим в геометрии, комбинаторике, алгебре и теории чисел — везде, где есть порядок и сравнение.

• Принцип наименьшего элемента (в $\mathbb{N}$): Любое непустое подмножество натуральных чисел имеет наименьший элемент. Когда использовать: предположили, что решений нет или конструкция бесконечна — получаем бесконечный убывающий процесс, противоречие.

• Принцип экстремальной точки в конечном множестве: В любом конечном непустом множестве есть максимальный (и минимальный) элемент. Когда использовать: рассматриваем «самую дальнюю» точку, «самый большой» элемент набора.

• Принцип граничного объекта: Если взять объект с максимальной характеристикой, то все «ходы» из него (переходы к соседям) не увеличивают характеристику. Это ограничение на соседей. Когда использовать: задачи о графах, последовательностях, геометрических конфигурациях.

• Метод бесконечного спуска: Предполагаем, что есть решение $x_1$. Конструируем меньшее решение $x_2 < x_1$. Получаем бесконечную убывающую последовательность натуральных чисел — противоречие. Когда использовать: доказательства неразрешимости диофантовых уравнений, иррациональности чисел.

• Выбор точки/элемента с максимальным значением: фиксируем элемент $x^* = \arg\max f(x)$ и рассматриваем всех его «соседей»: все они имеют $f \leq f(x^*)$. Это ограничение используется для доказательства.

• Выбор крайней точки в геометрии: берём точку, наиболее удалённую от прямой / с наибольшей координатой. Из экстремальности выводим, что прямая/полуплоскость «отделяет» эту точку от других.

• Рассмотрение минимального контрпримера: предположим, что утверждение неверно. Берём минимальный контрпример. Показываем, что он не может быть минимальным (существует меньший контрпример). Противоречие.

• Рёбро максимального (минимального) веса в графе: в задачах о деревьях и путях выбор ребра с экстремальным весом часто позволяет охарактеризовать структуру.

• Бесконечный спуск: строим убывающую последовательность натуральных чисел — это невозможно, значит исходное предположение неверно.

• Точка с максимальной суммой соседей: в задачах о функциях на множествах выбираем вершину графа с максимальным значением — все её соседи имеют меньшее значение.

Поверхностные признаки (что буквально написано):
- «Докажите, что некоторый элемент имеет такое-то свойство».
- «Найдите наибольшее/наименьшее значение».
- «Рассмотрите элемент с наибольшим/наименьшим значением X».

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

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

Задача 1. Точка с наибольшим числом соседей (ВсОШ-стиль)

Условие: В стране $n \geq 2$ городов. Из каждого города выходит хотя бы одна дорога. Докажите, что найдётся город $A$ такой, что из каждого города, из которого есть дорога в $A$, есть дорога хотя бы ещё в один город с не меньшим числом дорог, чем у $A$.

Источник: тренировочная (уровень ВсОШ-9)

Как думать (рассуждение ученика$):
1. $Что вижу? Граф, дороги. Нужно доказать существование города с особым свойством. Триггер: экстремальный принцип — беру город с максимальной степенью.$2. *$Первый ход: пусть $A$ — город с наибольшим числом дорог (степенью $d$). Если таких городов несколько, беру любой.$3. *$Рассуждение: пусть $B$ — любой город, соединённый с $A$. Так как $A$ — максимальный по степени, $\deg(B) \leq \deg(A)$. Нам нужно, что у $B$ есть сосед с $\deg \geq \deg(A) = d$. Сам $A$ — сосед $B$ со степенью $d$. Готово!

Решение:

Пусть $A$ — город с максимальной степенью (числом дорог) $d$. Пусть $B$ — произвольный город, из которого есть дорога в $A$. Тогда $A$ является соседом $B$ и $\deg(A) = d \geq \deg(B)$ (так как $A$ максимален). Значит, среди соседей $B$ есть город $A$ с числом дорог $\geq \deg(B)$. Что и требовалось.

Ответ: Такой город $A$ — это город с максимальной степенью.

Что главное: экстремальный объект «обслуживает» всех своих соседей одним своим фактом — быть максимальным.

Задача 2. Бесконечный спуск (иррациональность)

Условие: Докажите, что $\sqrt{2}$ иррационально.

Источник: классическая задача (метод бесконечного спуска, Евклид)

Как думать (рассуждение ученика$):
1. $Что вижу?* Нужно доказать, что $\sqrt{2}$ нельзя представить в виде дроби. Способ «от противного».$2. *$Первый ход: предположим $\sqrt{2} = \frac{p}{q}$ несократимая дробь, $p, q \in \mathbb{N}$.$3. *$Экстремальный принцип (бесконечный спуск$):*$ рассмотрим наименьшее такое $q$. Покажем, что существует меньший знаменатель — противоречие.$4. *$Альтернатива (стандартное доказательство$):*$ $2q^2 = p^2 \Rightarrow p$ чётное $\Rightarrow p = 2p_1 \Rightarrow 2q^2 = 4p_1^2 \Rightarrow q$ чётное. Противоречие с несократимостью.

Решение:

Предположим, что $\sqrt{2} = \frac{p}{q}$, где $p, q \in \mathbb{N}$ и дробь несократима (т.е. $\gcd(p,q)=1$). Тогда $p^2 = 2q^2$, значит $p^2$ чётно, а значит $p$ чётно: $p = 2k$. Подставляем: $(2k)^2 = 2q^2$, $4k^2 = 2q^2$, $q^2 = 2k^2$ — значит $q$ тоже чётно. Но тогда $\gcd(p,q) \geq 2$ — противоречие с несократимостью дроби.

Ответ: $\sqrt{2}$ иррационально.

Что главное: «минимальный знаменатель» — это экстремальный объект. Из его существования получаем меньший — противоречие.

• Ошибка: «взяли максимум» без указания, что он существует. В конечном множестве максимум всегда есть — но нужно это оговорить. В бесконечном — нет. Как избежать: явно укажите, что множество конечно (или ограничено снизу в $\mathbb{N}$).

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

• Ошибка: при бесконечном спуске не доказывают, что новое решение строго меньше. Нужно явно показать неравенство $x_2 < x_1$, а не «уменьшили». Как избежать: выпишите явную конструкцию нового (меньшего) объекта с доказательством неравенства.

• Ошибка: забывают рассмотреть случай равенства. Если максимальных объектов несколько, рассуждение часто работает для любого из них — но это нужно проверить. Как избежать: при выборе «максимального» объекта добавьте «если таких несколько — выберем любой» и проверьте, что рассуждение не зависит от выбора.

• Ошибка: применяют «минимальный контрпример» к задаче без понятного понятия «меньше». Метод требует линейного порядка. Как избежать: явно укажите, по какому параметру измеряется «меньше» (число вершин, сумма, значение функции).