Задача 73590

Темы:    [ Десятичная система счисления ] [ Суммы числовых последовательностей и ряды разностей ] [ Индукция (прочее) ]

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

Условие

Все натуральные числа, в десятичной записи которых не больше n цифр, разбили на два множества следующим образом. В первое множество входят числа с нечётной суммой цифр, а во второе — c чётной суммой цифр. Докажите, что для любого натурального числа k £ n сумма k-х степеней всех чисел первого множества равна сумме k-х степеней всех чисел второго множества.

Решение

Докажем данное утверждение индукцией по n. Условимся, рассматривая не более чем n-значные числа, дописывать перед каждым нули так, чтобы все числа стали n-значными.

Справедливость утверждения при n=2 (тогда k может принимать только одно значение k = 1) проверить нетрудно:

Переход от n к n + 1 ненамного сложнее.
Чтобы избежать неясностей и большого числа многоточий, удобно использовать знак суммы – .
Будем обозначать n-значные числа с четной суммой цифр (начиная с 00...00) – буквой a , с нечетной суммой цифр (начиная с 00...01) – буквой b. Нетрудно видеть, что каждая из переменных a и b может принимать 5 · 10^n-1 различных значений.
Пусть, далее, A принимает значения A = p · 10ⁿ , где p – одно из чисел 0, 2, 4, 6, 8; B – значения B = q · 10ⁿ , где q – одно из чисел 1, 3, 5, 7,9 . Мы должны доказать, что при каждом натуральном k < n
(A+b)^k+ (B+a)^k= (A+a)^k+ (B+b)^k (*) (каждая сумма берется по всевозможным парам значений букв, стоящих в круглой скобке под знаком ) при условии, что уже доказано равенство сумм a^l и b^l для всех l ≤ n - 1: a^k= b^k=S_k.
Раскроем в (*) каждую скобку, пользуясь формулой
(X+y)^k=X^k+C_k¹ X^k-1 y+...+C_k¹ X^k-1 y¹+...+y^k, и проверим, что для каждого отдельного l суммы членов вида X^{k - l} y^l в правой и левой частях равенства равны (нам не нужно знать формулы для вычисления C_k^l (так называемых "биномиальных коэффициентов"); важно лишь, что это числа, не зависящие от переменных X и y .) – коэффициент C_k^l мы не пишем:
Заметим, что нашу первоначальную выкладку для n=2 с помощью аналогичных обозначений можно записать так:
при k = 1 остаются только первый и последний члены, соответствующие l = 0 и l = k).

Нетрудно видеть, что утверждение задачи справедливо не только в десятичной, но и в любой другой системе счисления с основанием d , где d – четное число (подумайте, где в нашем решении используется четность основания d = 10).
Если взять d=2, получается такой любопытный ряд равенств:

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

журнал
Название	"Квант"
год
Год	1970
выпуск
Номер	11
Задача
Номер	М55