Олимпиада Туймаада по математике. Старшая лига. 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)$ Ч.Т.Д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.