ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116402
Темы:    [ Произведения и факториалы ]
[ Индукция (прочее) ]
[ Основная теорема арифметики. Разложение на простые сомножители ]
[ Многочлены (прочее) ]
[ Комплексные числа помогают решить задачу ]
[ Линейная и полилинейная алгебра ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

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


Решение 1

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


Решение 3

Для знатоков. Рассмотрим многочлены   Pk(x) = xk–1 + xk–2 + ... + x + 1,   Qn(x) = P2(x)... Pn(x)   (над полем комплексных чисел). Достаточно доказать, что Qm+n(x) делится на Qn(x)Qm(x). Действительно, Qn(x)Qm(x) – приведённый многочлен, частное – многочлен с целыми коэффициентами. Подставив  x = 10,  получаем утверждение задачи.

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

  Второй способ. Достаточно доказать, что Pn+m(x)Pn+m–1(x)...Pm+1(x) делится на Qn(x). Это эквивалентно тому, что многочлен
U(x) = (xn+m – 1)(xn+m–1 – 1)...(xm+1 – 1)   делится на  V(x) = (xn – 1)(xn–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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .