Наименьшее число обменов — 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 обменов.
