Processing math: 65%

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


Натурал n саны үшін, d(n) арқылы осы санның натурал бөлгіштер саны белгілейік, ал e(n)=[2000n] болсын (2000-ді n-ге бөлгендегі бүтін бөлігі). Олай болса, d(1)+d(2)++d(2000)=e(1)+e(2)++e(2000) теңдігі орындалатынын дәлелдеңіздер.
посмотреть в олимпиаде

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

  2
3 года 1 месяца назад #

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

f(k,n)=kn,f(2000,n)=e(n)

Докажем индукцией по k, что ki=1d(i)=ki=1f(k,i),kN

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

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

ki=1d(i)=ki=1f(k,i)

(!!!)k+1i=1d(i)=k+1i=1f(k+1,i), вычтем из этого первое получим:

(!!!)d(k+1)=f(k+1,k+1)+ki=1(f(k+1,i)f(k,i))

С другой стороны f(k+1,i)f(k,i)={0,ik+11,i, то есть правая скобка это количество случаев когда разность 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) Ч.Т.Д.