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$.

a)Используем, что $d_i \times d_{k+1-i}$ = $n$.

$d_1d_2 + \dots + d_{k-1}d_k < n^2 \iff d_1 \times d_k \times d_2/d_k + d_2 \times d_{k-1} \times d_3/d_{k-1} + \dots + d_{k-1} \times d_2 \times d_k/d_2 < n^2 \;|\div n \iff d_2/d_k + \dots + d_k/d_2 < n \iff n/d_{k-1}d_k + \dots + n/d_2d_1 < n \;|\div n \iff S = 1/d_1d_2 + \dots + 1/d_{k-1}d_k < 1$, что верно, поскольку $1/d_i \times d_{i+1} \le (d_{i+1}-d_i)/d_i \times d_{i+1} = 1/d_i - 1/d_{i+1}$, откуда $S \le 1 - 1/d_k < 1$, ч.т.д.

b)Как мы показали ранее данное выражение равно $n^2/d_1d_2 + \dots + n^2/d_{k-1}d_k \mid n^2$, что равносильно $1/d_1d_2 + \dots + 1/d_{k-1}d_k$ натурален. Если бы $k \ge 3$, то оно было,бы меньше $1$ - противоречие. Потому $n$ - простой.