D1b Серия конструкций (бесконечно много примеров)

Идея метода: задача просит доказать, что существует бесконечно много объектов с заданным свойством. Это не задача «найдите один пример» — нужна бесконечная серия. Метод состоит в конструировании параметрического семейства объектов, в котором параметр (обычно натуральное число $n$) пробегает все значения или все значения из некоторого бесконечного множества.

Ключевой момент: нужно не просто угадать несколько примеров, а написать явную формулу, зависящую от параметра, и доказать, что:
1. формула задаёт нужный объект (число, многочлен, пару чисел) для каждого $n$;
2. объекты при разных $n$ различны (чтобы их действительно было бесконечно много);
3. каждый из них обладает требуемым свойством.

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

Частый контекст в задачах ВсОШ заключительного этапа: «докажите, что существует бесконечно много натуральных/целых/простых чисел $n$ таких, что...»

• Принцип параметрического семейства. Если для каждого $n \in \mathbb{N}$ (или каждого $n$ из бесконечного множества) построен объект $X_n$, обладающий свойством $P$, и $X_n \neq X_m$ при $n \neq m$, то таких объектов бесконечно много.

• Теорема Дирихле о простых в арифметических прогрессиях. Если $\gcd(a, d) = 1$, то прогрессия $a, a+d, a+2d, \ldots$ содержит бесконечно много простых. Условие: взаимная простота. Когда использовать: нужна бесконечная серия простых с конкретным остатком.

• Лемма об умножении на $k$. Если $N$ обладает свойством $P$ (делимость, значение многочлена и т.п.), то часто $kN$ или $N + kd$ тоже обладает — это позволяет строить бесконечные серии из одного примера.

• Метод «взять $n = $ произведение». Если нужно доказать бесконечность простых, делящих $P(n)$ для специальных $n$: стандартный приём — предположить, что простых конечно $\{p_1, \ldots, p_k\}$, и рассмотреть $N = p_1 \cdots p_k \pm 1$ (или другую конструкцию).

• Явная параметрическая формула. Пиши $a_n = f(n)$, где $f$ — явная функция от параметра $n \in \mathbb{N}$; доказывай свойство для каждого $n$.
• Конструкция «кратное плюс константа». Если нужен объект с определённым остатком при делении — берёт $a_n = c + k \cdot n$ для подходящих $c, k$.
• Конструкция через простые числа. Если нужны числа с особыми множителями — строй $a_n = p_1^{e_1(n)} \cdot p_2^{e_2(n)} \cdots$.
• Конструкция через многочлен. Если $P(a) = 0 \pmod{m}$, то $P(a + km) = 0 \pmod{m}$ — строй серию $\{a + km : k \in \mathbb{N}\}$.
• Доказательство от противного + конструкция. Предположи, что объектов конечно; построй новый объект с нужным свойством, не входящий в предполагаемый конечный список — противоречие.
• Серия через рекуррентность. Если $a_0$ обладает свойством $P$, а из $a_n$ с помощью операции $T$ можно получить $a_{n+1}$ с тем же свойством — строй $a_n = T^n(a_0)$.

Поверхностные признаки (что буквально написано):
- «Докажите, что существует бесконечно много натуральных чисел $n$, таких что...»
- «Покажите, что множество $\{n \in \mathbb{N} : P(n)\}$ бесконечно».
- «Найдите бесконечно много примеров пар $(a, b)$ таких, что...»

Структурные признаки (форма выражения, объекты):
- Нужно не одно, а бесконечно много объектов.
- Условие задачи говорит о натуральных числах с некоторым свойством без верхней границы.
- Задача на нахождение простых чисел специального вида или с конкретным остатком.

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

Задача 1. Докажите, что существует бесконечно много натуральных чисел $n$ таких, что $n^2 + 1$ делится на 5.

Источник: тренировочная (базовый пример метода, стиль ВсОШ муниципальный)

Как думать (рассуждение ученика):
1. Что я вижу? Нужна бесконечная серия $n$ с заданной делимостью. Ищу параметрическое семейство.
2. Первый ход: проверю $n = 2$: $4 + 1 = 5$ — делится. Отлично, нашёл один пример.
3. Как построить серию? Если $n \equiv 2 \pmod{5}$, то $n^2 \equiv 4 \pmod{5}$, $n^2 + 1 \equiv 0 \pmod{5}$. Значит все $n = 2 + 5k$ ($k \in \mathbb{N}_0$) подходят.
4. Различность: при разных $k$ числа $n = 2 + 5k$ различны — это бесконечное множество.

Решение:

Положим $n_k = 2 + 5k$ для $k = 0, 1, 2, \ldots$

Тогда $n_k^2 + 1 = (5k+2)^2 + 1 = 25k^2 + 20k + 4 + 1 = 25k^2 + 20k + 5 = 5(5k^2 + 4k + 1)$.

Значит $5 \mid n_k^2 + 1$ для каждого $k \geq 0$. Числа $n_0 = 2, n_1 = 7, n_2 = 12, \ldots$ попарно различны, их бесконечно много.

Ответ: серия $n = 5k + 2$, $k = 0, 1, 2, \ldots$

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

Задача 2. Докажите, что существует бесконечно много натуральных чисел, которые можно представить в виде суммы двух полных квадратов двумя различными способами.

Источник: тренировочная (дух задач ВсОШ заключительного этапа 9 класс)

