C12 Симметрические многочлены и переход к s,p

Идея метода: выражение, симметричное относительно перестановки переменных $a$ и $b$, всегда можно записать через два «элементарных» симметрических многочлена: $s = a+b$ и $p = ab$. Это колоссально упрощает алгебру: вместо двух неизвестных $a$ и $b$ остаётся два «агрегированных» параметра $s$ и $p$, а затем можно вернуться к $a$ и $b$ через квадратное уравнение $t^2 - st + p = 0$.

Метод отличается от C5a (теорема Виета): там акцент на связь корней с коэффициентами конкретного уравнения. Здесь акцент — на алгебраическую технику: как выразить $a^n + b^n$, $a^3b + ab^3$, $a^4 + b^4$ через $s$ и $p$ с помощью рекуррентных формул Ньютона, и как решать симметричные системы двух уравнений, сводя их к одному.

Аналогия: представь, что $a$ и $b$ — это два «игрока», а $s$ и $p$ — их «общий счёт» и «произведение усилий». Любая игровая статистика, не различающая игроков, выражается через эти два числа. Если нам дали два уравнения с $a$ и $b$, симметричных относительно их перестановки, мы «перепишем правила» через $s$ и $p$ и решим задачу в два раза быстрее.

Для трёх переменных аналогично используют $e_1 = a+b+c$, $e_2 = ab+bc+ca$, $e_3 = abc$, но на олимпиадах 9–11 класса чаще встречается двухпеременный случай.

• Основная теорема о симметрических многочленах: любой симметрический многочлен от $a, b$ выражается как многочлен от $s = a+b$ и $p = ab$. Когда использовать: любое симметричное выражение — сделать замену $s, p$.

• Формулы для степенных сумм $P_n = a^n + b^n$:$$P_1 = s, \quad P_2 = s^2 - 2p, \quad P_3 = s^3 - 3sp, \quad P_n = s \cdot P_{n-1} - p \cdot P_{n-2}.$$ Это и есть формулы Ньютона (для двух переменных$). *$Условие: $a, b$ — корни $t^2 - st + p = 0$. Когда использовать:* выразить $a^n+b^n$ через $s$ и $p$ для любого $n$.

• Возврат к переменным: зная $s$ и $p$, находим $a$ и $b$ как корни уравнения $t^2 - st + p = 0$, то есть $a, b = \dfrac{s \pm \sqrt{s^2 - 4p}}{2}$. Условие применимости: $s^2 - 4p \geq 0$ для действительных $a, b$; целочисленные решения требуют, чтобы $s^2-4p$ было точным квадратом.

• Полезные выражения:$$a^2+b^2 = s^2-2p, \quad a^3+b^3 = s^3-3sp = s(s^2-3p),$$ $$a^2b+ab^2 = sp, \quad a^4+b^4 = (s^2-2p)^2 - 2p^2 = s^4 - 4s^2p + 2p^2.$$

• Симметричная система: система вида $\{f(a,b)=A,\ g(a,b)=B\}$, где $f$ и $g$ симметричны, решается заменой $s=a+b, p=ab$, затем возвратом через квадратное уравнение.

• Обозначить $s = a+b$, $p = ab$ немедленно, как только в задаче стоит симметричное выражение от двух переменных.

• Выразить всё через $s$ и $p$ по формулам $P_n = s\cdot P_{n-1} - p\cdot P_{n-2}$, начиная с $P_0=2$, $P_1=s$.

• Свести систему к двум уравнениям в $s, p$, решить её (нередко линейно или через подстановку), найти $s$ и $p$.

• Возврат: $a$ и $b$ — корни $t^2 - st + p = 0$. Проверить дискриминант. Записать пары $(a,b)$ с учётом симметрии.

• Телескопические суммы через рекуррентность: если дано $P_k$ для нескольких $k$, применять формулу $P_n = s P_{n-1} - p P_{n-2}$ итеративно.

