Разделы 
Дополнительно
Задача по математике - 2916
2019-05-06 
Доказать, что
a) $\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n = \left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \left [ \frac{n}{3} \right ] + \cdots + \left [ \frac{n}{n} \right ]$,
где $\tau_n$ - число делителей натурального числа $n$;
б) $\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n = \left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \left [ \frac{n}{3} \right ] + \cdots + \left [ \frac{n}{n} \right ]$,
где $\sigma_n$ - сумма делителей натурального числа $n$.
Решение:
Первое решение. При $n = 1$ мы в левой и правой частях равенств имеем по одному члену, равному 1; следовательно, в этом случае равенства справедливы. Докажем теперь, что если наше равенство справедливо для какого-то значения $n$, то оно будет справедливо и для значения $n+1$; в силу принципа мате, $m$ этической индукции, отсюда будет следовать, что равенство справедливо при всех значениях $n$.
Отметим, что если $n + 1$ не делится на $k$:
$n+1 = qk+r$,
где остаток $r$ заключен между 1 и $k-1$, то $n = qk+r^{ \prime}$, где $r^{ \prime} = r-1$, т. е. $0 \leq r^{ \prime} \leq k-2$; отсюда следует, что в этом случае величины $\left [ \frac{n + 1}{k} \right ]$ и $\left [ \frac{n}{k} \right ]$ совпадают (обе они равны $q$). Если же $n+1$ делится $k$: $n+1 = qk$, то, очевидно $\left [ \frac{n+1}{k} \right ] = q, \left[ \frac{n}{k} \right ] = q - 1$, т. е. $\left [ \frac{n+1}{k} \right ] = \left [ \frac{n}{k} \right ] + 1$. Таким образом,
$\left [ \frac{n+1}{k} \right ] = \left [ \frac{n}{k} \right ]$, если $k$ на есть делить числа $n+1$
$\left [ \frac{n+1}{k} \right ] = \left [ \frac{n}{k} \right ] + 1$, если $k$ на есть делить числа $n+1$
А отсюда вытекает, что:
а) $\left [ \frac{n+1}{1} \right ] + \left [ \frac{n+1}{2} \right ] + \cdots + \left [ \frac{n+1}{n+1} \right ] = \left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \cdots + \left [ \frac{n}{n+1} \right ] + \tau_{n+1}$,
т. е. если
$\left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \cdots + \left [ \frac{n}{n} \right ] = \tau_1 + \tau_2 + \cdots + \tau_n$,
то
$\left [ \frac{n+1}{1} \right ] + \left [ \frac{n+1}{2} \right ] + \cdots + \left [ \frac{n+1}{n+1} \right ] = \tau_1 + \tau_2 + \cdots + \tau_n + \tau_{n+1}$;
б) $\left [ \frac{n+1}{1} \right ] + 2 \left [ \frac{n+1}{2} \right ] + \cdots + (n + 1) \left [ \frac{n+1}{n+1} \right ] = \left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + \cdots + (n+1) \left [ \frac{n}{n+1} \right ] + \sigma_{n+1}$,
т. е. если
$\left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + \cdots + n \left [ \frac{n}{n} \right ] = \sigma_1 + \sigma_2 + \cdots + \sigma_n$,
то
$\left [ \frac{n+1}{1} \right ] + 2 \left [ \frac{n+1}{2} \right ] + \cdots + (n+1) \left [ \frac{n+1}{n+1} \right ] = \sigma_1 + \sigma_2 + \cdots + \sigma_n + \sigma_{n+1}$.
Второе решение. Число чисел ряда $1,2,3, \cdots, n$ делящихся на какое-то выбранное число $k$, равно $\left [ \frac{n}{k} \right ]$ (это будут числа $k, 2k, 3k, \cdots, \left [ \frac{n}{k} \right ]k$) сумма делителей $k$ всех таких чисел равна $k \left [ \frac{n}{k} \right ]$. Отсюда следует, что:
а) Сумма $\left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \cdots \left [ \frac{n}{k} \right ] + \cdots + \left [ \frac{n}{n} \right ]$ равна числу чисел ряда $1, 2, 3, \cdots, n$, делящихся на 1, плюс число чисел этого ряда, делящихся на 2, ..., плюс число чисел этого ряда, делящихся на $n$. Но этому же равна сумма $\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n$.
б) Сумма $1 \left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + \cdots + k \left [ \frac{n}{k} \right ] + \cdots + n \left [ \frac{n}{n} \right ]$ равна сумме делителей $l$ всех чисел ряда $1, 2, 3, \cdots, n$, плюс сумма делителей 2 всех чисел этого ряда, плюс сумма делителей 3 всех чисел этого ряда, …, плюс сумма делителей $n$ всех чисел этого ряда. Но этому же равна и сумма $\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n$.
Третье решение. Приведем еще изящное геометрическое решение задачи, близкое ко второму решению. Рассмотрим равностороннюю гиперболу (график обратной пропорциональности) $y = \frac{k}{x}$, или, что то же самое, $xy = k$ (точнее, ветвь этой гиперболы, расположенную в первом координатном углу; см. рис. а.
Отметим, кроме того, в первом координатном углу все точки с целыми координатами. Тогда, если $x$ есть делитель числа $к$, то на равносторонней гиперболе $xy = k$ есть целочисленная точка с абсциссой $x$. Обратно, если гипербола $xy = k$ проходит через целочисленную точку с абсциссой $x$, то $x$ есть делитель числа $к$. Таким образом, число $\tau_k$ делителей числа $к$ равно числу целочисленных точек, лежащих на гиперболе $xy = k$; сумма делителей $\sigma_k$ этого числа равна сумме абсцисс целочисленных точек, лежащих на гиперболе $xy = k$. Далее, воспользуемся еще тем, что все гиперболы $xy = 1, $xy = 2, $xy = 3, \cdots, xy = n - 1$ расположены ниже гиперболы $xy = n$. Отсюда можно сделать следующие выводы.
а) Сумма $\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n$ равна числу всех целочисленных точек, лежащих под гиперболой $xy = n$ (и на самой гиперболе). Но, с другой стороны, ни одна из этих точек не имеет абсциссы, большей $n$; число же целочисленных точек с абсциссой $k$, расположенных под гиперболой, равно целой части длинны отрезка $MN$, изображенного на рис. а), т. е. $\left [ \frac{n}{k} \right ]$, так как $MN = \frac{n}{k}$ (сравните с решением задачи 2915). Таким образом, имеем:
$\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n = \left[ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \left [ \frac{n}{3} \right ] + \cdots + \left [ \frac{n}{n} \right ]$.
б) Припишем каждой целочисленной точке номер, равный ее абсциссе (рис. б); в таком случае сумма $\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n$ равна сумме номеров всех целочисленных точек, расположенных под гиперболой $xy = n$. С другой стороны, сумма номеров всех таких точек, имеющих абсциссу $k$, равна $k \left [ \frac{n}{k} \right ]$. Таким образом, имеем:
$\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n = \left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + 3 \left [ \frac{n}{3} \right ] + \cdots + n \left [ \frac{n}{n} \right ]$.
Доказать, что
a) $\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n = \left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \left [ \frac{n}{3} \right ] + \cdots + \left [ \frac{n}{n} \right ]$,
где $\tau_n$ - число делителей натурального числа $n$;
б) $\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n = \left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \left [ \frac{n}{3} \right ] + \cdots + \left [ \frac{n}{n} \right ]$,
где $\sigma_n$ - сумма делителей натурального числа $n$.
Решение:
Первое решение. При $n = 1$ мы в левой и правой частях равенств имеем по одному члену, равному 1; следовательно, в этом случае равенства справедливы. Докажем теперь, что если наше равенство справедливо для какого-то значения $n$, то оно будет справедливо и для значения $n+1$; в силу принципа мате, $m$ этической индукции, отсюда будет следовать, что равенство справедливо при всех значениях $n$.
Отметим, что если $n + 1$ не делится на $k$:
$n+1 = qk+r$,
где остаток $r$ заключен между 1 и $k-1$, то $n = qk+r^{ \prime}$, где $r^{ \prime} = r-1$, т. е. $0 \leq r^{ \prime} \leq k-2$; отсюда следует, что в этом случае величины $\left [ \frac{n + 1}{k} \right ]$ и $\left [ \frac{n}{k} \right ]$ совпадают (обе они равны $q$). Если же $n+1$ делится $k$: $n+1 = qk$, то, очевидно $\left [ \frac{n+1}{k} \right ] = q, \left[ \frac{n}{k} \right ] = q - 1$, т. е. $\left [ \frac{n+1}{k} \right ] = \left [ \frac{n}{k} \right ] + 1$. Таким образом,
$\left [ \frac{n+1}{k} \right ] = \left [ \frac{n}{k} \right ]$, если $k$ на есть делить числа $n+1$
$\left [ \frac{n+1}{k} \right ] = \left [ \frac{n}{k} \right ] + 1$, если $k$ на есть делить числа $n+1$
А отсюда вытекает, что:
а) $\left [ \frac{n+1}{1} \right ] + \left [ \frac{n+1}{2} \right ] + \cdots + \left [ \frac{n+1}{n+1} \right ] = \left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \cdots + \left [ \frac{n}{n+1} \right ] + \tau_{n+1}$,
т. е. если
$\left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \cdots + \left [ \frac{n}{n} \right ] = \tau_1 + \tau_2 + \cdots + \tau_n$,
то
$\left [ \frac{n+1}{1} \right ] + \left [ \frac{n+1}{2} \right ] + \cdots + \left [ \frac{n+1}{n+1} \right ] = \tau_1 + \tau_2 + \cdots + \tau_n + \tau_{n+1}$;
б) $\left [ \frac{n+1}{1} \right ] + 2 \left [ \frac{n+1}{2} \right ] + \cdots + (n + 1) \left [ \frac{n+1}{n+1} \right ] = \left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + \cdots + (n+1) \left [ \frac{n}{n+1} \right ] + \sigma_{n+1}$,
т. е. если
$\left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + \cdots + n \left [ \frac{n}{n} \right ] = \sigma_1 + \sigma_2 + \cdots + \sigma_n$,
то
$\left [ \frac{n+1}{1} \right ] + 2 \left [ \frac{n+1}{2} \right ] + \cdots + (n+1) \left [ \frac{n+1}{n+1} \right ] = \sigma_1 + \sigma_2 + \cdots + \sigma_n + \sigma_{n+1}$.
Второе решение. Число чисел ряда $1,2,3, \cdots, n$ делящихся на какое-то выбранное число $k$, равно $\left [ \frac{n}{k} \right ]$ (это будут числа $k, 2k, 3k, \cdots, \left [ \frac{n}{k} \right ]k$) сумма делителей $k$ всех таких чисел равна $k \left [ \frac{n}{k} \right ]$. Отсюда следует, что:
а) Сумма $\left [ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \cdots \left [ \frac{n}{k} \right ] + \cdots + \left [ \frac{n}{n} \right ]$ равна числу чисел ряда $1, 2, 3, \cdots, n$, делящихся на 1, плюс число чисел этого ряда, делящихся на 2, ..., плюс число чисел этого ряда, делящихся на $n$. Но этому же равна сумма $\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n$.
б) Сумма $1 \left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + \cdots + k \left [ \frac{n}{k} \right ] + \cdots + n \left [ \frac{n}{n} \right ]$ равна сумме делителей $l$ всех чисел ряда $1, 2, 3, \cdots, n$, плюс сумма делителей 2 всех чисел этого ряда, плюс сумма делителей 3 всех чисел этого ряда, …, плюс сумма делителей $n$ всех чисел этого ряда. Но этому же равна и сумма $\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n$.
Третье решение. Приведем еще изящное геометрическое решение задачи, близкое ко второму решению. Рассмотрим равностороннюю гиперболу (график обратной пропорциональности) $y = \frac{k}{x}$, или, что то же самое, $xy = k$ (точнее, ветвь этой гиперболы, расположенную в первом координатном углу; см. рис. а.
Отметим, кроме того, в первом координатном углу все точки с целыми координатами. Тогда, если $x$ есть делитель числа $к$, то на равносторонней гиперболе $xy = k$ есть целочисленная точка с абсциссой $x$. Обратно, если гипербола $xy = k$ проходит через целочисленную точку с абсциссой $x$, то $x$ есть делитель числа $к$. Таким образом, число $\tau_k$ делителей числа $к$ равно числу целочисленных точек, лежащих на гиперболе $xy = k$; сумма делителей $\sigma_k$ этого числа равна сумме абсцисс целочисленных точек, лежащих на гиперболе $xy = k$. Далее, воспользуемся еще тем, что все гиперболы $xy = 1, $xy = 2, $xy = 3, \cdots, xy = n - 1$ расположены ниже гиперболы $xy = n$. Отсюда можно сделать следующие выводы.
а) Сумма $\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n$ равна числу всех целочисленных точек, лежащих под гиперболой $xy = n$ (и на самой гиперболе). Но, с другой стороны, ни одна из этих точек не имеет абсциссы, большей $n$; число же целочисленных точек с абсциссой $k$, расположенных под гиперболой, равно целой части длинны отрезка $MN$, изображенного на рис. а), т. е. $\left [ \frac{n}{k} \right ]$, так как $MN = \frac{n}{k}$ (сравните с решением задачи 2915). Таким образом, имеем:
$\tau_1 + \tau_2 + \tau_3 + \cdots + \tau_n = \left[ \frac{n}{1} \right ] + \left [ \frac{n}{2} \right ] + \left [ \frac{n}{3} \right ] + \cdots + \left [ \frac{n}{n} \right ]$.
б) Припишем каждой целочисленной точке номер, равный ее абсциссе (рис. б); в таком случае сумма $\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n$ равна сумме номеров всех целочисленных точек, расположенных под гиперболой $xy = n$. С другой стороны, сумма номеров всех таких точек, имеющих абсциссу $k$, равна $k \left [ \frac{n}{k} \right ]$. Таким образом, имеем:
$\sigma_1 + \sigma_2 + \sigma_3 + \cdots + \sigma_n = \left [ \frac{n}{1} \right ] + 2 \left [ \frac{n}{2} \right ] + 3 \left [ \frac{n}{3} \right ] + \cdots + n \left [ \frac{n}{n} \right ]$.
