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

Проект МЦНМО
при участии
школы 57
Задача 109775
Темы:    [ Целочисленные и целозначные многочлены ]
[ Свойства коэффициентов многочлена ]
[ Системы счисления (прочее) ]
[ Деление с остатком ]
[ Метод спуска ]
Сложность: 5
Классы: 10,11
В корзину
Прислать комментарий

Условие

Автор: Храбров А.

Даны многочлены  f(x) и g(x) с целыми неотрицательными коэффициентами, m – наибольший коэффициент многочлена  f. Известно, что для некоторых натуральных чисел  a < b  имеют место равенства  f(a) = g(a)  и  f(b) = g(b).  Докажите, что если  b > m,  то многочлены  f и g совпадают.


Решение

  Предположим что  f ≠ g:   f(x) = cnxn + cn–1xn–1 + ... + c1x + c0  и  g(x) = dkxk + dk–1xk–1 + ... + d1x + d0.  Поскольку  0 ≤ ci ≤ m < b,  в b-ичной системе счисления число  f(b) будет записываться как  cncn–1...c1c0.  Если все коэффициенты многочлена g также меньше b, то из единственности записи числа
f(b) = g(b)  в b-ичной системе счисления мы можем заключить, что коэффициенты многочленов  f и g совпадают, а значит,  f = g.  Но это противоречит предположению.
  Пусть i – наименьший номер, для которого  di > b.  Тогда  di = bq + r.  Рассмотрим вместо многочлена g новый многочлен g1, у которого коэффициент di заменён на r, а коэффициент di+1 – на  di+1 + q.  Тогда  g1(b) = g(b),  а  g1(a) < g(a),  ибо
diai + di+1ai+1 = (bq + r)ai + di+1ai+1 > (aq + r)ai + di+1ai+1 = rai + (di+1 + q)ai+1.  Далее продолжим эту процедуру со следующим номером i. На каждом шаге i увеличивается, поэтому не более чем через n шагов процесс остановится, и мы придём к некоторому многочлену gj, у которого все коэффициенты будут целыми неотрицательными и меньшими b. Тогда, как показано выше, многочлены  f и gj совпадают. Но это невозможно, ибо   f(a) = g(a) > gj(a). Противоречие.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2003
Этап
Вариант 5
Класс
Класс 11
задача
Номер 03.5.11.3

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

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