Обозначим через $%S(n)$% сумму цифр десятичной записи натурального числа $%n$%.

Доказать, что $$\lim_{n\to\infty}S(2^n)=+\infty$$

задан 7 Янв '15 22:15

изменен 6 Фев '15 23:55

10|600 символов нужно символов осталось
2

Идея оказалась проще, чем я думал поначалу.

Последняя цифра степени двойки отлична от нуля и не делится на $%2^4$%. Отсюда следует, что у достаточно большой степени двойки перед последней цифрой не могут идти три нуля. Значит, среди последних 4 цифр есть как минимум две ненулевые.

Поскольку 4-значное десятичное число не делится на $%2^{14}$%, у достаточно больших степеней двойки не может оказаться 10 нулей перед двумя последними четырьмя цифрами, то есть среди последних 14 цифр есть как минимум три ненулевых, и так далее.

Несколько огрубляя оценку, обобщаем: если десятичная запись степени двойки оканчивается $%4^m$% цифрами, то среди них имеется как минимум $%m+1$% ненулевая. Доказываем по индукции: десятичное $%4^m$%-значное число меньше $%10^{4^m} < 16^{4^m}=2^{4^{m+1}}$%, то есть оно не делится на степень двойки с указанным показателем. Следовательно, если мы у достаточно большой степени двойки берём последние $%4^{m+1}$% десятичных цифр, то среди них найдётся ещё хотя бы одна ненулевая цифра помимо тех, которые входят в последние $%4^m$%, и тогда всего получится не менее $%m+2$% ненулевых цифр.

Таким образом, если $%n\ge4^m$%, то $%2^n=16^{4^{m-1}} > 10^{4^{m-1}}$% обладает $%m$% ненулевыми цифрами среди последних $%4^{m-1}$% цифр, и тогда $%S(2^n)\ge m$%.

Получается логарифмическая относительно $%n$% оценка снизу. Интересно, можно ли её улучшить?

Интересно, что среднее арифметическое значение десятичных цифр числа $%2^n$% ведёт себя достаточно причудливо. Скажем, при $%n=1200$% получается около 4,786, а при $%n=1500$% оно будет близко к 4,5. При $%n=3000$% происходит падение до 4,28. Совершенно непонятно, стремится ли это число к какому-либо пределу.

ссылка

отвечен 7 Фев '15 22:55

@falcao: Идея Вашего решения совпадает с авторской идеей. Лет 40 назад я придумал иное решение, основанное на принципе Дирихле. Если вспомню его, то выложу.

(7 Фев '15 23:55) EdwardTurJ

@EdwardTurJ: а кто автор этой задачи?

Другие способы решения тоже интересно было бы узнать -- включая порядок получаемой оценки.

(8 Фев '15 0:06) falcao

@falcao: Польские математические олимпиады, задача № 138 http://math.ru/lib/94

(8 Фев '15 0:46) EdwardTurJ

@EdwardTurJ: у меня эта книга есть (правда, не при себе), но я оттуда решал далеко не всё, поэтому не помню этой задачи. Решение я посмотрел -- идея в точности такая же.

(8 Фев '15 0:54) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×37

задан
7 Янв '15 22:15

показан
3056 раз

обновлен
8 Фев '15 0:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru