E14 Оценка + пример (главный жанр ВсОШ)

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

Часть 1 — Оценка: доказать, что показатель не может превышать (быть меньше) некоего значения $M$. Это означает: для ЛЮБОЙ конфигурации, удовлетворяющей условиям, показатель $\leq M$ (или $\geq M$). Оценка — это доказательство невозможности превзойти $M$.

Часть 2 — Пример: явно построить конфигурацию, в которой показатель равен $M$. Это доказывает достижимость. Без примера мы знаем лишь верхнюю границу, но не знаем, достигается ли она.

Почему нужны оба? Ответ «не более 5» без примера может означать, что настоящий ответ — 4 или даже 3. Ответ «вот пример с 5» без оценки не доказывает, что 6 невозможно. Только вместе оценка и пример образуют полное решение.

На ВсОШ задачи этого типа составляют около 47 из тестируемых задач. Типичная формулировка: «какое наибольшее число X можно Y при условии Z?» Ловушка для неопытных: дать пример с большим значением и объявить его ответом, забыв про оценку — или наоборот, доказать оценку, но не показать, что она достигается.

Самые популярные идеи в E14

Идея 1. Разбиение на пары, тройки и блоки

Если условие запрещает брать два объекта вместе, попробуй разбить все объекты на блоки, внутри которых много взять нельзя.

Пример мышления:

• В каждой паре можно взять не больше одного.
• В каждом блоке из трёх можно взять не больше двух.
• В каждой строке можно взять не больше \(k\).
• В каждой цепочке можно взять не больше половины с округлением.

Так рождается верхняя оценка.

После этого конструкция обычно зеркальная: взять из каждого блока максимально возможное количество.

Идея 2. Цепочки

Если запрещено, чтобы два числа отличались на фиксированное число, надо смотреть не на обычный порядок чисел, а на цепочки по этому шагу.

Например, запрет «два числа не отличаются на 11» превращает числа в цепочки:

\[ 1,12,23,34,\ldots \]

\[ 2,13,24,35,\ldots \]

и так далее. В каждой цепочке нельзя брать соседние элементы. Значит, максимум в цепочке длины \(L\) равен \(\lceil L/2 \rceil\).

Это мощный приём. Он встречается в задачах про числа, клетки, маршруты, отрезки и даже расписания.

Идея 3. Ограничение через сумму

Иногда максимум ограничивается общей суммой. Если каждый объект даёт вклад хотя бы \(a\), а общая сумма равна \(S\), то объектов не больше \(S/a\). Если каждый объект требует хотя бы одну «потерю», а потерь всего \(P\), то объектов не больше \(P\).

Этот ход часто работает в задачах про углы, деньги, веса, баллы, длины, площади.

Идея 4. Инвариант и остатки

Если действие меняет систему, но какая-то величина сохраняется, это почти готовая оценка. Особенно часто работают:

• чётность;
• остаток по модулю 3, 4, 5, 11;
• сумма по модулю;
• раскраска клеток;
• количество объектов одного типа минус количество объектов другого типа.

Инвариант говорит: «ты хочешь прийти к такой конфигурации, но она имеет другой остаток, значит нельзя».

Идея 5. Двойной счёт

Если каждый объект связан с несколькими другими объектами, можно посчитать связи двумя способами. Это даёт ограничение.

Типовые фразы:

• «посчитаем пары»;
• «посчитаем инцидентности»;
• «каждая клетка входит в столько-то блоков»;
• «каждый участник проигрывает не более одного раза»;
• «каждое ребро учитывается дважды».

Двойной счёт часто работает рядом с E14: сначала получаем оценку, потом строим пример, где все неравенства превращаются в равенства.

Идея 6. Крайний объект

Выбери самый левый, самый маленький, самый большой, самый ранний, самый длинный или самый тяжёлый объект. Часто крайний объект вынуждает структуру вокруг себя.

