ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 110774
Темы:    [ Итерации ]
[ Целочисленные и целозначные многочлены ]
[ Многочлен n-й степени имеет не более n корней ]
[ Теорема Безу. Разложение на множители ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

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


Решение

  Лемма. Пусть  a1, a2, ..., am  – различные числа, а числа  b1, b2, ..., bm  таковы, что  |aiaj| = |bibj|  для всех i, j от 1 до m. Тогда найдётся такая линейная функция f(x), что  bi = f(ai)  для всех i от 1 до m.
  Доказательство. Предположим, что в равенстве  |aiaj| = |bibj|  для пар различных индексов  (r, s)  и  (s, t)  модуль раскрывается с разным знаком, то есть  aras = br – bs,  а  as – at = bt – bs.  Складывая, получим  ar – at = br + bt – 2bs.  Но  ar – at = ±(br – bt),  откуда  bs = br  или   bs = bt,  а значит, и
as = ar  или  as = at.  Противоречие.
  Следовательно если  a2a1 = b2b1,  то  aia1 = bib1  для всех i, и можно взять  f(x) = x + (b1a1).  Если же  a2a1 = b1b2,  то аналогично можно взять  f(x) = –x + (b1 + a1).

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .