E10a Корни многочленов в комбинаторике

Идея метода: использовать алгебраические свойства многочленов — в частности, тот факт, что многочлен степени $n$ имеет не более $n$ корней — для доказательства комбинаторных или числовых утверждений. Метод состоит в том, чтобы закодировать комбинаторный объект в многочлен и использовать информацию о его корнях или тождестве нулевого многочлена.

Ключевая идея: если многочлен $P(x)$ степени $n$ обращается в нуль при $n+1$ различных значениях $x$, то $P \equiv 0$ (тождественный ноль). Это «жёсткость»: нельзя придумать «случайный» многочлен, исчезающий в слишком многих точках.

В комбинаторике это используется так: строим многочлен $P$, который «кодирует» нужное свойство. Затем показываем, что $P$ имеет слишком много корней для своей степени — значит $P \equiv 0$, что и нужно доказать.

Аналогия: если вы знаете, что прямая (многочлен степени 1) проходит через 2 точки — она определена однозначно. Если через 3 — это уже невозможно (если только это не горизонтальная прямая, т.е. $P \equiv c$). Больше точек, чем степень — многочлен обязан быть нулевым.

• Теорема об идентичности многочленов: Многочлен $P(x)$ степени $\leq n$ над полем $\mathbb{F}$ имеет не более $n$ корней. Если $P$ обнуляется в $n+1$ точках — $P \equiv 0$. Когда использовать: нужно доказать, что два многочлена тождественно равны — достаточно показать равенство в $\deg + 1$ точках.

• Теорема Чебышёва–Лагранжа (интерполяция): По $n+1$ точке $(x_0, y_0), \ldots, (x_n, y_n)$ (с различными $x_i$) существует единственный многочлен степени $\leq n$, принимающий данные значения. Когда использовать: конструктивные задачи: задать многочлен через значения в точках.

• Производящая функция и корни единицы: $\sum_{k=0}^{n-1} \omega^{jk} = n \cdot [n \mid j]$, где $\omega = e^{2\pi i/n}$ — первообразный корень из $n$. Когда использовать: считать суммы биномиальных коэффициентов с шагом $n$, доказывать тождества через подстановку корней единицы.

• Лемма о нулевом многочлене над $\mathbb{Z}_p$: Если $P(x) \equiv 0$ для всех $x \in \mathbb{Z}_p$, это не значит $P \equiv 0$ как многочлен (например, $x^p - x \equiv 0$ для всех $x \in \mathbb{Z}_p$$). *$Когда использовать:* при работе с многочленами по модулю простого числа.

• Метод подстановки корней $n$-й степени из единицы: Для нахождения $\sum_{k \equiv r \pmod n} \binom{N}{k}$ подставляем $x = \omega^j$ в $(1+x)^N$ и суммируем по $j = 0, 1, \ldots, n-1$.

• Кодирование множества в многочлен: множество $S = \{s_1, \ldots, s_m\}$ кодируем многочленом $P(x) = \prod_{i=1}^m (x - s_i)$. Свойства элементов $S$ — свойства корней.

• Доказательство тождества через лишние корни: строим разность $Q(x) = P(x) - R(x)$ двух многочленов. Если $\deg Q \leq n$ и $Q$ обнуляется в $> n$ точках — $Q \equiv 0$, значит $P = R$.

• Подстановка корней единицы: в производящую функцию $F(x) = \sum_k a_k x^k$ подставляем $x = 1, \omega, \omega^2, \ldots, \omega^{n-1}$ и берём среднее — выделяем коэффициенты с нужными остатками.

• Интерполяция Лагранжа: строим многочлен степени $n$ по $n+1$ точке. Используем единственность для доказательства.

• Линейная независимость над полем: $n+1$ многочлен степени $\leq n$ линейно зависим — используем это для оценок.

• Оценка через количество корней: если многочлен $P$ специфической структуры имеет корни в $S$, а $|S| > \deg P$ — $P \equiv 0$.

Поверхностные признаки (что буквально написано):
- «Докажите тождество для $\sum \binom{n}{k}$» с суммированием по $k$ определённого остатка.
- «Многочлен с целыми коэффициентами, принимающий такие-то значения...».
- «Докажите, что многочлен делится на...».

Структурные признаки (форма выражения, объекты):
- Сумма биномиальных коэффициентов с шагом (через каждый $k$-й).
- Задача, где нужно доказать равенство для бесконечно (или «для всех $n$») многих значений — используем тождество многочленов.
- Задача о характеристических функциях множеств (кодирование через $x^i$).

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

Задача 1. Сумма биномиальных коэффициентов с шагом 3

Условие: Докажите, что $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots = \dfrac{2^n + 2\cos(n\pi/3)}{3}$.

Источник: классическая задача (производящие функции, корни единицы; уровень ВсОШ заключ.–Физтех)

