Учитель собирается дать детям задачу следующего вида. Он сообщит им, что он задумал многочлен P(x) степени 2017 с целыми коэффициентами, старший коэффициент которого равен 1. Затем он сообщит им k целых чисел n₁, n₂, ..., n_k и отдельно сообщит значение выражения  P(n₁)P(n₂)...P(n_k).  По этим данным дети должны найти многочлен, который мог бы задумать учитель. При каком наименьшем k учитель сможет составить задачу такого вида так, чтобы многочлен, найденный детьми, обязательно совпал бы с задуманным?

   Решение

Темы:    [ Линейные рекуррентные соотношения ] [ Цепные (непрерывные) дроби ] [ Индукция (прочее) ]

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

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

Условие

Докажите, что для чисел {x_n} из задачи 61297 можно в явном виде указать разложения в цепные дроби:  x_n+1 = [1;].
Оцените разность  |x_n – |.

Решение

  Подходящие дроби  ^P_k/_Qk  к разложению   = [1; (2)]  в цепную дробь удовлетворяют рекуррентным соотношениям  P_–1 = 1,  P₀ = 1,  P_k = 2P_k–1 + P_k–2;
Q_–1 = 0,  Q₀ = 1,  Q_k = 2Q_k–1 + Q_k–2  (см. задачи 60613, 60601). Отсюда по индукции легко вывести соотношения  P_k = Q_k + Q_k–1;  2Q_k = P_k + P_k–1.
  Пусть  x_n = ^P_k/_Qk,  где  k = 2^n–1 – 1.  Дробь x_n+1 получается из дроби     заменой последней двойки на  1 + ^P_k/_Qk.  По аналогии с формулой из решения задачи 60616 имеем

  Таким образом, {x_n} – последовательность из задачи 61297.
  Поскольку  Q_k > 2Q_k–1  при  k > 2,  то  Q_k > 2^k.
 

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