43-я Международная Математическая OлимпиадаВеликобритания, Глазго, 2002 год

Дано натуральное число $n$, большее 1. Обозначим через ${{d}_{1}},{{d}_{2}},\ldots ,{{d}_{k}}$ все его делители так, что $1={{d}_{1}} < {{d}_{2}} < \ldots < {{d}_{k}}=n$. Пусть $D={{d}_{1}}{{d}_{2}}+{{d}_{2}}{{d}_{3}}+\ldots +{{d}_{k-1}}{{d}_{k}}$.
а) Докажите, что $D < {{n}^{2}}$.
б) Найдите все $n$, для которых число $D$ — делитель числа ${{n}^{2}}$.

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

$a)$

$d_1d_2= \dfrac{n^2}{d_kd_{k-1}}$ и т.д. со всеми $\Rightarrow$

$ \dfrac{n^2}{d_{k}d_{k-1}}+$$ \dfrac{n^2}{d_{k-1}d_{k-2}}$$+$.....$+ \dfrac{n^2}{d_{1}d_{2}}<n^2$$\Rightarrow$

$ \dfrac{n^2(d_{k-2}d_{k-3}...d_{1})}{d_{k}d_{k-1}...d_{1}}$$+$$ \dfrac{n^2(d_{k}d_{k-3}...d_{1})}{d_{k}d_{k-1}...d_{1}}$$+$.....$+$$ \dfrac{n^2(d_kd_{k-1}d_{k-2}d_{k-3}...d_{3})}{d_{k}d_{k-1}...d_{1}} <n^2$$\Rightarrow$

$n^2(d_{k-2}d_{k-3}...d_{1}+d_{k}d_{k-3}...d_{1}+...+d_kd_{k-1}d_{k-2}d_{k-3}...d_{3})<n^2(d_{k}d_{k-1}...d_{1})$$\Rightarrow$

$d_{k-2}d_{k-3}...d_{1}+d_{k}d_{k-3}...d_{1}+...+d_kd_{k-1}d_{k-2}d_{k-3}...d_{3}<d_{k}d_{k-1}...d_{1}$ясно что правое больше по индукции

$b)$$n^2/\dfrac{n^2(d_{k-2}d_{k-3}...d_{1}+d_{k}d_{k-3}...d_{1}+...+d_kd_{k-1}d_{k-2}d_{k-3}...d_{3})}{n^2(d_{k}d_{k-1}...d_{1})}$$\Rightarrow$

$\dfrac{n^4(d_{k}d_{k-1}...d_{1})}{n^2(d_{k-2}d_{k-3}...d_{1}+d_{k}d_{k-3}...d_{1}+...+d_kd_{k-1}d_{k-2}d_{k-3}...d_{3})}$$\Rightarrow$

$\dfrac{n^2(d_{k}d_{k-1}...d_{1})}{(d_{k-2}d_{k-3}...d_{1}+d_{k}d_{k-3}...d_{1}+...+d_kd_{k-1}d_{k-2}d_{k-3}...d_{3})}$$\Rightarrow$

Пусть $n\ne x^{2k} \Rightarrow$$d_kd_1=n=d_{k-1}d_{2}=....$$\Rightarrow$

$\dfrac{n^2n^{k/2}}{(k-1)n^{(k-2)/2}(d_1d_2+...+d_kd_{k-1})}$$\Rightarrow$

$\dfrac{n^3}{(k-1)(d_1d_2+...+d_kd_{k-1})}$ Заметим$d_1d_2+...+d_kd_{k-1}$ нечетное тогда если $k=2$ то заметим что $n$ простое

Заметим что $d_1d_2+...+d_kd_{k-1}$ не может быть делителем числа $n$

т.к. это сумма делителей четного числа Заметим что откуда ответ $n\in P$

B)

p - ең кішкентай n санының жай бөлгіші болсын. к > 1 болсын ( n жай сан болмасын). Онда D > n²/p . n²/k = D. Осы жақта к > p бола алмайды және к ≠ 1 бола алмайды. Онда к < р және к n ды бөледі. Значит n санында p данда кіші жай бөлгіш табылып қалды противоречие. Значит n кез келген жай сан болады, құрама сан бола алмайды.

а) Запишем $d_j=\dfrac{n}{d’_j}$ для каждого $1 \leq j \geq n$. Тогда:

$D=n^2(\dfrac{1}{d’_1d’_2}+…+\dfrac{1}{d’_{k-1}d’_k}) \leq n^2(\dfrac{1}{1 \cdot 2}+…+\dfrac{1}{k-1 \cdot k}) \Rightarrow (!) S=\dfrac{1}{1 \cdot 2}+…+\dfrac{1}{k-1 \cdot k} < 1$

Заметим что $\dfrac{1}{k}=\int_{0}^{1 }{x^{k-1}}$ отсюда тк $\dfrac{1}{m(m+1)}=\dfrac{1}{m}-\dfrac{1}{m+1}=\int_{0}^{1}{(x^{m-1}-x^m)} \Rightarrow S=\int_{0}^{1}{(1-x^{k-1})}=1-\dfrac{1}{k}<1$.