Задача из журнала «Квант» (1976, №6)

Условие

Докажите что существует бесконечно много натуральных ${n}$, для которых сумма цифр числа ${2}^{n}$ больше суммы цифр числа ${2}^{n+1}.$

Решение

Рис.1

Решение этой задачи основано на двух фактах.

I  Остатки чисел  $1,\quad 2,\quad { 2 }^{ 2 },\quad { 2 }^{ 3 }…$ при делении на 9 образуют периодическую последовательность, изображенную на рисунке 1.

II Количество цифр в числе   ${2}^{n}$ не превосходит

$$\lg{{ 2 }^{ n }}+1=n\cdot \lg{2}+1\le \frac { n }{ 3 } +1.$$

Покажем, что эти два факта находятся в противоречии с предположением:

III      

$$s({ 2 }^{ n })\le s({ 2 }^{ n+1 })$$

для всех  ${n}$, не меньших некоторого ${N}$, где ${s(a)}$ — сумма цифр числа ${a}.$

Отсюда будет следовать, что III неверно, а это и требуется доказать в задаче.

Допустим, что III верно, то есть что для всех ${n\ge N}$ сумма цифр ${2}^{n}$ все время возрастает. Тогда согласно I для ${n\ge N}$ при переходе от ${2}^{n}$ до ${2}^{n+6}$ (за один период) сумма цифр увеличивается не меньше, чем на

$${1+2+4+8+7+5=27}.$$

(Мы рассуждаем так: если ${a}$ дает при делении на ${9}$ остаток ${8}$, ${b}$ — остаток ${7}$ и ${a<b}$, то разность ${b-a}$ не меньше ${8}$; оценки для разностей указаны на рисунке 1 красным цветом). Итак,

$$s({ 2 }^{ n+6 })\le s({ 2 }^{ n })+27.$$

Значит, при ${n=N+6k}$, где  ${k\ge 1}$, будет

$$s({ 2 }^{ n })=s({ 2 }^{ N+6k })\ge { s(2 }^{ N })+27k=\cfrac { 9 }{ 2 } n-\cfrac { 9 }{ 2 } N+s({ 2 }^{ N }).$$

Поскольку все цифры не больше 9, согласно II

$$s({ 2 }^{ n })\le 9(\frac { n }{ 3 } +1).$$

Таким образом, при всех ${n=N+6k}$ должно выполняться неравенство

$$\frac { 9 }{ 2 } n-A\le s({ 2 }^{ n })\le 3n+9.$$

(здесь $A$ — число, не зависящее от $n$). Но поскольку $\frac { 9 }{ 2 } >3$, это, очевидно, неверно(при всех $n>2(A+9)/3$). Полученное противоречие доказывает, что предположение III неверно.