сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Имеем n фишек с но­ме­ра­ми 1, 2, ..., n рас­став­ле­ны в ряд по воз­рас­та­нию. За один ход раз­ре­ша­ет­ся по­ме­нять ме­ста­ми любые две фишки, между ко­то­ры­ми либо две, либо пять фишек. Су­ще­ству­ет ли такое n, для ко­то­ро­го удаст­ся за не­сколь­ко ходов рас­ста­вить все фишки в об­рат­ном по­ряд­ке?

Спрятать решение

Ре­ше­ние.

Пред­по­ло­жим, от про­тив­но­го, что для не­ко­то­ро­го n уда­лось рас­ста­вить фишки в об­рат­ном по­ряд­ке. Пред­ста­вим, что фишки рас­по­ло­же­ны на ко­ор­ди­нат­ной пря­мой в точ­ках с ко­ор­ди­на­та­ми 1, 2, ..., n. При любом ходе у двух фишек, ме­ня­ю­щих­ся ме­ста­ми, ко­ор­ди­на­ты из­ме­ня­ют­ся на 3 еди­ни­цы (у левой фишки ко­ор­ди­на­та уве­ли­чи­ва­ет­ся на 3, а у пра­вой умень­ша­ет­ся на 3). Зна­чит, при всех ходах ко­ор­ди­на­та любой фик­си­ро­ван­ной фишки со­хра­ня­ет тот же оста­ток при де­ле­нии на 3, ко­то­рый был вна­ча­ле.

Рас­смот­рим фишку с но­ме­ром n: вна­ча­ле у неё ко­ор­ди­на­та рав­ня­лась n, а в конце стала равна 1. По­это­му n – 1 де­лит­ся на 3. Ана­ло­гич­но, рас­смот­рим фишку с но­ме­ром n – 1: в конце у неё ко­ор­ди­на­та стала равна 2 и по­это­му n – 1 – 2 де­лит­ся на 3, то есть n долж­но быть крат­но 3  — про­ти­во­ре­чие.

 

Ответ: не су­ще­ству­ет.

 

Ком­мен­та­рий.

По срав­не­нию с при­ве­ден­ном ре­ше­ни­ем здесь име­ет­ся до­пол­ни­тель­ная воз­мож­ность пе­ре­став­лять ме­ста­ми две фишки, между ко­то­ры­ми пять фишек. Это поз­во­ля­ет из­ме­нять ко­ор­ди­на­ты на 6 еди­ниц, но эта до­пол­ни­тель­ная воз­мож­ность не ме­ня­ет остат­ка при де­ле­нии на 3 ко­ор­ди­на­ты фишки, по­это­му выше при­ве­ден­ное до­ка­за­тель­ство за­да­чи остаётся в силе.