Это не магия, а мощный приём — «принцип крайнего» (или экстремальный принцип). Он не решает задачу за вас, но указывает пальцем на того, с кого нужно начать думать. И этот «кто-то» всегда выделяется: он самый большой, самый маленький, первый по алфавиту, ближайший к точке — в общем, крайний.
Этот принцип — одно из любимых оружий олимпиадников и гениев комбинаторного мышления, от Эйлера до Эрдёша. Он превращает хаотичную проблему в упорядоченную, находя в ней «пешку», которую можно сдвинуть первой.
Эйлер и Эрдёш — те, кто виртуозно владел принципом крайнего.
Часть 1: Суть принципа: найдите того, кто выделяется
Задачи, где работает принцип крайнего, часто выглядят так: «Дано много объектов (точек, людей, чисел) с какими-то свойствами. Докажите, что найдётся объект с нужным свойством».
Стратегия проста до гениальности:
- Введите разумный порядок. Выберите критерий, по которому можно сравнить все объекты: «ближайший к точке O», «самый левый», «человек с наибольшим числом друзей», «наименьшее число».
- Выберите крайний объект. Тот, который максимизирует или минимизирует этот критерий.
- Изучите его. Из-за его «крайности» его свойства часто оказываются именно теми, которые нужны для решения. Он — ключ ко всей системе.
Это не алгоритм, а принцип мышления. Вы не вычисляете ответ, а находите идеальную точку для атаки на задачу.
Ищем самую удаленную точку, чтобы понять всю фигуру.
Часть 2: Разбираем на примерах: от абстракции к конкретике
1. Ладьи на шахматной доске:
На шахматной доске расставленны ладьи. Докажите, что некоторая ладья бьёт не более двух.
Решение: Вообще говоря, каждая ладья может бить не больше четырех других. Но давайте применим принцип крайнего и увеличим количество информации о наших фигурах. Рассмотрим самую левую ладью. Назовём её Л. Левее нее фигур нет, поэтому она бьет не более трех фигур.
Теперь давайте еще раз применим принцип крайнего и среди всех самых левых возьмем самую верхнюю ладью. Смотрим, кого она бьёт: других ладей на её вертикали (ниже её) и на её горизонтали (правее её). Может показаться, что их может быть много. Но вот загвоздка!
Ладья Л — самая левая из всех. Значит, левее неё ладей нет вообще. А если она к тому же самая верхняя в своём столбце — то выше неё в этом столбце тоже никого нет.
Таким образом, наша "крайняя" ладья Л не может бить 3 или более ладей. Значит, она бьёт не более двух. Экстремальный объект (самая левая-верхняя ладья) помог найти искомую фигуру.
2. Классическая задача:
В комнате стоят N человек. Докажите, что среди них найдутся два человека с одинаковым числом знакомых в этой комнате.
Решение: Кажется, что все могут знать разное количество людей. Но давайте применим принцип крайнего. Рассмотрим человека с наибольшим числом знакомых (пусть он знает M человек). И человека с наименьшим числом знакомых (пусть он знает m человек).
Теперь смотрим на возможные значения: каждый из N человек может знать от 0 до (N-1) других. Но здесь загвоздка! Если в комнате есть человек, который знает 0 человек (знакомств нет), то не может быть человека, который знает N-1 (всех), потому что он должен был бы знать и этого отшельника. И наоборот.
Таким образом, экстремумы 0 и N-1 не могут существовать одновременно. Значит, реальное количество знакомств у людей лежит в диапазоне либо от 0 до (N-2), либо от 1 до (N-1). В любом случае, возможных «номеров» (разных количеств знакомств) — всего (N-1). А людей — N. По принципу Дирихле (еще одна прекрасная идея!) как минимум у двоих количество знакомств будет одинаковым. Экстремальный объект (самый общительный или самый необщительный) помог сузить условия.
Это результат можно переформулировать на языке теории графов - мы доказали, что в любом графе существуют две вершины одинаковой степени. То есть обязательно найдутся две вершины из которых выходят одинаковое количество отрезков.
Заключение
Принцип крайнего — это философия решения задач. Он напоминает, что в любом хаосе есть точка опоры, а в любом множестве — элемент, с которого логично начать. Это мост между детской наблюдательностью («а вот этот самый большой!») и мощью взрослой математической логики.
P.S. (для особенно любопытных): Возьмите несколько монет, разбросайте их на столе и найдите самую левую. Теперь попробуйте представить все прямые, которые можно провести через пары монет. Чем выделена «крайняя» прямая, проходящая через эту левую монету? Вы только что прикоснулись к тому же мышлению, которое решает сложнейшие комбинаторные проблемы. Магия порядка в ваших руках.
Предлагаю задачи, пишите ответы или вопросы в комментарии:
👉 Подписаться на Telegram-канал
- На окружности расставлено 10 различных натуральных чисел. Всегда ли найдутся три последовательных числа, сумма которых больше 11?
- В некоторой галактике 2003 планеты. На каждой из них сидит астроном и наблюдает за ближайшей к нему планетой этой галактики. Все расстояния между планетами различны. Докажите, что хотя бы за одной из планет никто не наблюдает.
#принципкрайнего #олимпиаднаяматематика #комбинаторика #логика #решениезадач #математическоемышление #этоинтересно