Развлечения с суммами цифр

Морозов Владимир Владимирович,
учитель математики и информатики
НОУ школы "Ступени", Москва.

Определение. У некоторого натурального числа n найдём его сумму цифр. У полученного числа снова найдём сумму цифр. Так будем продолжать до тех пор, пока не получится однозначное число.

Это число и назовём окончательной суммой цифр и обозначим s(n).

Например, s(45738465)=6.

Рассматривая таблицу квадратов натуральных чисел, замечаем, что в клетках, расположенных по диагоналям таблицы окончательная сумма цифр одна и та же. Например, в выделенных ячейках таблицы на рис. 1 окончательная сумма цифр равна 9. Возникает вопрос, всегда ли выполняется замеченная закономерность?

Ученик 9-го класса Груненко Л. написал программу для персонального компьютера для проверки или опровержения этой гипотезы и выяснил, что эта закономерность выполняется не только для квадратов, но и для любых натуральных степеней. Более того, благодаря этой программе возникла гипотеза: s(ab)=s(s(a)s(b)). Теперь докажем истинность этих гипотез.

Лемма. Пусть p – основание системы исчисления, n – некоторое натуральное число. Тогда окончательная сумма цифр s(n) есть остаток от деления n на (p-1) (В десятичной системе исчисления – остаток от деления на 9 (Оговоримся сразу для удобства, что если n делится нацело на (p-1), то будем считать «остатком» число (p-1) вместо нуля.)).

Доказательство. Пусть n=abc...d (a, b, c, ... d - цифры). Разность этого числа и его суммы цифр делится на (p-1). Значит, чтобы получить суму цифр a+b+c+...+d, надо из числа n несколько раз вычесть . Чтобы вычислить сумму цифр второй раз, надо ещё несколько раз вычесть , и т. д. до тех пор, пока не останется однозначное число. Естественно, это остаток от деления n на , или само число  в случае, если n делится на  нацело. Лемма доказана.

Определение. Будем говорить, что а сравнимо с b по модулю d, если .

Пример. 51 сравнимо с 2 по модулю 7 так как 51-2 делится на 7.

Отношение сравнимости является отношением эквивалентности,

Теорема. s(ab)=s(s(a)s(b)), s(a+b)=s(s(a)+s(b)).

Доказательство. Согласно лемме существуют такие целые n и m, такие, что a=(p-1)n+s(a), b=(p-1)m+s(b). Умножая эти равенства, получаем: ab=(p-1)k+s(a)s(b), где k – некоторое целое число. Значит, ab сравнимо с s(a)s(b) по модулю p-1. Иными словами, у чисел ab и s(a)s(b) одинаковые остатки от деления на , то есть их окончательные суммы цифр равны.

Аналогично, складывая равенства a=(p-1)n+s(a) и b=(p-1)m+s(b), получаем a+b=(p-1)(n+m)+s(a)+s(b).

Значит, a+b сравнимо с s(a)+s(b) по модулю (p-1). Иными словами, у чисел a+b и s(a)+s(b) одинаковые остатки от деления на , то есть их окончательные суммы цифр равны: s(a+b)=s(s(a)+s(b)). Теорема доказана.

Следствие 1. Пусть a, b – натуральные числа, пусть их окончательные суммы цифр равны: s(a)=s(b).

Тогда для любого натурального n:

1.     s(aⁿ)=s(bⁿ).

2.     s(na)=s(nb).

3.     s(a+n)=s(b+n).

Доказательство. По доказанной выше теореме, s(aⁿ)=s(s(a)ⁿ), по условию s(a)=s(b), значит, s(aⁿ)=s(s(a)ⁿ)=s(s(b)ⁿ)=s(bⁿ). Аналогично доказываются 2 и 3 равенства,.

Следствие 2. Пусть f(x) – многочлен с целыми коэффициентами, принимающий положительные значения при натуральных аргументах. Если s(a)=s(b), то s(f(a))=s(f(b)).

Эти результаты можно использовать для поиска ошибок в громоздких вычислениях или для опровержения некоторых равенств.

Пример. Верно ли равенство 7848319406×2847563 =22348582952707578 (намеренно допущена ошибка, вместо выделенной двойки должна быть тройка). Проверяем: окончательную сумму цифр первого числа считаем так: складываем цифры и по мере накопления суммы отнимаем девятки. Получаем 5. Окончательная сумма цифр второго числа равна 8. Значит, по теореме, у произведения окончательная сумма цифр должна быть равна s(5×8)=4. А у нас окончательная сумма цифр результата равна 3, что не возможно. Вывод: данное равенство не верно.

Пример (в восьмеричной системе исчисления). Верно ли равенство 6274₈×341₈=2630374₈? Нет, так как в восьмеричной системе исчисления окончательная сумма первого множителя равна 5, второго множителя равна 1. Значит, по теореме, окончательная сумма цифр произведения должна быть равна 5, но окончательная сумма цифр правой части равенства равна 4, что невозможно. 

Итак, если окончательная сумма цифр не сходится с данными теоремы, то вычисления не верные. Если же суммы цифр сходятся, то это ещё не доказывает правильность вычислений.

Пример (олимпиадного характера). Может ли число 1981198119811981...1981 (группа цифр 1981 повторяется 1400 раз) быть квадратом натурального числа? Нет. Согласно теореме, окончательная сумма цифр квадрата может быть равна только 1, 4, 7, 9. У нашего же числа окончательная сумма цифр равна пяти, как нетрудно убедиться. Впрочем, сразу видно, что данное число не может быть и кубом натурального числа.

Пример. На очной соросовской олимпиаде по математике ученикам 11 класса была предложена задача. «Найти все натуральные числа, меньшие чем 10⁵, которые делятся на 1999 и у которых сумма цифр в десятичной записи равна 25». Дети решали эту задачу, перебирая натуральные числа от 1 до 50, умножали их на 1999 и проверяли сумму цифр результата на предмет равенства 25. Без калькулятора не обошлось. Но эту задачу можно очень красиво решить с помощью обсуждаемой теоремы. Ведь если сумма цифр произведения равна 25, то окончательная сумма цифр произведения равна 7. Окончательная сумма цифр числа 1999 равна 1. Поэтому искомый множитель находится среди чисел, чья окончательная сумма цифр равна 7. Это числа: 7, 16, 25, 34, 43. Число 52 нас уже не устраивает. Умножая эти числа на 1999, имеем:

7×1999=13997, сумма цифр равна 25.

16×1999=31984, сумма цифр равна 25.

25×1999=49975, сумма цифр равна 34.

34×1999=67966, сумма цифр равна 34.

43×1999=85957, сумма цифр равна 34.

Доказанная здесь теорема позволяет утверждать, что других решений нет. Заметим, что с помощью этой теоремы перебор сократился ровно в 10 раз.

Ответ. Искомые числа 13993, 31984.

Последний пример показывает, что теорема о суммах цифр позволяет создавать аналогичные нестандартные задачи олимпиадного характера.