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

Проект МЦНМО
при участии
школы 57
Задача 116706
Темы:    [ Треугольник Паскаля и бином Ньютона ]
[ Простые числа и их свойства ]
[ Произведения и факториалы ]
Сложность: 5-
Классы: 11
В корзину
Прислать комментарий

Условие

Обозначим через  S(n, k)  количество не делящихся на k коэффициентов разложения многочлена  (x + 1)n  по степеням x.
  а) Найдите  S(2012, 3).
  б) Докажите, что  S(20122011, 2011)  делится на 2012.


Решение

  Пусть p – простое число и  n = n0 + n1p + n0p² + ... + nkpk = (nk...n1n0)p  – p-ичное представление числа n. Покажем, что
S(n, p) = (n0 + 1)(n1 + 1)...(nk + 1).

  Первый способ. Будем рассматривать многочлены над полем вычетов Zp по модулю p. Здесь  S(n, p)  равно количеству ненулевых коэффициентов многочлена  (x + 1)n.  Заметим, что биномиальный коэффициент     делится на p при  m = 1, ..., p – 1,  а     не делится на p при любом  n < p,
m
= 0, ..., n. .
  Отсюда сразу следует, что над Zp   (x + 1)p = xp + 1,  (x + 1)p² = (xp + 1)p = xp² + 1,  ...,  (x + 1)pm = xpm + 1,  ...
  Поэтому   (x + 1)n = (x + 1)n0(x + 1)n1p...(x + 1)nkpk = (x + 1)n0(xp + 1)n1...(xpk + 1)nk.   Раскладывая  (xpi + 1)ni  по биному, мы получаем многочлен от xpi, все коэффициенты которого, как сказано выше, отличны от нуля. Этих коэффициентов ровно  ni + 1.  Перемножив теперь все скобки мы получим сумму  (n0 + 1)(n1 + 1)...(nk + 1)  одночленов вида xm0xm1p...xmkpk с ненулевыми коэффициентами. Поскольку  mini < p,  среди этих одночленов нет одинаковых, то есть "приведения подобных" не происходит и число  S(n, p)  ненулевых коэффициентов многочлена  (x + 1)n  равно
(n0 + 1)(n1 + 1)...(nk + 1).

  Второй способ. Надо подсчитать, сколько чисел среди   ,  m = 0, 1, ..., n  не делятся на p.

  Степень простого числа p, на которую делится n!, равна     (см. задачу 60553). Поэтому степень p, на которую делится

,  равна   ...

  Но  [a + b] ≥ [a] + [b]  для любых действительных чисел a и b. При этом  [a + b] = [a] + [b]  тогда и только тогда, когда  {a} + {b} < 1,  то есть
{a} ≤ {a + b}.  Получаем, что все слагаемые в выписанной выше сумме неотрицательны, и для того, чтобы      не делилось на p, надо, чтобы все они равнялись 0, а это равносильно тому, что     и т. д.
  Пусть  n = (nk...n1n0)p  и  m = (mk...m1m0)p  – p-ичные представления чисел n и m. Тогда требуемое условие равносильно тому, что  m0n0m1n1,
m2n2  и т. д. Значит, mi может принимать ровно  ni + 1  значений. Всего вариантов для m:  (n0 + 1)(n1 + 1)...(nk + 1).

  Вернёмся к решению задачи.

  а) Так как 3 – простое число, а  2012 = (2202112)3,  то  S(2012,3) = 34·2² = 324.

  б) Число 2011 простое, а  
  В этой сумме все слагаемые, начиная с четвёртого, делятся на 20114, а первые три слагаемых дают  1 + 2011² + 1005·2011³.  Это означает, что в представлении числа 20122011 в системе счисления с основанием 2011 младшие разряды такие:  n0 = 1,  n1 = 0,  n2 = 1,  n3 = 1005.  Поэтому
S(20122011, 2011)  делится на  (n0 + 1)(n3 + 1) = 2012.


Ответ

а) 324.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 75
Год 2012
класс
Класс 11
задача
Номер 5

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

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