Олимпиадная задача о разложении суммы степеней многочленов с коэффициентами 0 и 1 для 9-10 классов

  Пусть   F(x) = a₀ + a₁x + a₂x² + ...,   G(x) = b₀ + b₁x + b₂x² + ...,   F(x)G(x) = c₀ + c₁x + c₂x² + ... + c_n–1x^n–1  (c₀ = c₁ = c₂ = ... = c_n–1 = 1).

  Очевидно,  a₀ = b₀ = 1.  Допустим, что  b₁ = ... = b_k–1 = 1 , а  b_k = 0,  k ≥ 2  (для одного из многочленов F и G это обязательно верно). При этом

a₁ = a₂ = ... = a_k–1 = 0,  a_k = 1.

  Покажем, что тогда в многочлене G каждый отрезок из подряд идущих единичных коэффициентов, окаймлённый нулями, имеет длину k. Это и значит, что многочлен G представим в виде произведения многочлена  1 + x + ... + x^k–1  на многочлен, все коэффициенты которого – нули или единицы.

  Отрезок из единиц не может быть длиннее k, так как если  b_i = b_i+1 = ... = b_i+k = 1,  то  c_i+k ≥ a₀b_i+k + a_kb_i = 2,  что противоречит условию.

  Предположим, что отрезки длины меньше k существуют и рассмотрим первый такой отрезок (с наименьшими номерами коэффициентов):

b_i+1 = b_i+2 = ... = b_i+j = 1,  b_i = b_i+j+1 = 0,  1 ≤ j < k.

  Заметим, что найдутся такие p и q, что  a_p = b_q = 1  и  p + q = i + j + 1  (так как  c_i+j+1 = 1).  При этом  p > 0  (поскольку  b_i+j+1 = 0),  значит,  p ≥ k.  Поэтому

q ≤ i + j + 1 – k < i + 1.  Это значит, что q входит в один из предыдущих отрезков единиц, а он имеет длину k. Следовательно, в этот же отрезок входит либо  q – j,  либо  q – j + k.

  В первом случае  c_i+1 ≥ a₀b_i+1 + a_pb_q–j = 2,  во втором  c_i+k+1 ≥ a_kb_i+1 + a_pb_q–j+k = 2.  Противоречие.

Ответ задачи отсутствует