11-я Международная Жаутыковская олимпиада, 2015 год

Найдите наибольшее натуральное $n$ такое, что для любого натурального $k \le \dfrac{n}{2}$ найдутся два натуральных делителя $n$ с разностью $k$. ( А. Голованов )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: 24.
Решение. Это число, очевидно, удовлетворяет условию: $1=2-1$, $2=4-2$, $3=6-3$, $4=8-4$, $5=8-3$, $6=8-2$, $7=8-1$, $8=12-4$, $9=12-3$, $10=12-2$, $11-12-1$, $12=24-12$.
Предположим, что $n>24$ удовлетворяет условию. Если $n$ нечётно, у него нет делителей между $n$ и $\dfrac{n}{3}$, поэтому $\dfrac{n-1}{2}$ должно иметь вид $n-d$, где $d$ — делитель $n$. Но тогда $d=\dfrac{n+1}{2}$, очевидно, не делит $n$. Таким образом, $n$ чётно.
Если $\dfrac{n}{3} \leq k < \dfrac{n}{2}$ и $k=d_1-d_2$, где $d_1$ and $d_2$ — делители $n$, то $d_1=\dfrac{n}{2}$ (поскольку, очевидно, $d_1>\dfrac{n}{3}$, а при $d_1=n$ число $d_2$ должно быть больше $n\over 2$). Поэтому для каждого такого $k$ число $\dfrac{n}{2}-k$ — делитель $n$. Это означает, что $n$ делится на все натуральные числа, не превосходящие $n\over 6$. Поскольку $n>24$, оно делится на 3, 4 и, следовательно, на 12.
Числа $\dfrac{n}{6}$ и $\dfrac{n}{6}-1$ взаимно просты и делят $n$. Поэтому $n$ делится на их произведение, значит, $n\geq \dfrac{n}{6}\left(\dfrac{n}{6}-1\right)$, то есть $n\leq 42$. Так как $12|n$, остаётся проверить число 36, которое не делится на $5<\dfrac{36}{6}$ и потому не удовлетворяет условию.