Задача 110774

Темы:    [ Итерации ] [ Целочисленные и целозначные многочлены ] [ Многочлен n-й степени имеет не более n корней ] [ Теорема Безу. Разложение на множители ]

Сложность: 4+ Классы: 10,11

Условие

Пусть P(x) – многочлен степени  n > 1  с целыми коэффициентами, k – произвольное натуральное число. Рассмотрим многочлен
Q_k(x) = P(P(...P(P(x))...))  (P применён k раз). Докажите, что существует не более n целых чисел t, при которых  Q_k(t) = t.

Решение

Автор: Канель-Белов А.Я.

  Лемма. Пусть  a₁, a₂, ..., a_m  – различные числа, а числа  b₁, b₂, ..., b_m  таковы, что  |a_i – a_j| = |b_i – b_j|  для всех i, j от 1 до m. Тогда найдётся такая линейная функция f(x), что  b_i = f(a_i)  для всех i от 1 до m.
  Доказательство. Предположим, что в равенстве  |a_i – a_j| = |b_i – b_j|  для пар различных индексов  (r, s)  и  (s, t)  модуль раскрывается с разным знаком, то есть  a_r – a_s = b_r – b_s,  а  a_s – a_t = b_t – b_s.  Складывая, получим  a_r – a_t = b_r + b_t – 2b_s.  Но  a_r – a_t = ±(b_r – b_t),  откуда  b_s = b_r  или   b_s = b_t,  а значит, и
a_s = a_r  или  a_s = a_t.  Противоречие.
  Следовательно если  a₂ – a₁ = b₂ – b₁,  то  a_i – a₁ = b_i – b₁  для всех i, и можно взять  f(x) = x + (b₁ – a₁).  Если же  a₂ – a₁ = b₁ – b₂,  то аналогично можно взять  f(x) = –x + (b₁ + a₁).

  Перейдём к решению задачи. Предположим, что найдутся такие различные целые числа  x₁, ..., x_n+1,  что  Q_k(x_i) = x_i  для i от 1 до  n + 1.  Тогда
x_i – x_j = Q_k–1(P(x_i)) – Q_k–1(P(x_j))  и по теореме Безу для целочисленных многочленов (см. решение задачи 35562) делится на  P(x_i) – P(x_j),  а  P(x_i) – P(x_j),  в свою очередь, делится на  x_i – x_j.  Отсюда  |x_i – x_j| = |P(x_i) – P(x_j)|,  и по лемме найдётся такая линейная функция f(x), что  P(x_i) = f(x_i)  для i от 1 до
n + 1,  то есть  x₁, ..., x_n+1  являются корнями многочлена  P(x) – f(x)  степени n. Противоречие.

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

олимпиада
Название	Международная Математическая Олимпиада
Год
Год	2006
задача
Номер	5