Задать вопрос
29 апреля, 15:25

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

+2
Ответы (1)
  1. 29 апреля, 18:14
    0
    Число 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 операций.
Знаете ответ на вопрос?
Не уверены в ответе?
Правильный ответ на вопрос 👍 «На доске в произвольном порядке выписаны числа от 1 до 2017. Два числа можно поменять местами, если одно из них делится на другое. ...» по предмету 📗 Математика. Развернутая система поиска нашего сайта обязательно приведёт вас к нужной информации. Как вариант - оцените ответы на похожие вопросы. Но если вдруг и это не помогло - задавайте свой вопрос знающим оппонентам, которые быстро дадут на него ответ!
Искать готовые ответы