Разделы 
Дополнительно
Задача по математике - 3251
2019-05-29 
Пусть $1 + x + x^2 + \cdots + x^n = F(x)G(x)$, где $F$ и $G$ — многочлены, коэффициенты которых — нули и единицы. Докажите, что один из многочленов $F(x), G(x)$ представим в виде $(1 + x + x^2 + \cdots + x^k) T(x)$, где $T$ — также многочлен с коэффициентами 0 и 1 ($k > 0$).
Решение:
Обозначим
$F(x) = a_0 + a_1x + a_2x^2 + \cdots$,
$G(x) = b_0 + b_1x + b_2x^2 + \cdots$.
Тогда, по условию,
$(a_0 + a_1x + a_2x^2 + \cdots)(b_0 + b_1x + b_2x^2 + \cdots) = 1 + x + x^2 + \cdots + x^n$.
Свободный член произведения равен произведению свободных членов, т. е. $a_0 \cdot b_0 = 1$. Значит, $a_0 = 1$ и $b_0 = 1$. Коэффициент произведения $F(x) \cdot G(x)$ при первой степени $x$ вычисляется по формуле $a_0b_1 + a_1b_0$. Поскольку он равен 1, то либо $a_1 = 1, b_1 = 0$, либо $a_1 = 0, b_1 = 1$. Для определенности предположим, что $a_1 = 1$ и $b_1 = 0$.
Если все коэффициенты $a_i$ многочлена $F(x)$ равны 1, то задача решена. Если же среди них присутствует 0, то рассмотрим наименьшее $m$, для которого $a_m = 0$. Тогда
$a_0 = a_1 = \cdots = a_{m-1} = 1$, $a_m = 0$.
Мы хотим доказать, что многочлен $F(x)$ представим в виде $(1 + x + x^2 + \cdots + x^{m-1})T(x)$, где $T$ — также многочлен с коэффициентами 0 и 1.
Если какой-нибудь коэффициент $b_i$ равен единице, где $1 \leq i < m$, то сразу видим, что коэффициент при $x_i$ больше 1: член $x_i$ произведения $F(x)G(x)$ можно получить как умножая $a_0$ на $b_ix_i$, так и умножая $a_i$ на $b_0x^l$. Значит, $b_i = 0$ при $1 \leq l < m$. Теперь ясно, что $b_m = 1$: в противном случае коэффициент при $x^m$ был бы равен 0.
Последовательность коэффициентов $a_0, a_1$, можно представлять себе как последовательность чередующихся отрезков: сначала отрезок из единиц, потом отрезок из нулей, потом снова из единиц и т. д. Рассмотрим один из таких отрезков: $a_r = \cdots = a_{r+s-1} = 1$, причем $a_{r-1} = 0, a_{r+s} = 0$. Длина $s$ этого отрезка не может быть больше $m$: в противном случае член $x^{r+m}$ произведения можно получить как умножая $a_rx^r$ на $b_mx^m$, так и умножая $a_{r+m}x^{r+m}$ на $b_0$.
Докажем, что эта длина не может быть меньше $m$. Предположим противное. Рассмотрим самый левый такой (окаймленный нулями) отрезок из единиц $a_r, \cdots, a_{r+s-1}$, длина $s$ которого меньше, чем $m$.
Посмотрим, как получается член $x^{r+s}$ произведения $F(x) \cdot G(x)$. Поскольку $a_{r+s} = 0$, он должен получаться при умножении какого-то члена вида $a_ux^u$ на некоторый член $b_vx^v$, $v > 0$. (Разумеется, $u + v = r + s$.)
Нетрудно понять, что если $u \neq 0$, то $a_{u-1} = 0$ (случай $u = 0$ мы оставляем читателю) — в противном случае можно получить $x^{r+s-1}$ двумя способами: $a_{u-1}x^{u-1} \cdot b_vx^v = a_{r+s-1}x^{r+s-1} \cdot 1$. Значит, должен существовать отрезок из единиц $a_u, \cdots, a_{u+m-1}$. (Длина его равна $m$, поскольку он расположен левее отрезка $a_r, \cdots, a_{r+s-1}$.)
Но число $r + m - v = r + m - (r + s - u) = u + (m - s)$ лежит на отрезке $u, \cdots, u + m - 1$, так что $a_{r+m-v} = 1$, и мы приходим к противоречию: $a_rx^r \cdot b_mx^m = a_{r+m-v}x^{r+m-v} \cdot b_vx^v$.
Следовательно, все отрезки из единиц имеют одну и ту же длину $m$. Деление «уголком» (см. факт 19) убеждает нас в том, что многочлен $F$ представим в виде произведения многочлена $1 + x + \cdots + x^{m-1}$ на многочлен, все коэффициенты которого — нули или единицы.
Ответ: Да, существует.
Пусть $1 + x + x^2 + \cdots + x^n = F(x)G(x)$, где $F$ и $G$ — многочлены, коэффициенты которых — нули и единицы. Докажите, что один из многочленов $F(x), G(x)$ представим в виде $(1 + x + x^2 + \cdots + x^k) T(x)$, где $T$ — также многочлен с коэффициентами 0 и 1 ($k > 0$).
Решение:
Обозначим
$F(x) = a_0 + a_1x + a_2x^2 + \cdots$,
$G(x) = b_0 + b_1x + b_2x^2 + \cdots$.
Тогда, по условию,
$(a_0 + a_1x + a_2x^2 + \cdots)(b_0 + b_1x + b_2x^2 + \cdots) = 1 + x + x^2 + \cdots + x^n$.
Свободный член произведения равен произведению свободных членов, т. е. $a_0 \cdot b_0 = 1$. Значит, $a_0 = 1$ и $b_0 = 1$. Коэффициент произведения $F(x) \cdot G(x)$ при первой степени $x$ вычисляется по формуле $a_0b_1 + a_1b_0$. Поскольку он равен 1, то либо $a_1 = 1, b_1 = 0$, либо $a_1 = 0, b_1 = 1$. Для определенности предположим, что $a_1 = 1$ и $b_1 = 0$.
Если все коэффициенты $a_i$ многочлена $F(x)$ равны 1, то задача решена. Если же среди них присутствует 0, то рассмотрим наименьшее $m$, для которого $a_m = 0$. Тогда
$a_0 = a_1 = \cdots = a_{m-1} = 1$, $a_m = 0$.
Мы хотим доказать, что многочлен $F(x)$ представим в виде $(1 + x + x^2 + \cdots + x^{m-1})T(x)$, где $T$ — также многочлен с коэффициентами 0 и 1.
Если какой-нибудь коэффициент $b_i$ равен единице, где $1 \leq i < m$, то сразу видим, что коэффициент при $x_i$ больше 1: член $x_i$ произведения $F(x)G(x)$ можно получить как умножая $a_0$ на $b_ix_i$, так и умножая $a_i$ на $b_0x^l$. Значит, $b_i = 0$ при $1 \leq l < m$. Теперь ясно, что $b_m = 1$: в противном случае коэффициент при $x^m$ был бы равен 0.
Последовательность коэффициентов $a_0, a_1$, можно представлять себе как последовательность чередующихся отрезков: сначала отрезок из единиц, потом отрезок из нулей, потом снова из единиц и т. д. Рассмотрим один из таких отрезков: $a_r = \cdots = a_{r+s-1} = 1$, причем $a_{r-1} = 0, a_{r+s} = 0$. Длина $s$ этого отрезка не может быть больше $m$: в противном случае член $x^{r+m}$ произведения можно получить как умножая $a_rx^r$ на $b_mx^m$, так и умножая $a_{r+m}x^{r+m}$ на $b_0$.
Докажем, что эта длина не может быть меньше $m$. Предположим противное. Рассмотрим самый левый такой (окаймленный нулями) отрезок из единиц $a_r, \cdots, a_{r+s-1}$, длина $s$ которого меньше, чем $m$.
Посмотрим, как получается член $x^{r+s}$ произведения $F(x) \cdot G(x)$. Поскольку $a_{r+s} = 0$, он должен получаться при умножении какого-то члена вида $a_ux^u$ на некоторый член $b_vx^v$, $v > 0$. (Разумеется, $u + v = r + s$.)
Нетрудно понять, что если $u \neq 0$, то $a_{u-1} = 0$ (случай $u = 0$ мы оставляем читателю) — в противном случае можно получить $x^{r+s-1}$ двумя способами: $a_{u-1}x^{u-1} \cdot b_vx^v = a_{r+s-1}x^{r+s-1} \cdot 1$. Значит, должен существовать отрезок из единиц $a_u, \cdots, a_{u+m-1}$. (Длина его равна $m$, поскольку он расположен левее отрезка $a_r, \cdots, a_{r+s-1}$.)
Но число $r + m - v = r + m - (r + s - u) = u + (m - s)$ лежит на отрезке $u, \cdots, u + m - 1$, так что $a_{r+m-v} = 1$, и мы приходим к противоречию: $a_rx^r \cdot b_mx^m = a_{r+m-v}x^{r+m-v} \cdot b_vx^v$.
Следовательно, все отрезки из единиц имеют одну и ту же длину $m$. Деление «уголком» (см. факт 19) убеждает нас в том, что многочлен $F$ представим в виде произведения многочлена $1 + x + \cdots + x^{m-1}$ на многочлен, все коэффициенты которого — нули или единицы.
Ответ: Да, существует.
