Question

На доске в произвольном порядке выписаны числа от 1 до 2017. Два числа можно поменять местами, если одно из них делится на другое. Докажите, что за несколько таких операций числа можно расположить в порядке возрастания.

Answer 1

Число 1 можно поменять с любым другим (все числа от 2 до 2017 делятся на 1). Будем поступать следующим образом:

1) Если число 1 не стоит на месте i (i не равно 1), то меняем местами число 1 и число, стоящее на месте i.
2) Меняем местами число i и число 1.

Повторяем эти действия для всех i от 2 до 2017.

Покажем, что таким образом числа окажутся в порядке возрастания.
На месте t>1 после t-1 повторения оказывается число t. После этого мы это число не трогаем (далее мы меняем 1 только с числами, большими t).
Значит после 2016-го применения данного алгоритма на позициях 2..2017 окажутся числа 2..2017 в порядке возрастания. Значит для числа 1 осталось только позиция 1. Отсюда все числа расположены в порядке возрастания.
Всего произведено 2*2016=4032 операций.