Версия для печати
Убрать все задачи

---

Пусть P(x) – многочлен со старшим коэффициентом 1, а последовательность целых чисел  a₁, a₂, ...  такова, что  P(a₁)= 0,  P(a₂) = a₁,  P(a₃) = a₂  и т. д. Числа в последовательности не повторяются. Какую степень может иметь P(x)?

   Решение

Темы:    [ Делимость чисел. Общие свойства ] [ Раскладки и разбиения ] [ Разбиения на пары и группы; биекции ] [ Индукция (прочее) ]

Сложность: 4+ Классы: 8,9,10

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

Условие

Пусть n и b – натуральные числа. Через  V(n, b)  обозначим число разложений n на сомножители, каждый из которых больше b (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12,  так что  V(36, 2) = 5).  Докажите, что  V(n, b) < ⁿ/_b.

Решение

  Индукция по n. База  (n = 1)  очевидна:  V(1, b) = 0.
  Шаг индукции. Предположим теперь, что это неравенство верно при всех  m < n. 
  Для каждого делителя  k > b  числа n рассмотрим все разложения числа n, в которых минимальный сомножитель равен k. Количество таких разложений равно  V(ⁿ/_k, k – 1).  Исключение составляет случай  k = n   – такое разложение одно, а  V(ⁿ/_n, n – 1) = 0.  Следовательно,

Замечания

12 баллов

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