Задача 116402

Темы:    [ Произведения и факториалы ] [ Индукция (прочее) ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ Многочлены (прочее) ] [ Комплексные числа помогают решить задачу ] [ Линейная и полилинейная алгебра ]

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

Условие

Автор: Берштейн М.А.

Обозначим через [n]! произведение 1·11·111·...·11...11 – всего n сомножителей, в последнем – n единиц.
Докажите, что  [n + m]!  делится на произведение [n]!·[m]!.

Решение 1

  Пусть 1_k – число из k единиц, тогда  [m]! = 1_m·[m–1]!,  1_m+n = 10^m·1_n + 1_m.  Обозначим     Положим  [0]! = 1,  тогда C[0, n] и C[m, 0] определены и равны 1. Докажем индукцией по  m + n,  что число  C[m, n]  целое. База и случай  m = 0  или  n = 0  очевидны.
  Шаг индукции. Пусть  m, n ≥ 1  и для меньших значений  m + n  все доказано. Тогда число

        тоже целое.

Решение 2

  Пусть q – число, взаимно простое с 10,  k(q) = min {k| 1_k   кратно q}. Тогда 1_k кратно q тогда и только тогда, когда k кратно k(q). Поэтому из множителей вида 1_k, входящих в [n]!, на q делятся ровно  .   Из этого следует, что простое число  p ≠ 2, 5  входит в разложение [n]! на простые множители в степени  
  В силу неравенства     каждое простое число входит в разложение [n+m]! не в меньшей степени, чем в разложение [n]!·[m]!.

Решение 3

Для знатоков. Рассмотрим многочлены   P_k(x) = x^k–1 + x^k–2 + ... + x + 1,   Q_n(x) = P₂(x)... P_n(x)   (над полем комплексных чисел). Достаточно доказать, что Q_m+n(x) делится на Q_n(x)Q_m(x). Действительно, Q_n(x)Q_m(x) – приведённый многочлен, частное – многочлен с целыми коэффициентами. Подставив  x = 10,  получаем утверждение задачи.

  Первый способ. Корнями многочлена P_k(x) являются все (кроме единицы) корни k-й степени из единицы. Пусть ε – первообразный корень k-й степени из 1. Тогда он является корнем l-й степени тогда и только тогда, когда l кратно k. Поэтому множитель  x – ε  входит в разложение Q_m+n(x) на линейные множители в степени  [^m+n/_k],  а в Q_n(x)Q_m(x) – в степени    .   Следовательно, Q_m+n(x) делится на Q_n(x)Q_m(x).

  Второй способ. Достаточно доказать, что P_n+m(x)P_n+m–1(x)...P_m+1(x) делится на Q_n(x). Это эквивалентно тому, что многочлен
U(x) = (x^n+m – 1)(x^n+m–1 – 1)...(x^m+1 – 1)   делится на  V(x) = (xⁿ – 1)(x^n–1 – 1)...(x – 1).
  Поделим с остатком:  U(x) = W(x)V(x) + R(x),  где W(x) и R(x) – многочлены с целыми коэффициентами, и предположим, что  R(x) ≠ 0.  Поскольку
deg R(x) < deg V(x),  при больших натуральных k выполнено неравенство  0 < |R(k)| < |V(k)|,  то есть число U(k) не кратно V(k).
  Но, как известно, для любого простого числа p количество n-мерных подпространств в равно     Противоречие.

Замечания

1. См. также задачу М2166 из Задачника "Кванта" ("Квант", 2010, №1).
2. 9 баллов

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

олимпиада
Название	Турнир городов
Турнир
Дата	2009/2010
Номер	31
вариант
Вариант	осенний тур, сложный вариант, 10-11 класс
Задача
Номер	4