Республиканская олимпиада по математике, 2016 год, 11 класс

Для любого натурального числа докажите, что все его натуральные делители можно расставить по кругу так, чтобы из любых двух соседних чисел одно число делилось на другое. ( Д. Елиусизов )

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

Комментарии от администратора Комментарии от администратора №1.     Докажем сначала, что можно выложить все натуральные делители числа $N$ в последовательность $d_1$, $\ldots$, $d_k$ так, чтобы для каждого $1\le i < k$ одно из чисел $d_i/d_{i+1}$ и $d_{i+1}/d_i$ было целым.
Докажем утверждение индукцией по количеству простых делителей числа. Если число имеет только один простой делитель $p_1$, то есть оно вида $p_1^{k_1}$, то можно выписать последовательность $1$, $p_1$, $\ldots$, $p_1^{k_1}$.
Предположим утверждение верно для числа, которое имеет $n \geq 1$ простых делителей. Докажем для числа, имеющего $n+1$ простых делителей следующим образом. Пусть $N = p_{n+1}^l\cdot N'$ ($p_{n+1}$ это $n+1$-ый простой делитель), где $N'$ имеет $n$ простых делителей и $d_1$, $\ldots$, $d_m$ искомая последовательность для $N'$. Тогда для всех делителей числа $N$, новую последовательность можно построить так: $$d_1,\ \ldots, \ d_m; \quad pd_m, \ \ldots, \ pd_1; \quad p^2d_1, \ \ldots,\ p^2d_m; \ \ldots.$$ Легко видеть, что эта последовательность содержит все делители $N$ по одному разу и что она удовлетворяет требуемому условию.
Если запишем эти числа по кругу в этом же порядке, по получим требуемое расставление.