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

Число 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 операций.