Задача 98055

Темы:    [ Свойства коэффициентов многочлена ] [ Деление многочленов с остатком. НОД и НОК многочленов ] [ Индукция (прочее) ]

Сложность: 3+ Классы: 8,9,10

Условие

Автор: Фомин Д.

Докажите, что при любом натуральном n найдётся ненулевой многочлен P(x) с коэффициентами, равными 0, –1, 1, степени не больше 2ⁿ, который делится на
(x – 1)ⁿ.

Решение

Положим  P₁(x) = x – 1,  P_n+1(x) = (x²ⁿ – 1)P_n(x).  Докажем, что эти многочлены обладают требуемыми свойствами. Легко проверить, что  deg P_n = 2ⁿ – 1.  Коэффициенты P_n+1 – это два непересекающихся набора коэффициентов P_n, следовательно, так же как и у P₁, они равны ±1.  P_n делится на  (x – 1)ⁿ,  так как  x^2k – 1  делится на  x – 1.

Замечания

6 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1989/1990
Номер	11
вариант
Вариант	весенний тур, основной вариант, 10-11 класс
Задача
Номер	1