Задача на сумму цифр со всероса

Автор текста: Дуйсенбеков Данат

Вроде бы, однажды, на Всероссийской олимпиаде школьникам была предложена следующая задача:

Обозначим через s(x) сумму цифр натурального числа x. Докажите, что существует бесконечно много натуральных n, таких, что s(3^n) \ge s(3^{n+1}).

Решение совсем простое. Предположим обратное. Тогда с какого то момента n_0>2 последовательность s(3^n) строго возрастает. Рассматривая по модулю 9, получаем: s(3^{n_0+k}) \ge s(3^{n_0+k-1}) + 9 \ge … \ge s(3^{n_0})+9k. Возьмем k достаточно большим. Тогда 9k < s(3^{n_0+k}) \le 9\log_{10}(3^{n_0+k}) < 9\log_{10}(10^{\frac{n_0+k}{2}}) =9\cdot\frac{n_0+k}{2}, что, очевидно, является противоречием. А что если чуточку изменить задачу, всего лишь один знак?

Обозначим через s(x) сумму цифр натурального числа x. Докажите, что существует бесконечно много натуральных n, таких, что s(3^n) < s(3^{n+1}).

По сути, нужно доказать, что сумма цифр степени тройки может быть сколь угодно большой. Давайте же докажем более сильное утверждение - степень тройки может начинаться на любую последовательность цифр (при условии, что первая цифра - не ноль). Например, есть степень тройки которая начинается на цифры 6969, или же 7082002, или же просто 55555555.

Поймем, для начала, что значит что число x “начинается” на число A. Если в десятичной записи x содержит еще n цифр после A, то тогда 10^nA ≤ x < 10^n(A+1). Ясно, что это необходимое и достаточное условие. Получается, для любого натурального A, нам необходимо найти m,n такие, что:

10^nA \leq 3^m < 10^n(A+1).

Что равносильно

n+\log_{10}(A) \le m\log_{10}(3) < n + \log_{10}(A+1).

Видим, что проблема кроется в дробных частях и что нам достаточно найти такое большое натуральное m, что \{m\log_{10}(3)\} принадлежит промежутку (\{\log_{10}(A)\}, \{\log_{10}(A+1)\}), либо же промежутку (\{\log_{10}(A)\}, 1), если между \log_{10}(A) и \log_{10}(A+1) есть целое число. Тогда мы легко подберем n, чтобы неравенство выше действительно выполнялось (n = [m\log_{10}(3)]-[\log_{10}(A)]).

Такой m найдется, потому что для любого иррационального \alpha и любого интервала (x, y), 0 \le x < y \le 1, существует натуральное k, что \{ k\alpha\} \in (x, y), т.е. потому что множество \{ \{n\alpha\} \ \mid \ n \in N \} плотно в (0,1). Доказать это - довольно легко. Из утверждения сразу же следует, что таких натуральных k бесконечно (поделим (x,y) на бесконечно много непересекающихся интервалов, например). Осталось понять, что \log_{10}(3) - иррационально. Что касается суммы цифр, мы только что доказали, что 3^n может начинаться на сколь угодно много семерок, а значит и s(3^n) не ограничен.

Заметим, что единственное свойство числа 3, используемое в данном решении - это иррациональность \log_{10}(3). Поэтому, можем заменить 3 на любое натуральное a, такое, что \log_{10}(a) - иррационально, т.е. на любое число, кроме степеней 10. Конечно, можно и по другому подойти к изначальной проблеме. Например, в этой статье показывается, что s(2^n) > \log_4(n).

Вот еще несколько задач про цифры и суммы цифр:

  • Докажите, что существует бесконечно много пар точных квадратов a^2 и b^2 не кратных 10 с одинаковыми наборами(мультимножествами) цифр.
  • Докажите, что для любого n не делящегося на 10, существует число кратное n и состоящее только из цифр 1, 2, 3, 4, 5.
  • Верно ли, что для любого натурального n>2 выполняется s(9^n)>9?
3 симпатии
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)