Математикадан республикалық олимпиада, 2015-2016 оқу жылы, 10 сынып


Натурал $N$ санының $k$ натурал бөлгіші бар. Сол санның барлық натурал бөлгіштерін, кез келген $1\le i < k$ үшін, $d_i/d_{i+1}$ немесе $d_{i+1}/d_i$ саны жай болатындай, $d_1$, $\ldots$, $d_k$ тізбегіне тізіп шығуға болатынын дәлелдеңіздер. ( Д. Елиусизов )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Докажем утверждение индукцией по количеству простых делителей числа. Если число имеет только один простой делитель $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$ по одному разу и что она удовлетворяет требуемому условию.