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

Проект МЦНМО
при участии
школы 57
Задача 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 · 10n-1 различных значений.
Пусть, далее, A принимает значения A = p · 10n , где p – одно из чисел 0, 2, 4, 6, 8; B – значения B = q · 10n , где q – одно из чисел 1, 3, 5, 7,9 . Мы должны доказать, что при каждом натуральном k < n
(A+b)k+ (B+a)k= (A+a)k+ (B+b)k (*)
(каждая сумма берется по всевозможным парам значений букв, стоящих в круглой скобке под знаком ) при условии, что уже доказано равенство сумм al и bl для всех l ≤ n - 1: ak= bk=Sk.
Раскроем в (*) каждую скобку, пользуясь формулой
(X+y)k=Xk+Ck1 Xk-1 y+...+Ck1 Xk-1 y1+...+yk,
и проверим, что для каждого отдельного l суммы членов вида Xk - l yl в правой и левой частях равенства равны (нам не нужно знать формулы для вычисления Ckl (так называемых "биномиальных коэффициентов"); важно лишь, что это числа, не зависящие от переменных X и y .) – коэффициент Ckl мы не пишем:
Заметим, что нашу первоначальную выкладку для n=2 с помощью аналогичных обозначений можно записать так:
при k = 1 остаются только первый и последний члены, соответствующие l = 0 и l = k).

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

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

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

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

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