Пример: если выбран самый маленький запрещённый элемент, то рядом с ним должны отсутствовать какие-то элементы. Если выбран самый длинный интервал, остальные интервалы должны пересекаться с ним особым образом.

Это особенно полезно, когда разбиение на блоки сразу не видно.

Идея 7. Жадная конструкция

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

Но жадность опасна. Нельзя просто сказать «будем брать жадно». Нужно доказать, что итог не нарушает условие и достигает нужного количества.

---

Как распознать E14

Метод почти всегда прячется за словами:

• «наибольшее количество»;
• «наименьшее количество»;
• «максимально возможное»;
• «минимально возможное»;
• «найдите все значения, которые могут быть»;
• «докажите, что можно, и что лучше нельзя»;
• «оцените и приведите пример».

Но есть ловушка. Иногда в условии нет слов «максимум» или «минимум», а задача всё равно решается через E14. Например, если нужно доказать существование конфигурации или невозможность слишком хорошего результата, внутри решения всё равно появятся две части: ограничение и конструкция.

---

Базовый алгоритм решения

Шаг 1. Понять, что оптимизируем

Сначала нужно чётко назвать величину. Не «что-то побольше», а конкретно:

• количество выбранных чисел;
• количество матчей;
• число клеток одного цвета;
• длина маршрута;
• число предметов, которые можно оставить;
• максимальное \(n\);
• минимальное число операций.

Пока величина не названа, оценку строить рано.

Шаг 2. Угадать ответ на маленьких случаях

Перед строгим доказательством полезно решить маленькие версии задачи:

• вместо \(1,\ldots,321\) взять \(1,\ldots,20\);
• вместо доски \(11 \times 10\) взять \(3 \times 4\);
• вместо 100 монет взять 10;
• вместо \(n\)-угольника посмотреть на пятиугольник или десятиугольник.

Цель маленьких случаев: увидеть структуру. Часто ответ рождается не из формулы, а из рисунка.

Шаг 3. Доказать ограничение

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

• разбить объекты на группы, где из каждой группы можно взять не больше одного или не больше половины;
• посчитать одну и ту же величину двумя способами;
• применить принцип Дирихле;
• использовать чётность или остатки;
• выбрать самый большой, самый маленький или самый крайний объект;
• заменить сложную конфигурацию на цепочки, пары, блоки или интервалы.

Шаг 4. Построить пример

После оценки нужно построить конфигурацию, которая достигает границы. Конструкция должна быть понятной и проверяемой.

Плохая конструкция: «можно подобрать».

Хорошая конструкция: «возьмём все числа такого вида», «раскрасим строки периодом 1,2,3», «разобьём на цепочки и в каждой цепочке возьмём элементы с нечётными номерами».

Шаг 5. Проверить, что пример не нарушает условие

Финальная проверка обязательна. В E14 часто ошибаются не в оценке, а в примере: конструкция красивая, но нарушает одно из условий.

Мини-чеклист:

• Все объекты допустимы?
• Количество ровно то, что заявлено?
• Запрещённая ситуация действительно не возникает?
• Если есть максимум, пример достигает максимума?
• Если есть минимум, пример достигает минимума?

---

Карта выбора идеи

Если в задаче есть...	Сначала пробуй...
Запрет на пару объектов	Разбить на пары, цепочки или блоки
Слова «отличаются на \(k\)»	Цепочки с шагом \(k\)
Клетчатая доска	Раскраска, строки/столбцы, блоки \(2\times2\)
Турнир, игры, выбывание	Инвариант прогресса, количество проигрышей, число ходов
Углы, суммы, деньги, веса	Общая сумма и максимальный вклад одного объекта
«Докажите, что всегда найдётся»	Принцип Дирихле или двойной счёт
«Наибольшее количество»	Верхняя оценка плюс конструкция
«Наименьшее количество»	Нижняя оценка плюс пример достижения

---

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

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

