Задание олимпиады: разложение чисел по сумме цифр и равенство сумм сте

Докажем данное утверждение индукцией по 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, получается такой любопытный ряд равенств: