Математикадан республикалық олимпиада, 2015-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$ по одному разу и что она удовлетворяет требуемому условию.
Если запишем эти числа по кругу в этом же порядке, по получим требуемое расставление.