Всероссийская олимпиада школьников по математике, 10 класс, 2017 год
дата проведения: 16 октября 2017 - 22 октября 2017
Задача 3.
На доске в произвольном порядке выписаны числа от 1 до 2017. Два числа можно поменять местами, если одно из них делится на другое. Докажите, что за несколько таких операций числа можно расположить в порядке возрастания.
Ответ на Задачу 3.
Решение:
Покажем, как поставить число $k$ ≠ 1 на $k$-ое место. Пусть на $k$-ом месте стоит число $n$. Поменяем сначала $n$ с 1, затем поменяем $k$ с 1. Тогда $k$ действительно окажется на своём месте.
Последовательно ставя на свои места числа 2017, 2016, …, мы поставим все числа в порядке возрастания.