Цель задачи (что от тебя хотят):
- Назвать конкретное число $M$ И доказать, что $M$ — точный ответ (оба направления)
- Распознать, что «найти наибольшее» = «оценить + построить пример»
- Не перепутать «привести пример» с «доказать»

Решённый пример 1. Числа от 1 до 321

Задача

Лёша хочет выписать на доске несколько натуральных чисел от 1 до 321 так, чтобы никакие два числа не отличались ровно на 11. Какое наибольшее количество чисел он сможет выписать?

Почему это E14

Спрашивают «наибольшее количество». Значит, нужно:

1. доказать, что больше некоторого числа нельзя;
2. показать, что столько чисел можно выписать.

Оценка

Разобьём числа на цепочки с шагом 11:

\[ 1,12,23,\ldots \]

\[ 2,13,24,\ldots \]

\[ \ldots \]

\[ 11,22,33,\ldots \]

Внутри каждой цепочки соседние числа отличаются ровно на 11. Поэтому нельзя брать два соседних числа одной цепочки.

Теперь посмотрим на длины цепочек. Чисел от 1 до 321 всего 321. Так как \(321=11\cdot29+2\), две цепочки имеют длину 30, а девять цепочек имеют длину 29.

В цепочке длины 30 можно взять не больше 15 чисел. В цепочке длины 29 можно взять не больше 15 чисел. Значит, всего можно взять не больше:

\[ 2\cdot15+9\cdot15=165. \]

Получили верхнюю оценку: больше 165 нельзя.

Пример

В каждой цепочке возьмём числа через одно: первое, третье, пятое и так далее.

Например, из цепочки

\[ 1,12,23,34,\ldots \]

возьмём

\[ 1,23,45,\ldots \]

Тогда в одной цепочке никакие два выбранных числа не соседние, значит они не отличаются на 11. Из разных цепочек числа тоже не отличаются на 11, потому что числа, отличающиеся на 11, всегда лежат в одной такой цепочке.

Мы взяли 15 чисел из каждой из 11 цепочек, всего:

\[ 11\cdot15=165. \]

Ответ

\[ 165 \]

Что надо запомнить

Запрет «отличаются на фиксированное число» почти всегда просит разбить числа на цепочки по этому шагу.

---

Решённый пример 2. Турнир на выбывание

Задача

В турнире по боксу участвуют 27 человек. Каждый матч заканчивается победой одного из участников. Турнир идёт на выбывание: проигравший выбывает. Сколько матчей нужно провести, чтобы определить победителя?

Идея

Здесь не нужно строить сложную таблицу турнира. Главное заметить, что каждый матч создаёт ровно одного проигравшего, а чтобы остался один победитель, должны выбыть остальные 26 участников.

Оценка

За один матч выбывает ровно один человек. Чтобы из 27 участников остался 1, нужно убрать 26 человек. Поэтому меньше 26 матчей невозможно.

Пример

Проводим турнир любым способом: каждый раз выбираем двух ещё не выбывших участников, проигравший выбывает. После 26 матчей выбыли 26 человек, остался один победитель.

Ответ

\[ 26 \]

Что надо запомнить

Иногда оценка строится не на сложной формуле, а на «единице прогресса»: один матч даёт ровно одно выбывание.

---

Решённый пример 3. Углы многоугольника

Задача

В выпуклом \(n\)-угольнике каждый угол составляет целое число градусов. Известно, что два угла равны \(63^\circ\) и \(97^\circ\). Какое наибольшее значение может принимать \(n\)?

Идея

Снова максимум. Нужно понять, что ограничивает число сторон. У выпуклого многоугольника каждый внутренний угол меньше \(180^\circ\). Так как углы целые, каждый из остальных углов не больше \(179^\circ\).

Оценка

Сумма углов \(n\)-угольника равна:

\[ 180(n-2). \]

Два угла уже равны \(63^\circ\) и \(97^\circ\), их сумма:

\[ 63+97=160. \]

