Метод крайнего — олимпиадный приём: в конечном наборе выбирают объект с самым большим или самым маленьким значением подходящей величины и используют то, что «дальше» в этом направлении объекта уже нет. Приём законен только после выбора величины и объяснения, почему у неё действительно есть максимум или минимум.
Представьте ряд карточек с числами. Пока взгляд скользит по середине ряда, задача кажется общей. Но стоит взять самую большую карточку, и у неё появляется особое свойство: в этом наборе уже нет карточки правее по числовой шкале. Это не ответ само по себе, а точка, из которой можно начать доказательство.
Что именно нужно выбрать
Крайним может быть не только число. В задаче это бывает самая длинная цепочка, самая левая точка, наименьший остаток или позиция, после которой уже нельзя сделать ход. Сначала назовите величину: длину, число, координату, количество ходов. Для непустого конечного набора сравнимых значений максимум и минимум существуют. Если набор бесконечен, отдельно докажите, что нужное крайнее значение достигается: одной ограниченности недостаточно.
Если множество бесконечно, фраза «возьмём наибольшее» может быть ошибкой. Среди всех натуральных чисел наибольшего нет. Иногда вместо максимума подходит минимум, а иногда нужен другой приём. Эта проверка отличает доказательство от удачной на вид догадки.
Разбор 1: наибольшее число и делители
Задача. В непустом конечном наборе различных положительных целых чисел докажите, что найдётся число, которое не делит ни одно другое число из этого набора.
Решение. Возьмём наибольшее число M. Если бы M делило другое число N из набора, то N = kM при натуральном k. Так как N отличается от M, k не равно 1, значит k не меньше 2 и N больше M. Это невозможно: M выбрано наибольшим. Следовательно, M не делит ни одного другого числа набора.
Здесь важно не перепутать направление. Для утверждения «M не делит другое положительное число из набора» полезен максимум: каждый другой положительный кратный M имеет вид kM при натуральном k ≥ 2 и потому больше M. Минимум в этой задаче такого свойства не даёт.
Разбор 2: почему убывающая игра заканчивается
Задача. На доске написано положительное целое число. За ход его разрешается заменить любым меньшим положительным целым числом. Может ли игра продолжаться бесконечно?
Решение. Нет. После каждого хода число строго уменьшается, но оставаться положительным обязано. Если стартовать с 11, возможны не более 10 уменьшений хотя бы на единицу, прежде чем появится 1; из 1 хода уже нет. Нижняя граница 1 не позволяет строить бесконечную строго убывающую цепочку положительных целых чисел.
Этот пример показывает границу аналогии: здесь не выбирают крайний объект из готового набора, а следят за величиной, которая не может уменьшаться бесконечно. Общая идея та же: крайнее значение блокирует невозможное продолжение.
Проверьте ход мысли
В задачах ниже сначала назовите крайнюю величину, а уже затем открывайте решение. Это небольшая практика без регистрации: она тренирует именно выбор объекта, а не угадывание финального ответа.
Для каждого задания сначала предскажите ответ и причину, затем раскройте подсказку и решение. Задания работают без JavaScript.
1. В наборе {3, 6, 10, 15} какое число метод крайнего гарантированно предлагает выбрать, чтобы доказать: оно не делит другое число набора?
Подсказка. Выберите число, больше которого в наборе ничего нет.
Ответ: 15. Это максимум. Каждый другой положительный кратный 15 имеет вид k · 15 при натуральном k ≥ 2, поэтому не меньше 30 и не лежит в наборе. Числа 6 и 10 здесь тоже не делят другие элементы, но это отдельная проверка данного набора, а не гарантированный выбор метода крайнего; число 3 делит 6 и 15.
2. Почему нельзя начать доказательство фразой «возьмём наибольшее натуральное число»?
Ответ: среди всех натуральных чисел нет наибольшего. Нужно ограничить набор или выбрать величину, для которой доказано существование максимума либо минимума.
3. Стартуем с 8; каждый ход заменяет число на меньшее положительное целое. Какое наибольшее число ходов возможно?
Ответ: 7. Самая длинная цепочка — 8, 7, 6, 5, 4, 3, 2, 1. Каждый ход уменьшает число хотя бы на 1, поэтому длиннее цепочки быть не может.
Как заметить приём в новой задаче
Ищите слова «конечный», «самый», «последний», «минимальный», «невозможно продолжать». Они не гарантируют метод крайнего, но подсказывают вопрос: какое значение окажется особенным на границе и какое противоречие появится, если попытаться выйти за неё? Сначала ответьте на этот вопрос в черновике, потом пишите доказательство целиком.
Тренировать стратегии рассуждения в курсе «Основы олимпиадной математики». Курс собирает разные олимпиадные приёмы и задачи; ссылка не обещает отдельный урок именно о методе крайнего.