Разделы 
Дополнительно
Задача по математике - 2004
2019-01-23 
Даны многочлены $f(x)$ и $g(x)$ с целыми неотрицательными коэффициентами, $m$ - наибольший коэффициент многочлена $f$. Известно, что для некоторых натуральных чисел $а < b$ имеют место равенства $f(а) = g(a)$ и $f(b) = g(b)$. Докажите, что если $b > m$, то многочлены $f$ и $g$ совпадают.
Решение:
Предположим что $f \neq g$. Пусть
$f(x) = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x + c_0$
и
$g(x) = d_kx^k + d_{k-1}x^{k-1} + \cdots + d_1x + d_0$.
Поскольку $0 \leq c_i \leq m < b,$ в $b$-ичной системе счисления число $f(b)$ будет записываться как $\overline{c_nc_{n-1} \cdots c_1c_0}$. Если все коэффициенты многочлена $g$ также меньше $b$, то из единственности записи числа $f(b) = g(b)$ в $b$-ичной системе счисления мы можем заключить, что коэффициенты многочленов $f$ и $g$ совпадают, а значит, $f = g$. Пусть $i$ - наименьший номер, для которого $d_i > b$. Тогда $d_i = b_q+r$. Рассмотрим вместо многочлена $g$ новый многочлен $g_1$, у которого коэффициент $d_i$ заменен на $r$, а коэффициент $d_{i+1}$ - на $d_{i+1} + q$. Тогда $g_1(b) = g(b)$ не изменится, а $g_1(a) < g(a),$ ибо
$d_ia^i + d_{i+1}a^{i+1} = (bq + r)a^i + d_{i+1}a^{i+1} > (aq + r)a^i + d_{i+1}a^{i+1} = ra^i + (d_{i+1} + q)a^{i+1}$.
Далее продолжим эту процедуру со следующим номером $i$. На каждом шаге $i$ увеличивается хотя бы на 1, и всегда не больше $n$, поэтому не более чем через $n$ шагов процесс остановится и мы придем к некоторому многочлену $g_j$, у которого все коэффициенты будут целыми неотрицательными и меньшими $b$. Тогда по единственности записи числа $f(b) = g_j(b)$ в $b$-ичной системе счисления следует, что многочлены $f$ и $g_j$ совпадают, но это невозможно, ибо $f(a) = g(a) > g_j(a)$. Противоречие.
Даны многочлены $f(x)$ и $g(x)$ с целыми неотрицательными коэффициентами, $m$ - наибольший коэффициент многочлена $f$. Известно, что для некоторых натуральных чисел $а < b$ имеют место равенства $f(а) = g(a)$ и $f(b) = g(b)$. Докажите, что если $b > m$, то многочлены $f$ и $g$ совпадают.
Решение:
Предположим что $f \neq g$. Пусть
$f(x) = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x + c_0$
и
$g(x) = d_kx^k + d_{k-1}x^{k-1} + \cdots + d_1x + d_0$.
Поскольку $0 \leq c_i \leq m < b,$ в $b$-ичной системе счисления число $f(b)$ будет записываться как $\overline{c_nc_{n-1} \cdots c_1c_0}$. Если все коэффициенты многочлена $g$ также меньше $b$, то из единственности записи числа $f(b) = g(b)$ в $b$-ичной системе счисления мы можем заключить, что коэффициенты многочленов $f$ и $g$ совпадают, а значит, $f = g$. Пусть $i$ - наименьший номер, для которого $d_i > b$. Тогда $d_i = b_q+r$. Рассмотрим вместо многочлена $g$ новый многочлен $g_1$, у которого коэффициент $d_i$ заменен на $r$, а коэффициент $d_{i+1}$ - на $d_{i+1} + q$. Тогда $g_1(b) = g(b)$ не изменится, а $g_1(a) < g(a),$ ибо
$d_ia^i + d_{i+1}a^{i+1} = (bq + r)a^i + d_{i+1}a^{i+1} > (aq + r)a^i + d_{i+1}a^{i+1} = ra^i + (d_{i+1} + q)a^{i+1}$.
Далее продолжим эту процедуру со следующим номером $i$. На каждом шаге $i$ увеличивается хотя бы на 1, и всегда не больше $n$, поэтому не более чем через $n$ шагов процесс остановится и мы придем к некоторому многочлену $g_j$, у которого все коэффициенты будут целыми неотрицательными и меньшими $b$. Тогда по единственности записи числа $f(b) = g_j(b)$ в $b$-ичной системе счисления следует, что многочлены $f$ и $g_j$ совпадают, но это невозможно, ибо $f(a) = g(a) > g_j(a)$. Противоречие.