Как думать (рассуждение ученика):
1. Что я вижу? Нужна бесконечная серия чисел с конкретным свойством представления. Начну с поиска одного примера, затем построю серию.
2. Пример: $25 = 0^2 + 5^2 = 3^2 + 4^2$ — два способа. Хорошо.
3. Как получить серию из одного примера? Умножение: если $N = a^2 + b^2 = c^2 + d^2$, то $k^2 N = (ka)^2 + (kb)^2 = (kc)^2 + (kd)^2$ — тоже два способа. Значит $25k^2$ работает для всех $k$.
4. Различность: числа $25 \cdot 1^2, 25 \cdot 2^2, 25 \cdot 3^2, \ldots$ попарно различны.

Решение:

Возьмём $N_k = 25k^2$ для $k = 1, 2, 3, \ldots$

Тогда:$N_k = (5k)^2 + 0^2 = (3k)^2 + (4k)^2$

— два различных представления в виде суммы двух квадратов (при $k \geq 1$ они различны, так как $5k \neq 3k$ и пары $(5k, 0), (3k, 4k)$ не совпадают).

Числа $N_k = 25, 100, 225, \ldots$ попарно различны (растут). Серия бесконечна.

Ответ: $N_k = 25k^2$, $k = 1, 2, 3, \ldots$

Что было главным: нашли один «базовый пример» (25), затем применили масштабирование (умножение на $k^2$) — оба представления масштабируются одновременно. Это стандартная стратегия «один пример + параметризация».

Задача 3. (Уровень ВсОШ заключительный, 9 класс) Докажите, что существует бесконечно много натуральных $n$, для которых $n! + 1$ не является простым числом.

Источник: задача в духе ВсОШ заключительного этапа

Как думать (рассуждение ученика):
1. Что я вижу? Нужно доказать, что «почти всегда» $n! + 1$ составное. Метод от противного не подойдёт — нужна явная серия.
2. Идея: если $n! + 1 = p$ — простое, то все простые $\leq n$ не делят $n! + 1$ (они делят $n!$). Но нам нужно показать, что $n! + 1$ составное для бесконечно многих $n$.
3. Конструкция: возьму $n = (m!)! + m! - 1$ — слишком сложно. Попробую другой путь.
4. Простая идея: $n!+1$ составное, если у него есть делитель в $(1, n!+1)$. Заметим: если $n \geq 3$, то $(n+1)! + 1 = (n+1) \cdot n! + 1$. Если $n!+1 = p$ простое, то $(n+1)! + 1 = (n+1)(n!+1) - n = (n+1)p - n$. Это не помогает напрямую. Используем другой факт: для любого $n \geq 2$, $(n \cdot k)! + 1$ делится на $(k! + 1)$... нет.
5. Правильная конструкция: заметим, что $p! + 1$ для любого простого $p \geq 5$ делится на $p+1$? Проверим: $5! + 1 = 121 = 11 \cdot 11$ — составное ($11 = 5+6$, не $p+1=6$). Попробуем: при $n = p - 1$: $(p-1)! \equiv -1 \pmod{p}$ (теорема Вильсона), значит $(p-1)! + 1 \equiv 0 \pmod{p}$, то есть $p \mid (p-1)! + 1$. При $p \geq 3$: $(p-1)! + 1 \geq 3! + 1 = 7 > p$ при $p \geq 5$. Значит $(p-1)! + 1$ составное!

Решение:

По теореме Вильсона: для простого $p$, $(p-1)! \equiv -1 \pmod{p}$, то есть $p \mid (p-1)! + 1$.

При $p \geq 5$: $(p-1)! + 1 \geq 4! + 1 = 25 > 5 \geq p$ (так как $p \geq 5$ и $(p-1)! \geq 24$), значит $(p-1)! + 1$ не равно $p$ — оно составное.

Числа $n = p - 1$ для простых $p \geq 5$ образуют бесконечную серию (простых бесконечно много), и для каждого $n! + 1$ составное.

Ответ: числа $n = p - 1$ для простых $p \geq 5$ дают бесконечную серию.

Что было главным: теорема Вильсона — неожиданный инструмент, который даёт делитель $p$ для $(p-1)! + 1$; оценка снизу гарантирует, что это делитель меньше самого числа.

• Ошибка: привести несколько конкретных примеров и заявить «существует бесконечно много». Почему неверно: конечный список примеров не доказывает бесконечность. Как избежать: пиши явную формулу $a_n = f(n)$ для $n = 1, 2, 3, \ldots$ и доказывай свойство для каждого $n$.
• Ошибка: не доказать, что объекты в серии попарно различны. Почему неверно: если $f(n) = f(m)$ при $n \neq m$, то множество может быть конечным. Как избежать: явно указывай, что $f$ строго возрастает или инъективна.
• Ошибка: строить серию, не проверив, что каждый элемент обладает нужным свойством. Почему неверно: ошибка в выборе параметров может дать объекты, не удовлетворяющие условию. Как избежать: после написания формулы сразу докажи свойство в общем виде (не проверкой для $n=1,2,3$).
• Ошибка: в задачах на делимость брать $n = c + kd$ без проверки, что $c$ подходит. Почему неверно: базовый пример мог не работать. Как избежать: сначала найди один $c$, для которого свойство выполняется, а затем строй прогрессию с шагом $d$.
• Ошибка: использовать доказательство от противного «пусть примеров конечно» без явного построения нового. Почему неверно: само по себе предположение о конечности не приводит к противоречию — нужно построить новый пример. Как избежать: при доказательстве от противного всегда явно конструируй новый объект.