Как думать (рассуждение ученика$):
1. $Что вижу?* Сумма $\binom{n}{k}$ с шагом 3 — нужно «выделить» коэффициенты с $k \equiv 0 \pmod 3$.$2. *$Метод: корни из единицы! $\omega = e^{2\pi i/3}$ — первообразный корень 3-й степени из $1.
3. $Ключевая формула:* $\sum_{k \equiv 0 (\mathrm{mod}\, 3)} \binom{n}{k} = \frac{(1+1)^n + (1+\omega)^n + (1+\omega^2)^n}{3}$.$4. *$Вычисляем: $1+1 = 2$; $1 + \omega = 1 + e^{2\pi i/3} = -e^{-i\pi/3}$; $|1+\omega| = 1$, $\arg(1+\omega) = \pi/3$ (точнее, $1+\omega = e^{i\pi/3}$, $|\cdot|=1$). По формуле Эйлера: $(1+\omega)^n = e^{in\pi/3} = \cos(n\pi/3) + i\sin(n\pi/3)$. Аналогично $(1+\omega^2)^n = e^{-in\pi/3}$. Сумма $(1+\omega)^n + (1+\omega^2)^n = 2\cos(n\pi/3)$.

Решение:

Пусть $\omega = e^{2\pi i/3}$. Используем тождество для выделения коэффициентов $k \equiv 0 \pmod 3$:$$S = \sum_{k \equiv 0 (3)} \binom{n}{k} = \frac{1}{3}\left[(1+1)^n + (1+\omega)^n + (1+\omega^2)^n\right].$$ Вычислим $1+\omega$: $\omega = e^{2\pi i/3} = -\frac{1}{2} + \frac{\sqrt{3}}{2}i$, поэтому $1+\omega = \frac{1}{2} + \frac{\sqrt{3}}{2}i = e^{i\pi/3}$. Аналогично $1+\omega^2 = e^{-i\pi/3}$.

Тогда $(1+\omega)^n + (1+\omega^2)^n = e^{in\pi/3} + e^{-in\pi/3} = 2\cos(n\pi/3)$.

$S = \frac{2^n + 2\cos(n\pi/3)}{3}.$

Ответ: $\binom{n}{0} + \binom{n}{3} + \ldots = \dfrac{2^n + 2\cos(n\pi/3)}{3}$.

Что главное: корни единицы «просеивают» биномиальные коэффициенты нужных остатков.

Задача 2. Многочлен тождественно равен нулю

Условие: Многочлен $P(x)$ целых коэффициентов степени $\leq 10$ принимает значение 0 в 11 различных целых точках. Докажите, что $P \equiv 0$.

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

Как думать (рассуждение ученика$):
1. $Что вижу?* Многочлен степени $\leq 10$ с 11 корнями. Основная теорема — многочлен степени $n$ имеет $\leq n$ корней. Если 11 корней при степени $\leq 10$ — это невозможно, если $P \not\equiv 0$.$2. *$Рассуждение: если $P \not\equiv 0$, то $\deg P = d \leq 10$ и $P$ имеет $\leq d \leq 10$ корней. Но нам дано 11 корней — противоречие. Значит $P \equiv 0$.

Решение:

Предположим, что $P \not\equiv 0$. Тогда степень $P$ равна некоторому $d \leq 10$. Над полем $\mathbb{Q}$ (и тем более над $\mathbb{R}$) многочлен степени $d$ имеет не более $d$ корней. По условию $P$ имеет $\geq 11 > 10 \geq d$ корней — противоречие. Следовательно $P \equiv 0$.

Ответ: $P \equiv 0$.

Что главное: «число корней > степень ⇒ P ≡ 0» — это и есть базовое применение теоремы об идентичности.

• Ошибка: путают «P обнуляется в точках» и «P тождественно равен нулю». Первое — частный случай второго только если число точек превышает степень. Как избежать: явно сравните число корней и степень многочлена.

• Ошибка: работают с многочленами над $\mathbb{Z}_p$ и забывают о «лжекорнях». Над $\mathbb{Z}_p$ многочлен $x^p - x$ обнуляется во всех точках, но не равен нулю как многочлен. Как избежать: различайте «нулевой многочлен» и «многочлен, равный нулю на всех точках поля».

• Ошибка: неправильно вычисляют корни единицы. $\omega^3 = 1$, $\omega \neq 1$ — не путайте $\omega^3$ с $\omega$. Как избежать: выпишите явно $\omega = e^{2\pi i/n}$ и проверьте: $\omega^n = 1$, $\omega^k \neq 1$ для $0 < k < n$.

• Ошибка: не учитывают, что интерполяционный многочлен единственен при фиксированной степени. Без условия на степень многочленов, проходящих через данные точки, бесконечно много. Как избежать: явно укажите «единственный многочлен степени $\leq n$».

• Ошибка: сумма $\sum_{k \equiv r} \binom{n}{k}$ считается без разбивки по $\omega^j$. Без формулы с корнями единицы эту сумму получить крайне сложно. Как избежать: сразу пишите $\frac{1}{n}\sum_{j=0}^{n-1} \omega^{-jr}(1+\omega^j)^N$.