Математикадан «Туймаада» олимпиадасы. Жоғары лига. 2000 жыл

Натурал $n$ саны үшін, $d(n)$ арқылы осы санның натурал бөлгіштер саны белгілейік, ал $e(n)=\left[ \dfrac{2000}{n} \right]$ болсын (2000-ді $n$-ге бөлгендегі бүтін бөлігі). Олай болса, $d(1)+d(2)+\ldots+d(2000)=e(1)+e(2)+\ldots+e(2000)$ теңдігі орындалатынын дәлелдеңіздер.

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

Введем функцию

$$f(k, n) = \left \lfloor \frac{k}{n} \right \rfloor, f(2000, n) = e(n)$$

Докажем индукцией по $k$, что $\displaystyle{\sum_{i = 1}^k d(i)= \sum_{i = 1}^k f(k, i)}, \forall k \in \mathbb{N}$

База $: k = 1: d(1) = f(1, 1) - $ верно

Переход $:$, допустим что для $l = k - $ верно, докажем для $l = k+1$

$\displaystyle{\sum_{i = 1}^k d(i)= \sum_{i = 1}^k f(k, i)}$

$(!!!)\displaystyle{\sum_{i = 1}^{k+1} d(i)= \sum_{i = 1}^{k+1} f(k+1, i)}$, вычтем из этого первое получим:

$(!!!) d(k+1) = \displaystyle{f(k+1, k+1) + \sum_{i=1}^k (f(k+1, i) - f(k, i))}$

С другой стороны $f(k+1, i) - f(k, i) = \begin{cases} 0, i \mid k+1 \\ 1, i \nmid k + 1\end{cases} \implies \displaystyle{f(k+1, k+1) + \sum_{i=1}^k (f(k+1, i) - f(k, i))} = 1 + (d(k+1) - 1)$, то есть правая скобка это количество случаев когда разность $f(k+1, i) - f(k, i) = 1$ при этом $i < k+1$, то есть все делители $k+1$, кроме самого $k+1$, следовательно

$$\displaystyle{f(k+1, k+1) + \sum_{i=1}^k (f(k+1, i) - f(k, i))} = 1 + (d(k+1) - 1) = d(k+1)$$, из чего и следует переход индукции

Но тогда при $k = 2000$, это верно, а следовательно $\displaystyle{\sum_{i=1}^{2000} d(i) = \sum_{i=1}^{2000} f(2000, i)} = \sum_{i=1}^{2000} e(i)$ Ч.Т.Д.