• Для трёх переменных: использовать $e_1=a+b+c$, $e_2=ab+bc+ca$, $e_3=abc$ и формулу Ньютона $P_n = e_1 P_{n-1} - e_2 P_{n-2} + e_3 P_{n-3}$.

Поверхностные признаки (что буквально написано):
- «Решите систему $a+b=\ldots,\ a^2+b^2=\ldots$» или аналог
- «Найдите $a^3+b^3$, если $a+b=\ldots$ и $ab=\ldots$»
- «Докажите, что $a^n+b^n$ целое, если $a+b$ и $ab$ целые»
- «Для всех $a+b=k$, $ab=m$ найдите ...»

Структурные признаки (форма выражения, объекты):
- В задаче два уравнения с двумя переменными, оба симметричны: не меняются при перестановке $a \leftrightarrow b$ - Задача содержит выражение вида $a^n+b^n$ или $a^n b^m + a^m b^n$ - Система содержит «нечётные» и «чётные» степени, которые удобно выражать через рекуррентность
- Выражение не симметрично в явном виде, но становится симметричным после подстановки

Цель задачи (что от тебя хотят):
- Решить систему с двумя (тремя) неизвестными симметричного вида
- Доказать целочисленность или знак выражения
- Найти значение выражения $a^n+b^n$ при данных условиях на $a+b$ и $ab$

Задача 1. Решите систему: $a + b = 5$, $\ a^3 + b^3 = 35$.

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

Как думать (рассуждение ученика):
1. Что я вижу? Два уравнения, два неизвестных. Оба выражения симметричны: если поменять $a$ и $b$ местами, уравнения не изменятся. Триггер: замена $s=a+b, p=ab$.
2. Какой метод? C12 — симметрические многочлены. Вместо того чтобы выражать $b=5-a$ и получать кубическое уравнение, переходим к $s$ и $p$.
3. Первый ход: $s = 5$ (прямо из первого уравнения). Теперь нужно найти $p$.
4. Ключевая идея: Применим формулу $a^3+b^3 = s^3 - 3sp$, получим $p$, затем найдём $a$ и $b$ из квадратного уравнения $t^2 - st + p = 0$.

Решение:

Обозначим $s = a+b = 5$, $p = ab$.

Используем тождество:$$a^3 + b^3 = (a+b)^3 - 3ab(a+b) = s^3 - 3ps.$$

Подставляем:$$35 = 5^3 - 3p \cdot 5 = 125 - 15p \implies 15p = 90 \implies p = 6.$$

Знаем: $s = 5$, $p = 6$. Числа $a$ и $b$ — корни уравнения:$$t^2 - 5t + 6 = 0 \implies t = 2 \ \text{или} \ t = 3.$$

Ответ: $(a, b) \in \{(2, 3),\ (3, 2)\}$.

Проверка: $2+3=5$ ✓; $2^3+3^3=8+27=35$ ✓.

Ответ: $(a, b) = (2, 3)$ или $(a, b) = (3, 2)$.

Что в этой задаче было главным: вместо подстановки $b=5-a$ и кубического уравнения — применение формулы $a^3+b^3=s^3-3sp$ сразу даёт линейное уравнение на $p$. Это и есть сила метода $s, p$.

Задача 2. Докажите, что если $a+b$ и $ab$ целые числа, то $a^n + b^n$ — целое для любого натурального $n$.

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

Как думать (рассуждение ученика):
1. Что я вижу? Нужно доказать целочисленность $a^n + b^n$ для всех $n \in \mathbb{N}$. Параметр — натуральное число $n$. Значит, нужна индукция. Но по чему индуцировать? По $n$.
2. Какой метод? Сочетание C12 (формулы Ньютона) и C10 (индукция). Формула $P_n = s \cdot P_{n-1} - p \cdot P_{n-2}$ позволяет делать индукционный шаг.
3. Первый ход: $P_1 = a+b = s \in \mathbb{Z}$, $P_2 = s^2 - 2p \in \mathbb{Z}$ (так как $s,p \in \mathbb{Z}$). Это база для двух шагов.
4. Ключевая идея: Рекуррентность $P_n = s P_{n-1} - p P_{n-2}$ с $s, p \in \mathbb{Z}$ и $P_{n-1}, P_{n-2} \in \mathbb{Z}$ (по ПИ) даёт $P_n \in \mathbb{Z}$.

