E14b Явное построение примера (конструкция)

Идея метода: в задачах жанра «оценка + пример» вторая часть — явное построение (конструкция) объекта, достигающего оптимума, — является полноценной половиной решения. Метод E14b — это искусство придумывать примеры, которые:
1. удовлетворяют всем условиям задачи,
2. достигают заявленного оптимального значения показателя.

Часто именно пример — самая сложная часть задачи. Оценку можно получить общим рассуждением, а конструкция требует озарения. Хороший пример обычно выглядит «красиво»: симметричен, регулярен, имеет явную закономерность.

Метод обучает ключевому олимпиадному навыку: не бояться «угадывать» ответ, строить кандидата, проверять, что он подходит, и корректировать. Это итеративный процесс: сначала маленькие случаи, потом обобщение, потом верификация.

Сравни с E14a: там мы доказываем оценку алгебрически; здесь мы строим пример, который эту оценку «закрывает снизу» (для максимума) или «закрывает сверху» (для минимума).

• Принцип явного построения. Для доказательства «существования» объекта с некоторым свойством достаточно явно его предъявить и проверить все условия. Никакого дополнительного аргумента не нужно. Применять: всегда, когда задача просит «докажите, что существует» или требует нижней/верхней оценки через пример.

• Принцип симметрии в конструкциях. Оптимальный пример часто максимально симметричен. Применять: если не знаешь, с чего начать — попробуй равномерное/симметричное распределение.

• Рекуррентная конструкция. Если для $n-1$ пример построен, попробуй расширить его до $n$: добавить один объект «правильным образом». Применять: когда задача параметрическая (для всех $n$) и ответ монотонен по $n$.

• Стартуй с маленьких случаев: проверь $n = 1, 2, 3, 4$, нарисуй явно — часто ответ виден сразу.
• Попробуй «самый простой» кандидат: константный, периодический, чередующийся, арифметическая/геометрическая прогрессия.
• Ищи симметричный пример: часто оптимум достигается при максимальной симметрии (все элементы равны, расположены равномерно).
• Строй рекурсивно: если для $n$ пример построен с ответом $f(n)$, добавь структуру для $n+1$ и убедись, что $f(n+1) = f(n) + \Delta$.
• Используй экстремальный объект: возьми «самый крайний» допустимый вариант и проверь — часто он и есть оптимум.
• Проверяй ВСЕ условия задачи явно для своего примера — не «по понятным причинам», а пункт за пунктом.

Поверхностные признаки (что буквально написано):
- «приведите пример», «существует ли», «построить конструкцию»
- «докажите, что возможно», «покажите, что значение $k$ достижимо»
- «при каком наибольшем $n$ существует» (вторая часть — это пример с таким $n$)

Структурные признаки (форма выражения, объекты):
- Задача просит нижнюю оценку (достижимость максимума) или верхнюю (достижимость минимума)
- Уже есть оценка, нужно её «закрыть» примером
- Задача двухчастная: доказать невозможность + показать возможность

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

Задача 1. Последовательность с нужной суммой

Условие: Существует ли последовательность из 9 различных натуральных чисел, сумма которых равна 100?

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что вижу? «Существует ли» — задача на существование. Нужно либо привести пример, либо доказать, что нет.$2. *$Метод:$* E14b$ — строим явный пример.$3. *$Угадываю кандидата:$* 9$ наименьших различных натуральных чисел: $1+2+\ldots+9 = 45$. Нужно 100. Разница: $100 - 45 = 55$. Могу заменить 9 на $9 + 55 = 64$: числа $1, 2, 3, 4, 5, 6, 7, 8, 64$ — все различны!$4. *$Проверяю:* $1+2+3+4+5+6+7+8+64 = 36+64 = 100$. Все различные натуральные. Работает!

Решение:
Пример: $1, 2, 3, 4, 5, 6, 7, 8, 64$. Эти 9 чисел попарно различны (все натуральные, очевидно различны). Их сумма $= (1+2+\ldots+8)+64 = 36+64 = 100$.

Ответ: Да, существует. Пример: $\{1,2,3,4,5,6,7,8,64\}$.

Что главное: Стартуй с «базового» примера ($1,2,\ldots,9$), посчитай его сумму, найди разницу и скорректируй один элемент.

Задача 2. Расстановка на доске

Условие: Можно ли расставить числа $1, 2, \ldots, 9$ в клетках доски $3 \times 3$ так, чтобы суммы в каждой строке были равны?

Источник: тренировочная (магический квадрат)

Как думать (рассуждение ученика$):
1. $Что вижу? «Можно ли» → задача на существование. Нужна конструкция.$2. *$Проверяю возможность: сумма всех чисел $= 45$, строк 3, значит каждая строка должна иметь сумму $45/3 = 15$. Условие — суммы равны, не сказано про столбцы и диагонали.$3. *$Строю: нужно разбить $\{1,\ldots,9\}$ на 3 тройки с суммой 15. Например: $\{1,5,9\}$, $\{2,6,7\}$, $\{3,4,8\}$. Ставим в строки: строка 1 = $(1,5,9)$, строка 2 = $(2,6,7)$, строка 3 = $(3,4,8)$.$4. *$Проверяю:* суммы строк $1+5+9=15$, $2+6+7=15$, $3+4+8=15$. Все числа от 1 до 9 использованы по одному разу.

Решение:$$\begin{pmatrix} 1 & 5 & 9 \\ 2 & 6 & 7 \\ 3 & 4 & 8 \end{pmatrix}$$ Суммы строк: $15, 15, 15$.

Ответ: Да, можно. Пример выше.

Что главное: Сначала проверить, что условие совместимо (сумма делится на 3), потом явно построить разбиение на равные по сумме части.

• Ошибка: не проверить пример явно. «Интуитивно понятно, что подходит» — недостаточно. Нужно проверить каждое условие задачи. → Как избежать: пройдись по всем условиям задачи пошагово для своего примера.
• Ошибка: пример не достигает заявленного оптимума. Показываешь пример с показателем $M-1$ вместо $M$. → Как избежать: явно посчитай значение показателя в примере перед тем, как писать ответ.
• Ошибка: пример слишком частный. Если задача параметрическая (для всех $n$), один пример при $n=5$ не доказывает ничего для других $n$. → Как избежать: строй пример для общего $n$, указывая явную формулу конструкции.
• Ошибка: написать «аналогично строится» без деталей. На олимпиаде нужна полная конструкция или явная рекуррентная формула. → Как избежать: либо дай формулу, либо опиши алгоритм построения шаг за шагом.
• Ошибка: пример нарушает одно из условий задачи. Забытое условие «все числа различны» или «ребро соединяет только несмежные вершины». → Как избежать: выпиши все условия на листе и проверяй по чеклисту.