Задание №177230: Турнир городов

6. Для каких натуральных n верно следующее утверждение: для произвольного многочле-
на P степени n с целыми коэффициентами найдутся такие различные натуральные a и b,
для которых P(a) + P(b) делится на a + b?
Г. Жуков
Ответ. При всех чётных n.
Решение. Нечётные n не подходят. В самом деле, рассмотрим многочлен P(x) = xn + 1 и
различные натуральные a, b. Так как n нечётно, an+bn делится на a+b, а тогда P(a)+P(b) =
(an + bn) + 2 не делится, поскольку a + b > 2.
Осталось доказать, что все чётные n подходят. Рассмотрим произвольный многочлен P(x)
степени n. Представим его в виде суммы P(x) = P (x)+P (x), где в P (x) все мономы чётной
0 1 0
степени, а в P (x) – нечётной. Заметим, что при всех натуральных a, b сумма P (a) + P (b)
1 1 1
делится на a + b. Докажем, что найдутся такие a, b,что и P (a) + P (b) делится на a + b.
0 0
Заметим, что степень P равна n.
0
Рассмотрим случай, когда старший коэффициент P (x) положителен (в случае отрицатель-
0
ного старшего коэффициента проведём дальнейшее доказательство для многочлена −P (x)).
0
Так как n > 1, то найдётся такое натуральное m, что P (m) > 2m. Докажем, что a = m,
0
b = P (m) − m подходят. В силу выбора m, они оба натуральные, причём b > a. Далее,
0
по модулю a + b = P (m) выполняются сравнения P (a) = P (m) ≡ 0 (очевидно) и P (b) =
0 0 0 0
P ((b+a)−a) ≡ P (−a) = P (m) ≡ 0 (в силу чётности многочлена P ). Значит, P (a)+P (b) ≡ 0
0 0 0 0 0 0
(mod a + b), что и требовалось.
Замечание. В случае чётного n можно проделать подобное рассуждение и без разбиения
на чётную и нечётную компоненты. Поскольку степень многочлена P(x)+P(−x) равна n > 1,
существует такое натуральное m, что P(m) + P(−m) > 2m. Тогда подойдут числа a = m,
b = P(m) + P(−m) − m. Действительно, тогда b > a > 0, и по модулю a + b = P(m) + P(−m)
верно сравнение P(a) + P(b) ≡ P(a) + P(−a) = P(m) + P(−m) ≡ 0.
3