Ответ 108

Январь 9, 2008

Наименьшее число обменов — 19.

Наиболее экономная система обменов состоит в том, чтобы укомплектование шашек вести цепочками, то есть, обменяв местами, например, шашки 1 и 7, поменять затем шашку 7 с той шашкой, которая занимает седьмое место, в данном примере — с шашкой 20. В свою очередь шашку 20 следует поменять стой, которая занимает ее место — с шашкой 16, а шашку 16 — с шашкой 11, которая незаконно расположилась на шестнадцатом месте и т. д., до завершения цепочки, когда обе обменивающиеся шашки попадут на свои зашитые места.

Тогда следует начать новую цепочку обменов, и так до полного их завершения.

Все перемещения, необходимые для решения данной задачи, располагаются в следующие 5 цепочек:

1)            1 и 7; 7 и 20; 20 и 16; 16 и 11; 11 и 2; 2 и 24;

2)            3 и 10; 10 и 23; 23 и 14; 14 и 18; 18 и 5;

3)            4 и 19; 19 и 9; 9 и 22;

4)            6 и 12; 12 и 15; 15 и 13; 13 и 25;

5)            17 и 21.

Схему необходимых перемещений можно наметить заранее, если предварительно выписать подряд номера всех шашек в их первоначальном расположении, а под ними порядковые номера: 7, 24, 10, 19, 3, 12, 20, 8, 22 и т. д. 1, 2, 3, 4, 5, 6, 7, 8, 9 и т. д. Вычеркиваем первую пару чисел 1 и 7; эти числа определяют первый обмен шашек, затем ищем 7 в нижнем ряду и замечаем над ним число 20; вычеркиваем числа 7 и 20; они определяют второй обмен шашек; ищем 20 в нижнем ряду, замечаем над ним 16; вычеркиваем числа 20 и 16; они определяют третий обмен соответствующих шашек и т. д.

Когда цепочка оборвется, начинаем составление ее следующего звена с самой крайней пары еще не зачеркнутых цифр слева.

В наихудшем случае могла бы образоваться одна цепочка; тогда для размещения 25 шашек потребовалось бы 25—1=24 обмена (в последнем обмене сразу две шашки занимают надлежащие места).

В данной задаче 5 цепочек, кроме того, одна шашка (8) уже в начальном положении занимает положенное ей место, поэтому для решения задачи необходимо и достаточно сделать 25—5—1=19 обменов.

Комметирование закрыто now!