Изначально на доске были написаны одночленs  1, x, x², ..., xⁿ.  Договорившись заранее, k мальчиков каждую минуту одновременно вычисляли каждый сумму каких-то двух многочленов, написанных на доске, и результат дописывали на доску. Через m минут на доске были написаны, среди прочих, многочлены  S₁ = 1 + x,  S₂ = 1 + x + x²,  S₃ = 1 + x + x² + x³,  ...,  S_n = 1 + x + x² + ... + xⁿ.  Докажите, что  

   Решение

Темы:    [ Многочлены (прочее) ] [ Процессы и операции ] [ Ориентированные графы ] [ Подсчет двумя способами ] [ Индукция (прочее) ]

Сложность: 5- Классы: 10,11

Прислать комментарий

Условие

Изначально на доске были написаны одночленs  1, x, x², ..., xⁿ.  Договорившись заранее, k мальчиков каждую минуту одновременно вычисляли каждый сумму каких-то двух многочленов, написанных на доске, и результат дописывали на доску. Через m минут на доске были написаны, среди прочих, многочлены  S₁ = 1 + x,  S₂ = 1 + x + x²,  S₃ = 1 + x + x² + x³,  ...,  S_n = 1 + x + x² + ... + xⁿ.  Докажите, что  

Решение

  Построим граф, соответствующий конечной ситуации на доске: если многочлен P появился как сумма многочленов Q и R, то проведём стрелки из P в Q и R. Если из многочлена F ведёт ориентированный путь в G, будем говорить, что G участвует в F (в частности, сам F участвует в F). Нетрудно видеть в этом случае, что все коэффициенты многочлена F – G неотрицательны.
  Можно считать, что каждый многочлен на доске – сумма различных степеней x: если какой-то коэффициент многочлена не меньше 2, то и у всех, в которых он участвует, соответствующий коэффициент также будет не меньше 2. Значит, он не участвует в суммах вида S_i.
  Каждый из многочленов  S₁, ..., S_n  назовём финальным. Каждый из многочленов, участвующих в S_n (то есть в сумме всех исходных одночленов), назовём существенным.
  Покажем индукцией по p, что в многочлене с p ненулевыми коэффициентами участвуют ровно  2p – 1  многочленов (из которых p одночленов); отсюда будет следовать, что количество существенных многочленов равно  2n + 1.  База  (p = 1)  очевидна.
  Шаг индукции. Пусть многочлен P был получен на некотором шаге как сумма Q и R, и количества ненулевых коэффициентов в P, Q и R равны p, q и r соответственно; тогда  p = q + r.  По предположению индукции, в Q и R участвуют  2q – 1  и  2r – 1  многочленов, среди которых нет совпадающих (поскольку в Q и R нет общих одночленов). Тогда в P, с учётом самого P, участвуют  (2q – 1) + (2r – 1) + 1 = 2p – 1  многочленов.
  Покажем, что в каждую минуту на доске появлялось не более одного финального существенного многочлена. Действительно, пусть в некоторый момент появились одновременно существенные многочлены S_p и S_q  (p < q).  Рассмотрим первый момент, когда на доске появился многочлен P, в котором одновременно участвуют и S_p и S_q; тогда он появился как сумма двух многочленов, каждый из которых содержит одночлен x^p. Но тогда коэффициент при x^p в P не меньше 2, что невозможно.
  Итак, на доске есть n финальных и  2n + 1  существенных многочленов, при этом не больше m из них являются и теми и другими. Значит, общее количество многочленов на доске не меньше чем  n + (2n + 1) – m.  С другой стороны, исходно на доске был  n + 1  многочлен, а добавилось не больше чем mk. Значит,  (n + 1) + mk ≥ n + (2n + 1) – m,  или  m(k + 1) ≥ 2n.

Замечания

Если зафиксировать натуральное k, то при всех достаточно больших n оценка в задаче точна.

Источники и прецеденты использования