Запишем подряд все натуральные числа, кратные девяти: 9,18,27,36,45,54,63,72,81, 99, 108... У каждого из этих чисел посчитали сумму цифр. В результате получим последовательность: 9,9,9,9,9,9,9,9,9,9,18,9,... Найдите сумму первых 550 членов этой последовательности.

задан 1 Фев '16 14:38

изменен 1 Фев '16 14:38

Это надо сделать вручную или на компьютере? По идее, там получится сумма чисел, равных 9, 18 или 27. И надо понять, сколько раз каждое встречается. Это не слишком сложно, и достаточно найти количество для 9 и для 27. В первом случае есть почти что готовая формула для количества чисел с суммой 9. Для 27 -- чуть посложнее, но там тоже можно организовать перебор. Но вообще-то это больше смахивает на задачу не для человека, а для компьютера.

(1 Фев '16 17:09) falcao

задача для человека)

(1 Фев '16 21:58) nevajno
10|600 символов нужно символов осталось
3

Хорошо, давайте сосчитаем вручную.

Как уже было сказано выше, нам достаточно узнать, у скольких чисел сумма цифр равна 9, и у скольких она равна 27. Сначала решим первую задачу.

Рассмотрим уравнение $%x+y+z=n$%. Количество его решений в целых неотрицательных числах равно $%f(n)=\frac{(n+2)(n+1)}2$%. Это достаточно простой факт: можно воспользоваться тем, что это число сочетаний с повторениями из 3 по $%n$%, а оно равно $%C_{3+n-1}^n=C_{n+2}^n=C_{n+2}^2$%. Можно также вывести эту формулу, полагая $%z$% равным 0, 1, ... , $%n$%, и суммируя далее члены арифметической прогрессии.

Заметим, что при $%n\le9$% данная формула даёт количество трёхразрядных чисел вида $%\overline{xyz}$% с суммой цифр $%n$%.

Наши числа, кратные 9, находятся в пределах от 9 до 4950. Поэтому их можно рассматривать как 4-разрядные. Если первая цифра равна нулю, то мы получаем $%f(9)=55$% чисел. Если первая цифра равна 1, то будет $%f(8)=45$% чисел. И так далее -- до цифры 4, когда сумма оставшихся равна 5. При этом числа, большие 4950, можно также включить, потому что у них суммы цифр пяти не равны. В итоге мы получим $%f(9)+f(8)+f(7)+f(6)+f(5)=55+45+36+28+21=185$% чисел списка с суммой цифр 9.

Теперь сделаем то же для суммы цифр, равной 27. Как и выше, нас будет интересовать количество 3-разрядных чисел с суммой n, равной 27, 26, 25, 24, 23 соответственно. То есть это число решений уравнения вида $%x+y+z=n$% в десятичных цифрах. Предыдущая формула тут уже непригодна. Но можно заметить, что здесь $%(9-x)+(9-y)+(9-z)=27-n$%, и слагаемые остаются цифрами. При этом в правой части сумма не превосходит 9, и тогда формула $%f(27-n)$% даёт нам ответ. Мы получим при этом $%f(0)+f(1)+f(2)+f(3)+f(4)=1+3+6+10+15=35$%. Однако это количество учитывает несколько лишних чисел с суммой 27, которые превышают 4950. Сумма двух последних цифр у них равна 14, и сюда попадают числа, оканчивающиеся на 59, 68, 77, 86, 95. Их пять, то есть в нашем списке имеется ровно $%30$% чисел с суммой цифр $%27$%. Поэтому сумма цифр, равная $%18$%, наблюдается у оставшихся $%550-185-30=335$% чисел.

Осталось найти общее значение суммы: $%9\cdot185+18\cdot335+27\cdot30=8505$%. То же самое можно было найти проще: если бы для всех чисел сумма цифра была равна 18, то мы получили бы $%18\cdot550=9900$%. Однако мы теряем 9 на каждом из 185 чисел, и приобретаем 9 на каждом из 30, поэтому общие "потери" составляют $%9\cdot155=1395$%. Разность даёт то, что мы получили выше.

ссылка

отвечен 1 Фев '16 22:35

1

Спасибо, это задача с олимпиады на базе ведомственных учреждений (вчера проходила), как и вот эти вопросы, задачи оттуда же math.hashcode.ru/questions/88391/ и math.hashcode.ru/questions/88354/ , завтра попробую написать программу и посчитать на компьютере, ещё раз спасибо)

(1 Фев '16 23:49) nevajno

@nevajno: я проверял полученный ответ при помощи Maple. Программа там совсем коротенькая. Вообще, мне поначалу показалось, что здесь долго считать, но на самом деле это не так. Скорее всего, решение можно сделать более коротким, так как я подозреваю, что суммы треугольных чисел в одном и другом случае не случайно дополняют друг друга, и если так, что сумма 1+3+6+...+55 считается по формуле очень быстро. Она равна 10x11x12/6=220, и тогда учесть надо только "хвостик" после 4950.

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

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

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

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

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

отмечен:

×299
×97
×84

задан
1 Фев '16 14:38

показан
1989 раз

обновлен
2 Фев '16 0:06

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

по почте:

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

по RSS:

Ответы

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

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