В задаче спрашивают наибольшее число объектов, минимальное количество действий или лучший возможный результат. Найти удачную конструкцию приятно, но она еще не доказывает оптимальность. Нужно показать, что улучшить результат нельзя. Метод “оценка плюс пример” соединяет эти две части и помогает заранее понять, какого доказательства пока не хватает.
Две части отвечают на разные вопросы
Верхняя оценка говорит, что результат не может превышать некоторое число. Конструкция показывает, что это число достигается. Для минимума направление меняется: сначала доказывают нижнюю границу, затем предъявляют допустимый объект с таким результатом. Порядок поиска может быть любым, но в завершенном решении нужны обе части.
Если удалось построить вариант с двенадцатью объектами и доказать, что их не больше четырнадцати, задача еще не решена. Максимум находится между этими числами. Этот промежуток полезен: он показывает, нужно ли улучшать конструкцию или усиливать ограничение, вместо бесконечного повторения уже известных рассуждений.
Простой пример на последовательности
Какое наибольшее количество чисел можно выбрать из 1, 2, …, 10, чтобы среди выбранных не было соседних? Разбейте числа на пары: (1, 2), (3, 4), (5, 6), (7, 8), (9, 10). Из каждой пары разрешено взять не больше одного числа, поэтому получится не больше пяти.
Теперь предъявите набор 1, 3, 5, 7, 9. В нем действительно нет соседних чисел и ровно пять элементов. Верхняя граница достигнута, значит максимум равен пяти. Пары дали оценку, а конкретный набор подтвердил ее точность. Ни одна из этих частей отдельно не обеспечивает полный ответ.
Откуда брать полезные оценки
Часто помогают разбиение на группы, подсчет одного объекта несколькими способами, принцип Дирихле или ограничение общей суммы. Прежде чем применять прием, спросите, какое свойство имеет любой допустимый вариант. Оценка должна охватывать все возможные конструкции, включая те, которые вы еще не пробовали рисовать.
Если используете разбиение, объясните, почему оно покрывает все объекты и сколько разрешено выбрать из каждой части. Если считаете суммарный ресурс, проверьте, не расходуется ли он дважды. Ошибки здесь нередко маскируются убедительным рисунком и проявляются только при разборе небольшого исключительного случая.
Как улучшать конструкцию
Начните с маленьких значений параметра, выпишите результаты и попробуйте обнаружить повторяющийся принцип. Затем замените картинку описанием, которое работает для произвольного размера. Например, выбор всех нечетных чисел задается правилом и не требует перечислять сотню элементов вручную.
При подборе занятий можно узнать программу смен и сопоставить предлагаемые задачи со своим уровнем. Особенно полезна обратная связь по доказательству оптимальности: верный ответ иногда получается раньше, чем корректное обоснование.
Как оформлять окончательный ответ
Отдельно сформулируйте ограничение и отдельно опишите достигающий его пример. Проверьте все требования условия для конструкции, а не только нужное количество элементов. В задачах с параметром разберите четные и нечетные значения, если правило меняется. Такая запись делает видимым главный результат: граница не только доказана, но и достижима.