Остальных углов \(n-2\), каждый не больше \(179^\circ\). Значит, вся сумма углов не больше:

\[ 160+179(n-2). \]

Но она должна быть равна \(180(n-2)\). Поэтому:

\[ 180(n-2)\le 160+179(n-2). \]

Раскрываем:

\[ 180n-360\le 179n-198. \]

Отсюда:

\[ n\le 162. \]

Получили оценку: больше 162 сторон быть не может.

Пример

Построим выпуклый 162-угольник с углами:

• \(63^\circ\);
• \(97^\circ\);
• остальные 160 углов равны \(179^\circ\).

Проверим сумму:

\[ 63+97+160\cdot179=28800. \]

А сумма углов 162-угольника:

\[ 180(162-2)=180\cdot160=28800. \]

Такой выпуклый многоугольник можно построить, потому что внешние углы будут:

\[ 117^\circ,\ 83^\circ,\ 1^\circ,\ldots,1^\circ, \]

и их сумма равна:

\[ 117+83+160=360^\circ. \]

Ответ

\[ 162 \]

Что надо запомнить

Если величина ограничена сверху, максимум часто достигается, когда почти все элементы «почти максимальные». Здесь остальные углы стали \(179^\circ\), то есть максимально возможными целыми углами выпуклого многоугольника.

---

Лестница задач: 7 семейств E14

Не надо думать, что у E14 всего 5 тем. «Оценка + пример» — это мета-метод, а внутри него есть несколько устойчивых семейств. Для курса FORMYLA лучше дать 7 семейств и в каждом сделать 4 задачи с ростом уровня.

Формат каждой задачи:

• уровень 1: ученик узнаёт идею почти сразу;
• уровень 2: идея та же, но числа менее удобные;
• уровень 3: нужна аккуратная оценка;
• уровень 4: задача ближе к олимпиадной, с маскировкой.

Семейство 1. Запрещённая разность и цепочки

Главный сигнал: в условии сказано, что два выбранных объекта не должны отличаться на фиксированное число \(k\). Почти всегда надо разбить числа на цепочки с шагом \(k\).

Задача 1.1

Из чисел от 1 до 40 нужно выбрать как можно больше чисел так, чтобы никакие два выбранных числа не отличались на 4. Найдите максимум.

Скелет решения: разбить на 4 цепочки:

\[ 1,5,9,\ldots,37;\quad 2,6,10,\ldots,38;\quad 3,7,11,\ldots,39;\quad 4,8,12,\ldots,40. \]

В каждой цепочке длины 10 можно взять не больше 5 чисел. Пример: взять элементы через один.

Ответ:

\[ 20 \]

Задача 1.2

Из чисел от 1 до 100 нужно выбрать как можно больше чисел так, чтобы никакие два выбранных числа не отличались на 7. Найдите максимум.

Скелет решения: есть 7 цепочек по остаткам modulo 7. Две цепочки имеют длину 15, пять цепочек имеют длину 14. В цепочке длины \(L\) можно взять не больше \(\lceil L/2\rceil\).

Ответ:

\[ 2\cdot 8+5\cdot 7=51 \]

Задача 1.3

Из чисел от 1 до 321 нужно выбрать как можно больше чисел так, чтобы никакие два выбранных числа не отличались на 11. Найдите максимум.

Скелет решения: 11 цепочек с шагом 11. Так как \(321=11\cdot29+2\), две цепочки имеют длину 30, девять цепочек имеют длину 29. Из каждой можно взять 15.

Ответ:

\[ 165 \]

Задача 1.4

На доске написаны числа от 1 до 2025. Нужно стереть как можно меньше чисел так, чтобы среди оставшихся никакие два не отличались на 45. Сколько чисел нужно стереть?

Скелет решения: сначала найти максимум оставшихся. Разбиваем на 45 цепочек с шагом 45. В каждой цепочке длины 45 можно оставить не больше 23 чисел. Всего можно оставить \(45\cdot23=1035\). Значит, стереть нужно \(2025-1035=990\).

