|
|
 |
Условие
Даны многочлены 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). Противоречие.
