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

Ключевая идея: число \( 1 \) делит любое число. Значит, число \( 1 \) можно поменять местами с любым другим числом.

Покажем, что с помощью таких операций можно поменять местами любые два числа \( a \) и \( b \), не испортив положение \( 1 \). Пусть \( 1 \) стоит где-то отдельно. Тогда делаем три обмена:

• меняем \( 1 \) и \( a \);
• меняем \( 1 \) и \( b \);
• снова меняем \( 1 \) и \( a \).

Все эти обмены разрешены, потому что \( 1 \) делит любое число. В результате числа \( a \) и \( b \) поменялись местами, а \( 1 \) вернулась на своё место.

Но любая перестановка чисел может быть приведена к порядку возрастания с помощью последовательности обычных попарных обменов. Каждый такой обмен мы умеем заменить на несколько разрешённых операций. Значит, числа от \( 1 \) до \( 2017 \) можно расположить по возрастанию.

0 0 Пожаловаться