Решение:

Обозначим $s = a+b \in \mathbb{Z}$, $p = ab \in \mathbb{Z}$, $P_n = a^n + b^n$.

Заметим, что $a$ и $b$ — корни уравнения $t^2 - st + p = 0$, поэтому:$a^2 = sa - p, \quad b^2 = sb - p.$ Отсюда для любого $n \geq 2$:$$a^n = s \cdot a^{n-1} - p \cdot a^{n-2}, \quad b^n = s \cdot b^{n-1} - p \cdot b^{n-2}.$$ Сложив:$$P_n = s \cdot P_{n-1} - p \cdot P_{n-2}. \quad (*)$$

Докажем $P_n \in \mathbb{Z}$ для всех $n \geq 1$ по сильной индукции.

База: $P_1 = s \in \mathbb{Z}$ и $P_2 = s^2 - 2p \in \mathbb{Z}$. ✓

Шаг: Предположим $P_{n-1}, P_{n-2} \in \mathbb{Z}$ для некоторого $n \geq 3$. По формуле $(*)$:$P_n = s \cdot P_{n-1} - p \cdot P_{n-2}.$ Так как $s, p \in \mathbb{Z}$ и $P_{n-1}, P_{n-2} \in \mathbb{Z}$, получаем $P_n \in \mathbb{Z}$.

По принципу сильной индукции $P_n = a^n + b^n \in \mathbb{Z}$ для всех $n \in \mathbb{N}$. $\blacksquare$

Ответ: доказано.

Что в этой задаче было главным: рекуррентность $P_n = s P_{n-1} - p P_{n-2}$ — сердце метода симметрических многочленов. Она позволяет применить сильную индукцию и доказать целочисленность без каких-либо конкретных значений $a$ и $b$ (которые могут быть вовсе иррациональными!).

• Ошибка: Не проверить симметричность системы и применять замену $s, p$ к несимметричной системе. → Почему неверно: если уравнения несимметричны, замена $s=a+b, p=ab$ не упрощает систему. → Как избежать: сначала проверить: изменится ли система при $a \leftrightarrow b$? Если нет — метод применим.

• Ошибка: Забыть написать обе пары решений $(a, b) = (x, y)$ и $(a, b) = (y, x)$. → Почему неверно: система симметрична, поэтому если $(a,b)=(2,3)$ — решение, то и $(3,2)$ тоже. → Как избежать: после нахождения $s, p$ и корней $t_1, t_2$ всегда записывать обе пары.

• Ошибка: Путать $a^3+b^3 = s^3-3sp$ с $a^3+b^3 = (s-p)(s^2-2p-p^2)$ или другой неверной формулой. → Почему неверно: $a^3+b^3 = (a+b)(a^2-ab+b^2) = s(s^2-3p)$; перепутать знак. → Как избежать: вывести формулу из рекуррентности: $P_3 = s\cdot P_2 - p \cdot P_1 = s(s^2-2p) - ps = s^3-3sp$.

• Ошибка: При возврате к переменным не проверить дискриминант $D = s^2 - 4p \geq 0$. → Почему неверно: если $D < 0$, действительных решений нет; если $D$ не точный квадрат, нет целых решений. → Как избежать: всегда вычислять $D$ и анализировать знак/структуру.

• Ошибка: Смешивать C12 с C5a: думать, что «Виета» и «$s,p$» — одно и то же. → Почему неверно: C5a — это связь корней конкретного уравнения с его коэффициентами (инструмент анализа уравнений); C12 — это алгебраический метод работы с симметричными выражениями (инструмент вычисления). Они пересекаются, но не одно и то же. → Как избежать: помнить: C12 применяется, когда хотим вычислить $a^n+b^n$ или решить симметричную систему; C5a — когда строим уравнение по его корням.