|
|
 |
Условие
Обозначим через 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 с ненулевыми коэффициентами. Поскольку mi ≤ ni < 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. Тогда требуемое условие равносильно тому, что m0 ≤ n0, m1 ≤ n1,
m2 ≤ n2 и т. д. Значит, 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.
