Числовые наборы и сюжетные задачи

Зачем это в ЕГЭ. Задание №19, 4 первичных балла. Числовые наборы — самый частый сюжет: «найти все наборы натуральных чисел, удовлетворяющих условиям на сумму, произведение, делимость, порядок». Структура а) пример, б) доказательство, в) все наборы (или мин/макс).

Главная идея. Три кита: (1) оценки — ограничить переменные сверху/снизу, чтобы перебор стал конечным; (2) делимость и остатки — отсечь невозможные комбинации; (3) упорядоченный перебор — $a\le b\le c$ убирает дубли, $a\ge1$ ограничивает снизу. Принцип Дирихле: если $n+1$ объектов разложены в $n$ ящиков, в одном $\ge2$.

Алгоритм (чеклист).
1. Зафиксировать порядок ($a\le b\le c$) — убрать перестановки.
2. Оценки сверху: из $abc=N$ и $a\le b\le c$ следует $a^3\le N$, то есть $a\le\sqrt[3]{N}$; аналогично для $b$.
3. Для каждого допустимого $a$ — перебрать $b$; $c$ определяется однозначно из уравнения.
4. Проверить все условия: натуральность, различность, делимость, неравенства.
5. Для пункта б) — использовать оценки или остатки для доказательства (не перебора!).
6. Для пункта в) — привести все наборы и доказать, что других нет.

Опоры (кратко).
- Число делителей $N=p_1^{k_1}\cdot\ldots\cdot p_s^{k_s}$: $d(N)=(k_1+1)\cdots(k_s+1)$.
- НСД $+$ НОК: $\gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab$.
- Принцип Дирихле: $n+1$ объект в $n$ ящиках $\Rightarrow$ хотя бы в одном $\ge2$.
- Среднее арифметическое $\ge$ среднее геометрическое: $\frac{a+b+c}{3}\ge\sqrt[3]{abc}$.

Пример 1 (перебор с оценкой). Найти все тройки натуральных $a\le b\le c$ таких, что $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1$.

Шаг 1. Оценка: $\frac{1}{a}\ge\frac{1}{3}$ (так как $\frac{3}{a}\ge\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1$), значит $a\le3$.

Шаг 2. $a=1$: $\frac{1}{b}+\frac{1}{c}=0$ — невозможно для натуральных.

Шаг 3. $a=2$: $\frac{1}{b}+\frac{1}{c}=\frac{1}{2}$. Аналогичная оценка: $b\le4$. $b=2$: нет; $b=3$: $c=6$; $b=4$: $c=4$.

Шаг 4. $a=3$: $\frac{1}{b}+\frac{1}{c}=\frac{2}{3}$, $b\ge3$: $b=3$, $c=3$. Итого: $(2,3,6)$, $(2,4,4)$, $(3,3,3)$.

Пример 2 (принцип Дирихле). Среди $13$ целых чисел найдутся два, разность которых делится на $12$.

Шаг 1. Остатки при делении на $12$: $0,1,2,\ldots,11$ — всего $12$ классов.

Шаг 2. $13$ чисел, $12$ классов — по принципу Дирихле хотя бы два в одном классе.

Шаг 3. Их разность делится на $12$. ЧТД.

Пример 3 (пункт в — оптимум). Сумма $n$ различных натуральных чисел равна $20$. Наибольшее $n$?

Шаг 1. Минимальная сумма $n$ различных натуральных: $1+2+\ldots+n=\frac{n(n+1)}{2}$.

Шаг 2. $\frac{n(n+1)}{2}\le20$: $n\le5$ (при $n=5$: $15\le20$; при $n=6$: $21>20$).

Шаг 3. Пример для $n=5$: $\{1,2,3,4,10\}$ — сумма $20$, все различные. Ответ: $n=5$.

Типичные ошибки.
1. Считают упорядоченные и неупорядоченные одинаково — $(2,3,6)$ и $(3,2,6)$ — один набор при $a\le b\le c$.
2. Забывают условие «различные» — $(4,4)$ не годится, если нужны различные.
3. Не доказывают оценку в пункте в) — предъявили пример, но не показали, что лучше нельзя.
4. Дублируют решения — не зафиксировали порядок и получили одну тройку несколько раз.
5. Перебирают вместо доказательства в б) — «проверил для $n=1,\ldots,100$» не является доказательством.

Дальше. Полные тренировочные задачи №19 в тренажёре.