Сколько целых чисел имеют сумму цифр, делящуюся на 19?

[Гость]

Не пиша компьютерной программы и не пользуясь катькулятором, определите, сколько целых чисел от 1 до 2026 (оба включительно) имеют сумму цифр, делящуюся на 19?

[admin]

Ответ: 100 чисел.

Сначала оценим, какие суммы цифр вообще возможны. Среди чисел от 1 до 2026 наибольшая сумма цифр у числа 1999: 1+9+9+9 = 28. Значит, из кратных 19 достижимо только само 19, а 38 уже недостижимо. Итак, задача сводится к подсчёту чисел с суммой цифр ровно 19.

Разобьём диапазон на три части.

1) От 1 до 999. Запишем число трёхзначной строкой abc с ведущими нулями, где 0 <= a,b,c <= 9 и a+b+c = 19. Сделаем замену x = 9-a, y = 9-b, z = 9-c, то есть дополним каждую цифру до 9. Тогда x+y+z = 27-19 = 8, причём ограничения x,y,z <= 9 выполняются автоматически, ведь сумма всего 8. Число неотрицательных целых решений уравнения x+y+z = 8 равно C(8+2,2) = C(10,2) = 45.

2) От 1000 до 1999. Первая цифра равна 1, значит для трёх остальных нужно b+c+d = 18. Та же замена даёт x+y+z = 27-18 = 9, откуда C(11,2) = 55 решений.

3) От 2000 до 2026. Сумма цифр равна 2 + 0 + (цифра десятков) + (цифра единиц), причём цифра десятков не больше 2. Максимум достигается на числе 2019: 2+0+1+9 = 12. До 19 не дотягивает, поэтому таких чисел здесь нет.

Итого: 45 + 55 + 0 = 100.

Про сам приём с заменой x = 9-a. Прямой подсчёт решений a+b+c = 19 потребовал бы включений-исключений: всего неотрицательных решений C(21,2) = 210, из них надо выбросить 3*C(11,2) = 165 случаев, где какая-то цифра больше 9 (две сразу такими быть не могут, так как 20 > 19), и получается те же 210-165 = 45. Замена на дополнение до 9 превращает большую сумму в маленькую, и ограничение сверху становится ненужным: считать быстрее и меньше шансов ошибиться.