|
|
 |
Условие
Пусть 1 + x + x² + ... + xn–1 = F(x)G(x), где F и G – многочлены, коэффициенты которых – нули и единицы (n > 1).
Докажите, что один из многочленов F, G представим в виде (1 + x + x² + ... + xk–1)T(x), где T(x) – также многочлен с коэффициентами 0 и 1 (k > 1).
Решение
Пусть F(x) = a0 + a1x + a2x² + ..., G(x) = b0 + b1x + b2x² + ..., F(x)G(x) = c0 + c1x + c2x² + ... + cn–1xn–1 (c0 = c1 = c2 = ... = cn–1 = 1).
Очевидно, a0 = b0 = 1. Допустим, что b1 = ... = bk–1 = 1 , а bk = 0, k ≥ 2 (для одного из многочленов F и G это обязательно верно). При этом
a1 = a2 = ... = ak–1 = 0, ak = 1.
Покажем, что тогда в многочлене G каждый отрезок из подряд идущих единичных коэффициентов, окаймлённый нулями, имеет длину k. Это и значит, что многочлен G представим в виде произведения многочлена 1 + x + ... + xk–1 на многочлен, все коэффициенты которого – нули или единицы.
Отрезок из единиц не может быть длиннее k, так как если bi = bi+1 = ... = bi+k = 1, то ci+k ≥ a0bi+k + akbi = 2, что противоречит условию.
Предположим, что отрезки длины меньше k существуют и рассмотрим первый такой отрезок (с наименьшими номерами коэффициентов):
bi+1 = bi+2 = ... = bi+j = 1, bi = bi+j+1 = 0, 1 ≤ j < k.
Заметим, что найдутся такие p и q, что ap = bq = 1 и p + q = i + j + 1 (так как ci+j+1 = 1). При этом p > 0 (поскольку bi+j+1 = 0), значит, p ≥ k. Поэтому
q ≤ i + j + 1 – k < i + 1. Это значит, что q входит в один из предыдущих отрезков единиц, а он имеет длину k. Следовательно, в этот же отрезок входит либо q – j, либо q – j + k.
В первом случае ci+1 ≥ a0bi+1 + apbq–j = 2, во втором ci+k+1 ≥ akbi+1 + apbq–j+k = 2. Противоречие.
Замечания
1. Понять это решение (и придумать его) проще, если рисовать отрезки и смотреть, что происходит при сдвигах. Для геометра рассматриваемая задача может быть сформулирована так:
Даны отрезок длины L и некоторая система S содержащихся в нем непересекающихся друг с другом отрезочков. Доказать, что если отрезок можно покрыть параллельными сдвигами системы S (чтобы каждая точка отрезка была покрыта и отрезочки не накладывались бы друг на друга внутренними точками, а только "состыковывались" бы в концах), то все отрезочки системы S имеют одну и ту же длину.
2. 8 баллов.
3. Ср. с задачей М1598 из Задачника "Кванта".
