А.В.Шаповалов => Задачи=> Просто переправы

Перестановки

В задачах на перестановки надо из одной позиции получить другую, следуя заданным правилам. Или доказать, что позицию получить нельзя. Наиболее известна "Игра 15". Частным случаем перестановок являются переправы. Но в отличие от переправ часто нужно доказать оценку на число ходов или невозможность перестановки, поэтому такого рода задачи чаще встречаются в соревнованиях старших школьников.
Здесь будут публиковаться только мои задачи - их немало.

Как ни садитесь
KC1. 4 персонажа басни Крылова и коза с баяном затеяли сыграть квинтет. Все пятеро уселись в кружок, однако музыка не пошла. Тогда они стали пересаживаться. За одну пересадку меняются местами двое соседей. Герои не успокоятся, пока каждый не посидит на месте каждого. Как им успокоиться, сделав 12 пересадок?
KC2. В круг сели 6 горе-музыкантов. При тех же условиях, какое наименьшее число пересадок им нужно, чтобы успокоиться?
KC3. Тот же вопрос для 7 музыкантов?

Билетёр и зрители
Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду. Все места заняты. Оказалось, что все места в первом ряду заняты. Билетёр может менять местами соседей, если оба сидят не на своих местах.
БЗ1. В ряду 10 мест. Зрители сели в обратном порядке. Как билетёру рассадить всех на свои места?
БЗ2. В ряду 2n мест. Зрители сели в обратном порядке. За какое наименьшее число пересадок билетёр может рассадить всех по своим местам?
БЗ3. В ряду произвольное число мест. Каждый зритель сидит не на своём месте. Всегда ли билетёр может рассадить всех на свои места?

Связка колец
На кольцевой шнур нанизана связка колец с разного размера номерами от 1 до N по часовой стрелке. Если номера колец отличаются на 2 или больше, их можно поменять местами, продев одно в другое. Кольца с соседними номерами так поменять нельзя.
СК1. N=5. Как расположить кольца в порядке 1, 3, 5, 2, 4?
СК2. Докажите, что при любом N кольца можно расположить в любом порядке, считая по часовой стрелке от кольца номер 1.

Столбики на линии
Посредине доски 1x1001 стоит столбик из 100 положенных друг на друга монет. За один ход разрешается снять с верха любого столбика k монет (где k - любое число от 1 до всех) и переставить их на k полей влево или вправо; если там уже стоит столбик, положить монеты на него.
СЛ1. Как передвинуть весь столбик на соседнее справа поле менее чем за 100 ходов?
СЛ2. Как передвинуть весь столбик на соседнее справа поле менее чем за 30 ходов?
СЛ3. Можно ли передвинуть весь столбик на соседнее справа поле менее чем за 15 ходов?

Ладьи до упора
Здесь каждая ладья может ходить только до упора в другую ладью или в край доски.
ЛУ1. В углах доски 8x8 стоят 4 ладьи. Можно ли собрать всех ладей в 4 центральных (цветных) клетках?
ЛУ2. В углах и центре клетчатой доски 9х9 стоят 5 ладей. Можно ли собрать всех ладей в виде «плюсика» (то есть поместить в 5 цветных клеток)?