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

Проект МЦНМО
при участии
школы 57
Задача 116008
Темы:    [ Делимость чисел. Общие свойства ]
[ Суммы числовых последовательностей и ряды разностей ]
[ Интерполяционный многочлен Лагранжа ]
[ Индукция (прочее) ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Дана функция f(x), значение которой при любом целом x целое. Известно, что для любого простого числа p существует такой многочлен Qp(x) степени, не превышающей 2013, с целыми коэффициентами, что  f(n) – Qp(n)  делится на p при любом целом n. Верно ли, что существует такой многочлен g(x) с вещественными коэффициентами , что  g(n) = f(n)  для любого целого n?


Решение 1

  Для функции h(x) обозначим Δh(x) = h(x + 1) – h(x).

  Лемма. Если Δh(x) в целых точках совпадает с многочленом степени не более  m – 1,  то h(x) в целых точках совпадает с многочленом степени не более m.
  Доказательство. Индукция по m. База:  m = 1.  Если Δh(x) равно константе c в целых точках, то  h(x) = h(0) + cx  при всех целых x.
  Шаг индукции. Пусть Δh(x) в целых точках совпадает с многочленом степени не более m и коэффициентом при xm, равным a (возможно, нулевым). Обозначим  h0(x) = h(x) – 1/(m+1) ax(x – 1)(x – 2)...(x – m + 1)(x – m).  Заметим, что  Δh0(x) = Δh(x) – ax(x – 1)(x – 2)...(x – m + 1)  равно многочлену степени не более  m – 1  в целых точках. Следовательно, по предположению индукции, h0(x) в целых точках совпадает с многочленом степени не более m. Так как  h(x) – h0(x)  – многочлен степени не более  m + 1,  то и h(x) в целых точках совпадает с многочленом степени не более  m + 1. 

  Докажем теперь индукцией по k, что если в условиях задачи для каждого p многочлен Qp(x) имеет степень, не большую k, то f(x) в целых точках совпадает с некоторым многочленом, степень которого тоже не больше k.

 База:  k = 0.  В этом случае нам известно, что для каждого простого p существует такая константа Qp, что  f(x) – Qp  делится на p при любом целом x. Но тогда  (f(x) – Qp) – (f(0) – Qp) = f(x) – f(0)  делится на p при любом целом x и любом простом p. Такое может быть, только если
f(x) = f(0),  то есть f(x) постоянна на целых числах.
  Шаг индукции. Функция Δf(x) удовлетворяет условию предположения индукции, так как  Δf(x) – ΔQp(x)  делится на p при любом целом x,
а ΔQp(x) – многочлен степени не выше  k – 1  (см. задачу 61433). Следовательно, Δf(x) совпадает в целых точках с многочленом степени не выше  k – 1.  По лемме f(x) совпадает в целых точках с многочленом степени не выше k.


Решение 2

  Выпишем интерполяционный многочлен Лагранжа, который совпадает с f(x) в точках 1, 2, ..., 2014 (см. задачу 61051):

  Положим  c = (2013!)².  Тогда коэффициенты многочлена cf0(x) – целые числа. Пусть p – простое число, большее c. Многочлен  cQp(x) – cf0(x)  имеет степень не выше 2013 и 2014 различных корней по модулю p – это числа 1, 2, ..., 2014 (поскольку  cQp(i) – cf0(i) = c(Qp(x) – f0(i))  при  1 ≤ i ≤ 2014).  Поэтому этот многочлен тождественно равен нулю по модулю p. Значит, при любом целом x число  c(f(x) – Qp(x)) + c(Qp(x) – f0(x)) = cf(x) – cf0(x)  делится на любое достаточно большое простое p. Следовательно,  f(x) = f0(x)  при всех целых x.

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

олимпиада
Название Московская математическая олимпиада
год
Год 2013
Номер 76
класс
Класс 10
задача
Номер 5

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

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