Ответ:

\[ 990 \]

Семейство 2. Блоки, пары и локальные ограничения

Главный сигнал: условие запрещает плохую ситуацию внутри каждого маленького блока: пары, тройки, квадрата \(2\times2\), нескольких подряд идущих элементов.

Задача 2.1

В ряд стоят 60 клеток. Нужно закрасить как можно больше клеток так, чтобы среди любых трёх подряд идущих клеток была хотя бы одна незакрашенная. Какое максимальное число клеток можно закрасить?

Скелет решения: разбить ряд на 20 блоков по 3 клетки. В каждом блоке можно закрасить не больше 2 клеток. Пример: в каждом блоке закрасить первые две клетки.

Ответ:

\[ 40 \]

Задача 2.2

В ряд стоят 101 клетка. Нужно отметить как можно больше клеток так, чтобы никакие две отмеченные клетки не стояли рядом. Найдите максимум.

Скелет решения: разбить на пары \((1,2),(3,4),\ldots,(99,100)\) и отдельную клетку 101. В каждой паре не больше одной отмеченной, плюс можно отметить 101-ю. Пример: отметить все нечётные клетки.

Ответ:

\[ 51 \]

Задача 2.3

В таблице \(8\times8\) нужно отметить как можно больше клеток так, чтобы никакие две отмеченные клетки не имели общей стороны. Найдите максимум.

Скелет решения: шахматная раскраска. У каждой отмеченной клетки пусть будет один цвет. Если отметить все клетки одного цвета, условие выполнено. Больше 32 нельзя, потому что в каждой горизонтальной паре соседних клеток можно отметить не больше одной, и шахматная раскраска даёт точную границу.

Ответ:

\[ 32 \]

Задача 2.4

В таблице \(5\times5\) нужно отметить как можно больше клеток так, чтобы в каждом квадрате \(2\times2\) было не больше одной отмеченной клетки. Найдите максимум.

Скелет решения: разбить строки на группы \((1,2),(3,4),(5)\), а столбцы так же. Получится 9 прямоугольных блоков. В каждом таком блоке можно отметить не больше одной клетки: если две клетки попали в один блок, они лежат в некотором квадрате \(2\times2\) или вместе с соседней строкой/столбцом образуют такой квадрат. Конструкция: отметить клетки с обеими нечётными координатами.

Ответ:

\[ 9 \]

Семейство 3. Ресурс, сумма и прогресс

Главный сигнал: каждое действие тратит или создаёт фиксированную единицу ресурса. Нужно понять, какой ресурс невозможно ускорить.

Задача 3.1

В турнире на выбывание участвуют 27 человек. Каждый матч заканчивается победой одного участника, проигравший выбывает. Сколько матчей нужно провести, чтобы определить победителя?

Скелет решения: каждый матч даёт ровно одного выбывшего. Чтобы из 27 участников остался 1, должны выбыть 26.

Ответ:

\[ 26 \]

Задача 3.2

В турнире на выбывание участвуют 128 человек. Сколько матчей нужно провести, чтобы определить победителя?

Скелет решения: аналогично, должны выбыть 127 участников.

Ответ:

\[ 127 \]

Задача 3.3

На доске написано число 0. За один ход разрешается увеличить число не больше чем на 3. За какое наименьшее число ходов можно получить число 100?

Скелет решения: за \(m\) ходов можно увеличить число не больше чем на \(3m\). Значит, \(3m\ge100\), откуда \(m\ge34\). Пример: 33 раза прибавить 3 и один раз прибавить 1.

Ответ:

\[ 34 \]

Задача 3.4

В выпуклом \(n\)-угольнике каждый угол выражается целым числом градусов. Два угла равны \(50^\circ\) и \(70^\circ\). Какое наибольшее значение может принимать \(n\)?

Скелет решения: сумма углов равна \(180(n-2)\). Остальные углы не больше \(179^\circ\). Значит:

