Упорядочить расположение шашек

Расположите 25 нумерованных шашек в 25 квадратных клетках, как указано на рисунке.

Обменивая шашки местами, приведите их в порядок, то-есть уложите номера 1, 2, 3,
4, 5 слева направо в первый ряд, номера 6, 7, 8, 9, 10 слева направо во второй ряд и т. д. до конца. Можете, например, поменять местами номера 7 и 1, 24 и 2 и т. д.
Определите наименьшее число необходимых обменов.
Для того чтобы избежать бесполезных перемещений, следует разработать какую-нибудь систему перемещений. Подумайте об этом.

ScreenShot - 2013-07-12 в 23.03.20

Решение:

Наименьшее число обменов—19.
Наиболее экономная система обменов состоит в том, чтобы укомплектование шашек вести цепочками, то-есть, обменяв местами, например, шашки 1 и 7, поменять затем шашку 7 с той шашкой, которая занимает седьмое место, в данном примере—с шашкой 20. В свою очередь шашку 20 следует поменять с той, которая занимает ее место — с шашкой 16, а шашку 16 — с шашкой И, которая незаконно расположилась на шестнадцатом месте и т. д. до завершения цепочки, когда обе обменивающиеся шашки попадут на свои законные места.
Тогда следует начать новую цепочку обменов и так до полного их завершения.
Все перемещения, необходимые для решения данной задачи, располагаются в следующие 5 цепочек:
1 и 7; 7 и 20; 20 и 16; 16 и 11; 11 и 2; 2 и 24;
3 и 10; 10 и 23; 23 и 14; 14 и 18; 18 и 5;
4 и 19; 19 и 9; 9 и 22;
6 и 12; 12 и 15; 15 и 13; 13 и 25;
17 и 21.
Схему необходимых перемещений можно наметить заранее, если Предварительно выписать подряд номера всех шашек в их первоначальном расположении, а под ними порядковые номера:
7 24 10 19 3 12 20 8 22 и т. д.
1 2 3 45 6 78 9 и т. д.
Вычеркиваем первую пару чисел 1 и 7; эти числа определяют первый обмен шашек, затем ищем 7 в нижнем ряду и замечаем над ним число 20; вычеркиваем числа 7 и 20; они определяют второй обмен шашек; ищем 20 в нижнем ряду, замечаем над ним 16; вычеркиваем числа 20 и l6; они определяют третий обмен соответствующих шашек и т. д.
Когда цепочка оборвется, начинаем составление ее следующего звена с самой крайней пары еще не зачеркнутых цифр слева.
В наихудшем случае могла бы образоваться одна цепочка; тогда для размещения 25 шашек потребовалось бы 25 — 1 =24 обмена (в последнем обмене сразу две шашки занимают надлежащие места).
В данной задаче 5 цепочек, кроме того одна шашка (№ 8) уже в начальном положении занимает положенное ей место, поэтому для решения задачи необходимо и достаточно сделать
25 — 5 — 1 = 19 обменов.



Это не спам.

 

На нашем сайте собраны задачи занимательной арифметики, математики, геометрии;
задачи на смекалку и логику, головоломки, логические загадки, игры, ребусы и многое другое
2017 © Самый умный - математическая смекалка