---

Показать решение

---

Скрыть решение

Решение

Пусть
F(x) = a₀ + a₁x + a₂x² + ... + a_mx^m,
G(x) = b₀ + b₁x + b₂x² + ... + b_n – m – 1xⁿ – m – 1,
F(x)G(x) = c₀ + c₁x + c₂x² + ... + c_n – 1xⁿ – 1.
Очевидно, a₀ = b₀ = 1. Допустим, что b₁ = ...= b_t – 1 = 1 и b_t = 0, t ≥ 2 (для одного из многочленов F и G это обязательно верно). При этом a₁ = a₂ = ... = a_t – 1 = 0, a_t = 1, b_t = b_t + 1 = ... = b_{2t – 1} = 0.
Покажем, что в многочлене G (т. е. в многочлене с ненулевым коэффициентом при x) каждый отрезок из подряд идущих единичных коэффициентов, окаймлённый нулями, имеет длину t, а каждый отрезок из нулей, окаймлённый единицами, — длину не меньше t.
Очевидно, что отрезок из единиц не может быть длиннее t, так как если b_i = b_i + 1 = ... = b_i + t = 1, то c_i + t ≥ a₀b_i + t + a_tb_i = 2, что противоречит условию. Теперь докажем оставшуюся часть утверждения индукцией по числу отрезков. Для первых отрезков из единиц и нулей оно верно. Рассмотрим очередной отрезок из единиц. Предположим, что b_i = 0, b_i + 1 = b_i + 2 = ... = b_i + k = 1, b_i + k + 1 = 0, причём 1 ≤ k < t. По предположению индукции, b_i – t + 1 = b_i + t = ... = b_i = 0. Тогда c_i + 1 = a₀b_i + 1, c_i + 2 = a₀b_i + 2, ..., c_i + k= a₀b_i + k. c_i + k + 1 = a_zb_y, где z ≥ t, поэтому y ≤ i + k + 1 – t ≤ i, следовательно, y ≤ i – t, так что z ≥ i + k + 1 – (i – t) = k + t + 1 > t. Кроме того, b_y – 1 = 0 (иначе c_i + k ≥ a₀b_i + k + a_zb_y – 1 = 2), отсюда по предположению индукции, b_y = b_y + 1 = ... = b_y + t – 1 = 1. Итак, имеем: c_i + t + 1 ≥ a_tb_i + 1 + a_zb_y + t – k = 2, так как y < y + t – k ≤ y + t – 1. Противоречие.
Рассмотрим очередной отрезок из нулей. Предположим, что b_i = 1, b_i + 1 = b_i + 2 = ... = b_i + k = 0, b_i + k + 1 = 1, причём 1 ≤ k < t. Тогда c_i + 1 = a_zb_y, где z ≥ t, y ≤ i + 1 – t ≤ i – 1. b_y – 1 = 0 (иначе c_i ≥ a₀b_i + a_zb_y – 1 = 2). Таким образом, по предположению индукции, b_y = b_y + 1 = ... = b_y + t – 1 = 1. Но в таком случае, c_i + k + 1 ≥ a₀b_i + k + 1 + a_zb_y + k = 2, так как y + 1 ≤ y + k < y + t. Противоречие.
Следовательно, многочлен G с коэффициентами b_i представим в виде произведения многочлена 1 + x + ... + x^t – 1 на многочлен, все коэффициенты которого — нули или единицы.