\[ 180(n-2)\le 50+70+179(n-2). \]

Отсюда \(n\le122\). Пример достигается углами \(50^\circ,70^\circ\) и 120 углами по \(179^\circ\).

Ответ:

\[ 122 \]

Семейство 4. Принцип Дирихле и двойной счёт

Главный сигнал: много объектов распределены по малому числу ящиков, пар, классов, строк, остатков или связей. Оценка возникает из фразы «где-то обязательно много».

Задача 4.1

31 шар разложили по 10 коробкам. Какое наименьшее число шаров гарантированно найдётся в какой-то одной коробке?

Скелет решения: если бы в каждой коробке было не больше 3 шаров, всего было бы не больше 30. Значит, где-то есть хотя бы 4. Пример распределения \(4,3,3,\ldots,3\) показывает точность.

Ответ:

\[ 4 \]

Задача 4.2

Из чисел от 1 до 20 нужно выбрать как можно больше чисел так, чтобы никакие два выбранных числа не давали в сумме 21. Найдите максимум.

Скелет решения: разбить числа на пары:

\[ (1,20),(2,19),\ldots,(10,11). \]

Из каждой пары можно взять не больше одного числа. Пример: взять все числа от 1 до 10.

Ответ:

\[ 10 \]

Задача 4.3

В компании 9 человек каждый сыграл с каждым в шахматы одну партию, ничьих не было. Докажите, что найдётся человек, выигравший не меньше 4 партий. Можно ли гарантировать 5?

Скелет решения: всего партий \(\binom{9}{2}=36\), значит всего побед тоже 36. Среднее число побед равно \(36/9=4\). Поэтому кто-то выиграл хотя бы 4. Гарантировать 5 нельзя: возможен турнир, где каждый выиграл ровно 4 партии.

Ответ:

\[ 4,\quad 5\text{ гарантировать нельзя} \]

Задача 4.4

В таблице \(10\times10\) отмечено 41 клетка. Докажите, что найдётся строка или столбец, где отмечено не меньше 5 клеток.

Скелет решения: если в каждой строке отмечено не больше 4 клеток, то уже по строкам всего не больше 40. Значит, какая-то строка содержит не меньше 5. Эта задача специально показывает, что иногда достаточно одного направления подсчёта, а не всей таблицы.

Ответ:

\[ \text{да, обязательно найдётся} \]

Семейство 5. Раскраски, инварианты и остатки

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

Задача 5.1

На шахматной доске \(8\times8\) нужно поставить как можно больше королей так, чтобы никакие два короля не били друг друга. Найдите максимум.

Скелет решения: разбить доску на 16 квадратов \(2\times2\). В каждом таком квадрате можно поставить не больше одного короля. Пример: поставить королей в левый верхний угол каждого квадрата \(2\times2\).

Ответ:

\[ 16 \]

Задача 5.2

В ряд стоят 50 клеток. За один ход можно отметить одну клетку, но нельзя отмечать клетку, соседнюю с уже отмеченной. Какое максимальное число клеток можно отметить?

Скелет решения: пары соседних клеток дают оценку, пример — все нечётные клетки.

Ответ:

\[ 25 \]

Задача 5.3

На доске \(8\times8\) нужно отметить как можно больше клеток так, чтобы никакие две отмеченные клетки не стояли на одной диагонали направления «северо-запад — юго-восток». Найдите максимум.

Скелет решения: таких диагоналей всего 15, значит больше 15 клеток отметить нельзя. Пример на 15: отметить все клетки первой строки и все клетки первого столбца, кроме общей угловой клетки. Эти 15 клеток лежат на 15 разных диагоналях направления «северо-запад — юго-восток».

Ответ:

\[ 15 \]

Задача 5.4

Клетки доски \(11\times10\) раскрасили в 3 цвета так, что в каждом квадрате \(2\times2\) встречаются все три цвета. Какой тип оценки нужно искать, если нужно максимизировать число клеток первого цвета?

