Республиканская олимпиада по математике, 2011 год, 9 класс

Выпишем в порядке возрастания число 1 и все натуральные числа, сумма цифр которых делится на 5. Получим последовательность $1$, $5$, $14$, $19$, $\ldots$. Докажите, что $n$-ый член последовательности меньше чем $5n$.

Комментарий/решение

Разобьём последовательность как $(a_{3},a_{4})=(14,19), \ (a_{5},a_{6})=(23,28), \ (a_{7},a_{8})=(32,37) , ... (a_{n-1}, a_{n} ) = (x,y) $

1)

Докажем что между последовательными десятичными разрядами то есть $20,30,40...$ найдутся два числа сумма цифр которых кратно $5.$

Так как разность последовательных чисел которые делятся на $5$ равна $5$ отсюда максимальная цифра на которую может оканчивается $x$ равна $4$ значит для второго максимальное $4+5=9$ что подходит так как $9<10$, откуда $y=x+5$

2) Тогда учитывая пункт $1$ следует $x \leq \dfrac{n-2}{2} \cdot 10 + 4 = 5n-6 < 5n $

и

$y \leq \dfrac{n-2}{2} \cdot 10 + 9 = 5n-1 < 5n $

Пусть $s(x)$ - сумма цифр $x$.

Заменим это множество на $A = \{0,5,14,\dots\}$.

Лемма: на интервале $[5m,5m+4]$ существует ровно одно целое число, сумма цифр которого кратна $5$.

Д-во: Число $5m$ оканчивается на $0$ или $5$.

Если $5m = 10n$, то среди $k,\dots,k+4$ ровно одно кратно $5$ ($s(10n)=s(n)=k$).

Если $5m = 10n+5$, то среди $k+5,\dots,k+9$ тоже ровно одно кратно $5$ ($s(10n)=s(n)=k$).$\blacksquare$

Обозначим это единственное число через $c_n$, причём $c_n \in [5n;5n+4]$, причём для разных $n$ эти отрезки не пересекаются, потому множество $\{0,5,14,\dots\}$ --- это в точности числа $c_0, c_1, \dots$ и $a_{m+1}=c_m$, откуда $a_{m+1} \le 5m+4 < 5(m+1)$. $\blacksquare$