Скелет решения: это уже олимпиадный уровень. Надо искать локальные ограничения в каждом \(2\times2\), но непересекающиеся блоки дадут слабую оценку. Сильная идея: анализировать пары соседних строк и периодичность цветов. В такой задаче E14 почти всегда соединяется с раскраской, блоками и конструкцией периодического узора.

Ответ для курса: не давать сразу полное решение, а использовать как «миссию» после изучения блоков и раскрасок.

Семейство 6. Делимость, кратность и антисистемы

Главный сигнал: запрещено, чтобы один объект был кратен другому, делил другой или отличался в несколько раз. Оценка часто строится через цепочки вида \(a,2a,4a,\ldots\).

Задача 6.1

Из чисел от 1 до 50 нужно выбрать как можно больше чисел так, чтобы никакое выбранное число не делилось на другое выбранное число. Найдите максимум.

Скелет решения: разбить числа на цепочки по нечётной части:

\[ m,2m,4m,\ldots \]

где \(m\) нечётное. Таких цепочек 25, значит можно взять не больше 25 чисел. Пример: взять все числа от 26 до 50.

Ответ:

\[ 25 \]

Задача 6.2

Из чисел от 1 до 100 нужно выбрать как можно больше чисел так, чтобы среди выбранных не было двух чисел, одно из которых ровно в 2 раза больше другого. Найдите максимум.

Скелет решения: разбить числа на цепочки по нечётной части:

\[ m,2m,4m,8m,\ldots \]

где \(m\) нечётное. В каждой цепочке нельзя брать соседние элементы. Значит, в цепочке длины \(L\) можно взять не больше \(\lceil L/2\rceil\). Конструкция: взять все числа, у которых показатель \(v_2(n)\) чётный. Тогда удвоение любого выбранного числа имеет нечётный показатель \(v_2\), значит не выбрано.

Ответ:

\[ 67 \]

Задача 6.3

Из чисел от 1 до 100 нужно выбрать как можно больше чисел так, чтобы никакое выбранное число не было в 3 раза больше другого выбранного. Какую идею нужно применить?

Скелет решения: строить цепочки по множителю 3:

\[ a,3a,9a,27a,\ldots \]

где \(a\) не делится на 3. В каждой цепочке нельзя брать соседние элементы. Эта задача нужна не ради ответа, а ради распознавания: множитель вместо разности тоже даёт цепочки.

Ответ:

\[ 76 \]

Задача 6.4

Из чисел от 1 до 1000 нужно выбрать как можно больше чисел так, чтобы никакое выбранное число не делило другое выбранное. Предложите конструкцию и объясните, почему она оптимальна.

Скелет решения: взять все числа от 501 до 1000. Их 500, и никакое из них не делит другое, потому что удвоение любого выбранного числа уже больше 1000. Оценка через цепочки по нечётной части показывает, что больше половины взять нельзя.

Ответ:

\[ 500 \]

Семейство 7. Геометрические максимумы и почти предельные конструкции

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

Задача 7.1

В выпуклом \(n\)-угольнике один угол равен \(60^\circ\), все углы целые. Какое наибольшее значение может принимать \(n\)?

Скелет решения: остальные \(n-1\) углов не больше \(179^\circ\). Значит:

\[ 180(n-2)\le 60+179(n-1). \]

Отсюда \(n\le241\). Пример: один угол \(60^\circ\), остальные 240 углов по \(179^\circ\). Сумма внешних углов: \(120+240=360\).

Ответ:

\[ 241 \]

Задача 7.2

В выпуклом \(n\)-угольнике два угла равны \(63^\circ\) и \(97^\circ\), все углы целые. Какое наибольшее значение может принимать \(n\)?

Скелет решения: это разобранный выше пример. Остальные углы не больше \(179^\circ\).

Ответ:

\[ 162 \]

Задача 7.3

В выпуклом \(n\)-угольнике все углы не превосходят \(170^\circ\). Какое наибольшее значение может принимать \(n\)?

Скелет решения:

\[ 180(n-2)\le170n. \]

Отсюда \(10n\le360\), значит \(n\le36\). Пример: правильный 36-угольник, у которого каждый угол равен \(170^\circ\).

Ответ:

\[ 36 \]

Задача 7.4

Шахматный король ходит по доске \(8\times8\) и должен побывать на всех клетках. Какой тип E14-идеи стоит искать, если нужно максимизировать или минимизировать суммарную величину, связанную с его маршрутом?

Скелет решения: это олимпиадная маскировка E14. Оценка может идти через раскраску доски, количество переходов между типами клеток, сумму локальных вкладов или невозможность слишком часто посещать «дорогие» клетки. Пример обычно строится явным маршрутом. Такие задачи не решаются одной формулой, но структура всё равно та же: оценка маршрута плюс конструкция маршрута.

Ответ для курса: давать после семейств 2, 4 и 5 как итоговую смешанную задачу.

---

Типовые ошибки

Ошибка 1. Есть пример, но нет оценки

Ученик пишет: «Можно выбрать 165 чисел». Но задача спрашивает максимум. Надо доказать, что 166 выбрать нельзя.

Как исправить: перед примером написать оценку. Разбить объекты на группы и показать ограничение в каждой группе.

Ошибка 2. Есть оценка, но нет примера

Ученик пишет: «Больше 165 нельзя». Но вдруг 165 тоже нельзя? Тогда ответ может быть 164 или меньше.

Как исправить: построить явную конфигурацию на 165 и проверить условие.

Ошибка 3. Конструкция дана словами «очевидно»

В олимпиадном решении слово «очевидно» часто скрывает дыру. Особенно в E14.

Плохо:

«Выберем числа через одно, всё получится».

Хорошо:

«В каждой цепочке с шагом 11 выбираем элементы с нечётными номерами. Тогда два выбранных элемента не являются соседними в цепочке, значит не отличаются на 11».

Ошибка 4. Перепутан максимум и минимум

Если задача спрашивает минимум, надо доказывать «не меньше». Если спрашивает максимум, надо доказывать «не больше».

Перед решением всегда напиши одну строку:

«Я хочу доказать, что ответ равен \(N\). Для этого нужно доказать \( \le N \) и привести пример на \(N\)».

Или:

«Я хочу доказать, что ответ равен \(N\). Для этого нужно доказать \( \ge N \) и привести пример на \(N\)».

---

Мини-тест после статьи

1. Почему пример без оценки не является полным решением?
2. Почему оценка без примера не является полным решением?
3. Что надо попробовать, если запрещены два числа с разностью \(k\)?
4. В каких задачах помогает общая сумма?
5. Что нужно проверить после построения конструкции?

Правильные ответы:

1. Потому что не доказано, что лучше нельзя.
2. Потому что не доказано, что граница достигается.
3. Разбить числа на цепочки с шагом \(k\).
4. В задачах про углы, веса, деньги, баллы, площади, ходы и любые ограниченные ресурсы.
5. Что все условия выполнены и количество ровно равно найденной границе.

---

Финальный конспект

E14: это не отдельная формула, а способ закрывать оптимизационные задачи. Любое решение состоит из двух половин:

\[ \text{оценка}+\text{пример}. \]

Оценка отвечает на вопрос: «почему лучше нельзя?»

Пример отвечает на вопрос: «почему найденная граница достижима?»

Самые частые инструменты:

• разбиение на блоки;
• цепочки;
• сумма и ресурс;
• инвариант;
• двойной счёт;
• крайний объект;
• жадная конструкция;
• проверка достижения равенства.

Если научиться видеть эти идеи, задачи на максимум и минимум перестают быть угадайкой. Они превращаются в инженерную задачу: найти ограничение, а потом построить конфигурацию, которая это ограничение точно достигает.

---